선택 정렬

선택 정렬

• 배열 안의 자료중 가장 작은수(혹은 가장 큰 수)를 찾아 첫번째 위치(혹은 가장
  마지막 위치)의 수와 교환해주는 방식의 정렬
• 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가

실행

• 우리에게 5,1,6,2,4,3 이란 배열이 주어지고 선택 정렬을 이용하여 정렬해줘야
  한다면 의사코드를 다음과 같이 만들수 있다.

        repeat for the amount of elements in the array
        find the smallest unsortted value
        swap that value with the first unsorted value

풀이

1. 프로그램은 array라는 배열의 첫번째 자리(5)에서 시작한다.
2. 가장 작은 원소를 찾기 위해 5를 (1,6,2,4,3)와 비교한다.
3. 1이 가장 작은 값이기 때문에 5의 위치와 교환합니다.
4. 이제 1은 정렬되었으며 나머지 5,6,2,4,3은 여전히 정렬되지 않은 상태이다.
5. 다음은 두 번째 자리(5)인데, 정렬되지 않은 오른쪽(6,2,4,3) 부분만 확인
6. 2가 정렬되지 않은 배여르이 원소 중 가장 작은 원소이므로 5의 자리와 바꿔준다.
7. 이와 같은 방식으로 계속해서 비교화 교환을 반복

    step 5에 이르면 우리는 배열이 정렬되었다는 것을 알 수 있지만 컴퓨터는  
    우리 처럼 큰 그림을 볼 수 없다는 것을 알아야 한다. 따라서 step6으로 넘어가
    5와 6의 크기 비교까지 마친후에야 알고리즘이 종료된다.

정렬된 배열

• 버블 정렬과는 다르게 몇번의 교환을 해주었는지 횟수를 셀 필요가 없다.
• 하지만 이과정은 우리가 해야 할 비교 횟수보다 훨씬 더많은 비교가 필요하므로
  비용이 많이 든다.
• 배열의 순서와 상관없이, 선택 정렬로 정렬되는 배열은 n-1번의 교환이 필요.
• n-1번의 교환은 확실히 버블 정렬의 교환 횟수보다는 적다.

    그러나 한번의 교환이 일어나기 위해서는 정렬되지 않은 수의 모든 비교가
    이루어져야 하므로, n²번의 비교가 이루어진다.

• 최선의 경우에도 최악의 경우에도 수행하는 횟수만큼 비교와 교환을 해야함

생각해보기

• 선택 정렬이 버블 정렬보다 선호되는 경우는 어떤 경우인가요?

    이동해야할 데이터 크기가 작다면 선택정렬이 좀 더 효율적

• 선택 정렬을 이용하여 4, 30, 49, 11, 5를 정렬해 봅시다.

    0.   4, 30, 49, 11, 5
    1.   4,  5, 49, 11, 30
    2.   4,  5, 11, 49, 30
    3.   4,  5, 11, 30, 49