[정렬 알고리즘] Seletion Sort (선택 정렬)

§선택 정렬

정렬 되지 않은 부분에서 최소 요소(오름차순 일때)를 반복적으로 찾아 시작 부분에 배치하여 배열을 정렬한다.

 

주어지는 배열은 두가지 경우를 생각 해볼 수 있다.

1. 부분 배열이 이미 정렬 되었을때
2. 부분 배열이 정렬 되지 않은 상태일때

 

Following example explains the above steps:

 

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

Time Complexity: O(n2) as there are two nested loops.

Auxiliary Space: O(1)

 

구현 방법

1. 가장 작은 원소를 남은 배열에서 고른다.
2. 해당 원소와 시작지점의 자리를 바꾼다.
3. 배열 시작지점을 앞으로 옮긴다.

 

 

구현언어(C)

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

//////////////////////////////// //    Selection Sort //    선택 정렬 ////////////////////////////////   #include <stdio.h>   void swap(int *xp, int *yp) {     int tmp = *xp;     *xp = *yp;     *yp = tmp; }   void selectionSort(int arr[], int n) {     int i, j, min_idx;            for (i = 0; i < n - 1; i++) {         min_idx = i;    //최소 원소를 찾는다.         for (j = i + 1; j < n; j++)             if (arr[j] < arr[min_idx])                 min_idx = j;           //최소 원소와 i번째 원소 자리를 바꾼다.         swap(&arr[min_idx], &arr[i]);     } }   void printArray(int arr[], int size) {     int i;     for (i = 0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); }   int main() {     int arr[] = { 64, 25, 12, 22, 11 };     int n = sizeof(arr) / sizeof(arr[0]);     printf("Before array: ");     printArray(arr, n);     selectionSort(arr, n);     printf("Sorted array: ");     printArray(arr, n);     return 0; } Colored by Color Scripter

cs