Selection sort

선택정렬 작성에 필요한 생각의 변화를 작성하고, 구현을 진행한다.

기본규칙

1) sorted list 와 unsorted list 를 둔다.
2) unsorted list 에서 가장 작은 값을 찾아 sorted list 뒤에 둔다.
3) unsorted list 가 빌 때까지 반복한다.

생각의 변화

&A 를 넘겨야 수정이 된다.

j 루프는 i 부터 시작해야 한다.
j 루프는 <= n-1 까지 진행해야 한다.
i 루프는 < n-1 만 진행해도 된다.

min 값 뿐만 아니라 min index 도 필요하다.
min 값과 min index 는 i 루프 시작할때마다 갱신되어야 한다.

pseudo code

selection_sort(&A)

for i=0  i < n-1  i++
    k = i
    min = A[k]
    for j=i  j <= n-1  j++
        if min > A[j]
            min = A[j]
            k = j
    swap A[i] A[k]        

검증

12 25 64 11 22
ij

min 12 0

min 11 3, swap i min

11 25 64 12 22
   ij

   min 25 1
   
   min 11 3, swap i min
   
11 12 64 25 22
      ij
      
      min 64 2
      
      min 22 4, swap i min
      
11 12 22 25 64
         ij
         
         min 25 3
         
         min 25 3

         stop

시간복잡도

min 을 찾기위해 n-1, n-2, ... , 1회 비교가 수행된다.
따라서

O(n^2) 가 된다.

• https://en.wikipedia.org/wiki/Selection_sort#Complexity