[C] 선택정렬 개념, 알고리즘, 코드 정리

선택정렬

---

첫번째 항목부터 최소값을 탐색하여 교환하며 정렬하는 방식입니다.

n 개의 주어진 리스트를 정렬하는데 O(n^2) 만큼의 시간이 걸립니다.

선택정렬의 알고리즘

---

1. 주어진 리스트 중에 최소값을 찾습니다.

2. 찾은 값을 맨 앞에 위치한 값과 교체합니다.

3. 맨 처음 위치를 뺀 나머지를 같은 방법으로 교체합니다.

선택정렬의 예제

---

가장 작은값(0)을 찾은 뒤 가장 좌측값(9)와 교환합니다.

9,1,6,8,4,3,2,0
0,1,6,8,4,3,2,9

가장 작은 값(1) 을 찾은 뒤 가장 좌측에서 다음번의 위치와 교환합니다. (여기에서는 같은 값이므로 교환되지 않습니다.)

0,1,6,8,4,3,2,9

가장 작은 값(2) 를 찾은 뒤 그 다음의 좌측값(6)과 교환합니다.

0,1,6,8,4,3,2,9
0,1,2,8,4,3,6,9

위의 작업을 정렬이 끝날때까지 반복합니다.

선택정렬의 소스

---

#include <stdio.h>

void selectionSort(int *list, const int n)
{
  int i, j, indexMin, temp;

  for (i = 0; i < n - 1; i++)
  {
    indexMin = i;
    for (j = i + 1; j < n; j++)
    {
      if (list[j] < list[indexMin])
      {
        indexMin = j;
      }
    }
    temp = list[indexMin];
    list[indexMin] = list[i];
    list[i] = temp;
  }
}

int main()
{
  int i;
  int list[10] = {5, 3, 8, 4, 9, 1, 6, 2, 7};

  selectionSort(list, 10);

  for(i=0; i<10; i++){
    printf("%d  ", list[i]);
  }
  return 0;
}

     위키에 첨부된 소스에서 main 함수를 넣어 완성시킨 코드입니다.