선택 정렬(Selection Sort)

: 제자리 정렬
: 불안정 정렬
: 시간 복잡도는 O(n^2)

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

for i = 0 to n:
    a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
    a[i]와 a[j]의 값을 서로 맞바꾼다.

위키피디아에서 가져온 의사코드

---

특징

• 제자리 정렬(in-place sort)
  추가적인 공간이 필요하지 않은 정렬
  최솟값을 찾고 값 자체를 교환하니까

• 불안정 정렬(unstable)
  동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식
  예를 들어서 b B c a 가 있다고 하면
  선택 정렬시 a B b c 가 됨

• 시간 복잡도는 O(n^2)
  비교하는데 for 또는 while 문을 2번 돌아서
  (n-1) + (n-2) + ... + 2 + 1 = n*(n-1)/2 = O(n^2)

• 전체 이동은 O(n)
  주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로
  3(n-1) = O(n)
  3인 이유는 swap을 하기 위해서는 3번의 이동이 필요하므로

---

개선방법

• 이중 선택 정렬
  : 한 번의 탐색에서 최솟값과 최댓값을 같이 찾는 방법이다. 탐색 횟수가 절반으로 줄어들게 된다.

• 탐색을 응용하여 개선
  : 한 번의 탐색 때 동일한 값이 있다면 함께 정렬하는 방법. 즉, 만약 최솟값을 찾았는데 그 값과 같은 값이 있다면 다음 번 탐색 때 최솟값으로 탐색될 것이기에 이 값도 탐색된 것으로 보고 미리 정렬한다. 같은 값이 많을수록 유용하게 된다.

---

소스코드

#include <stdio.h>

void ft_swap(int *a, int *b)
{
    int c;
    c = *a;
    *a = *b;
    *b = c;
}

void selection_sort(int *arr, int n)
{
    int i;
    int j;
    int min;

    i = 0;
    while (i < n)
    {
        min = i;
        j = i + 1;
        while (j < n)
        {
            if (arr[min] > arr[j])
                min = j;
            j++;
        }
        if (min != i)
            ft_swap(&arr[i], &arr[min]);
        i++;
    }
}

---

참고

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
https://mygumi.tistory.com/94
https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=wjdwoaud159&logNo=222365210954&categoryNo=0&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView
C언어로 쉽게 풀어쓴 자료구조