Selection Sort (선택 정렬)

선택 정렬은 간략하게 설명하자면 끝에서 잡던, 앞에서 잡던, 한 지점을 잡고 시작하며 현재 찾은 제일 낮은 값을 맨 앞으로 옮긴다. 예를 들면 한 배열이 A가 다음 숫자들을 다음과 같이 정의했다: [5, 4, 7, 3]. A[0...3]에서 가장 적은 값이 3이며, 3이 맨 앞자리 A[0]에다 옮겨지며 기존에 있던 A[0]값 -> 5는 기존에 있던 3의 위치 -> A[3]에 옮겨진다. 이제 A[1...3]에서 가장 적은 값을 찾아야하는데 가장 적은 값은 A[1]에 위치한 4이다. 따라서 A[1]에 4가 유지되며 바꿔치기를 할 필요가 없다. 대충 A[3]까지 반복이 되면서 [3, 4, 5, 7]로 정렬된다.

 

이해가 안 갔으면 다음 비쥬얼을 참고하면 된다.

 

메서드: Naive 네이브

의사코드는 다음과 같다.

  Selection-Sort(A)
      n = length(A)
    for i = 1 to n - 1
        minIndex = i
        for j = i + 1 to n
            if A[j] < A[minIndex] 
                minIndex = j
            Swap A[i] with A[minIndex]

 

두 개의 for loop들이 서로 겹치기 때문에 총 시간 복잡도는 O(n^2)이다. 공간 복잡도 마저 O(1)이기 때문에 메모리 공간이 압박할 때에 쓰기 좋은 정렬 알고르짐들 중 하나다. 하지만 성능이 삽입 정렬 만큼 하지 못해 아쉬운 점이 있다. 

 

 

아래의 깃허브 레포지토리에 선택 정렬 알고리즘을 응용한 프로그램을 구현했다. 응용할 때 참고하기 좋을 거다. 

yoonBot/Algorithm-Collection