자료구조 02 : 선택 정렬 (Selection Sort)

• 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

---

  선택 정렬(Selection Sort)은  정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식이다. 선택 정렬을 사용하여 특정 배열의 값을 오름차순으로 정렬하기 위한 다음과 같은 코드를 생각할 수 있다.

void SelectionSort(int arr[], int MAX) {     int i, j;     int min, temp;     for(i=0; i<MAX-1; i++) {         min = i;         for(j=i+1; j<MAX; j++) {             if(arr[j] < arr[min]) min = j;         }         temp = arr[i];         arr[i] = arr[min];         arr[min] = temp;     } }

  SelectionSort 함수의 인자 arr은 정렬되지 않은 배열이고 MAX는 배열의 개수가 들어온다. 함수는 처음에 min에 i의 값을 넣는다. 그리고 두번째 for문이 돌아가면서 arr[min] 보다 작은 값을 발견하면 min의 값을 j로 바꾼다. 그리고 j 변수로 돌아가는 for문이 완료 되었을 때 arr[i]와 arr[min]의 값을 교환한다. 쉽게 구현할 수 있는 만큼 프로그래밍시 개인적으로 자주 사용하는 정렬 기법이다. 

  자료구조를 처음배우거나, 알고리즘이 익숙하지 않으면(나같으면) 충분히 머리 아플 수 있다.. 그래서 동영상을 하나 준비했다. 루마니아 사피엔티아 대학교에서 촬영한 'Select-sort with Gypsy folk dance'. 선택 정렬을 집시 포크 댄스로 표현했다. 동영상을 보고나면 선택 정렬이 어떤 놈인지 대충 감이 잡힌다.

동영상 서비스가 종료되어 해당 콘텐츠를 재생할 수 없습니다.

  선택 정렬에서 두개의 반복문(위의 소스에서 for문)이 돌면서 시행되는 연산의 횟수는 다음과 같다. 

(MAX는 배열의 개수) 

(이렇게 표현하기도 한다.) 

  선택정렬은 비교 연산 및 이동 연산 횟수가 고정된 값(MAX의 제곱)이므로 최악의 연산 횟수의 경우나 평균 연산 횟수 값이나 정렬의 효율성은 MAX의 제곱이 된다. (사실 두개의 반복문이 종료된 후 반드시 교환 연산이 이루어지므로 최선, 최악의 의미가 없다.) 전체적인 알고리즘 효율성을 볼 때 느리다는 점과, 안정성을 만족하지 않는다(같은 값의 인덱스끼리도 교환 연산이 발생 가능)는 단점이 있다.

참고 도서

---

자료구조

저자

이상진 지음

출판사

프리렉 | 2010-01-15 출간

카테고리

컴퓨터/IT

책소개

열혈강의 자료구조 출판사 서평자료구조에 대한 지식을 쌓고 관련 ...

---