자료구조 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

책소개

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

---