[Java+Python]선택 정렬(Selection Sort)

<Java + Python>으로 구현한 다른 정렬:

 

[Java+Python]삽입 정렬(Insert Sort)

[Java+Python]버블 정렬(Bubble Sort)

[Java+Python]병합 정렬(Merge Sort)

[Java+Python]힙 정렬(Heap Sort)

[Java+Python]퀵 정렬(Quick Sort)

[Java+Python]카운팅 정렬(Counting Sort)

 

선택 정렬은 한 마디로 말하면 처음부터 끝까지 훑어서 가장 작은(혹은 큰) 숫자를 처음 인덱스에 넣는 방식이다.

 

시간 복잡도가 같은 삽입 정렬이나 버블 정렬이 그때그때 값을 바꾸는 데 비해

 

선택 정렬은 한 바퀴에 한 번씩 원소를 배정한다.

 

어떤 정렬 상황에서건 일관되게 O(N²)의 속도를 보여준다는 특징도 가지고 있으며,

 

버블 정렬에 비해 두 배 정도 빠르며 삽입정렬에 비해 근소하게 느리다고 한다.

 

추가로 칵테일 정렬을 도입하면 반복 횟수를 절반으로 줄일 수 있으며, 이를 이중 선택 정렬이라 부르기도 한다.

 

계속해서 실제 작동 방식과 구현에 대해 살펴보자.

 

Algorithm

 

오름차순의 경우 최소값을 저장해가며 끝까지 순회하고,

 

스왑이 필요하다면 스왑하고 다음 원소부터 순회하는 것을 확인할 수 있다.

 

Implementation

 

구현은 간단하다.

 

최솟값과 그 인덱스를 저장해서 가지고 있다가

 

순회 끝에 오면 해당 값을 시작 인덱스의 값과 바꾼다.

import java.util.Arrays;

public class SelectionSort {

    public static void main(String[] args) {

        int[] arr = {4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0};

        selectionSortImpl(arr);

        System.out.println(Arrays.toString(arr));
    }
    public static void selectionSortImpl(int[] arr) {

        for (int i = 0; i < arr.length - 1 ; i++) { // 0번 인덱스에서 시작

            int min = arr[i]; // 처음 값을 최솟값에 넣어둠
            int minIdx = i; // 마찬가지로 처음 인덱스를 최솟값 인덱스에 넣어둠

            for (int j = i + 1; j < arr.length; j++) {

                if (arr[j] < min)  {
                    min = arr[j]; // i 번째 원소가 더 작으면 저장
                    minIdx = j;
                }
            }
            int tmp = arr[i]; // 한 바퀴 다 돌면 스왑
            arr[i] = arr[minIdx];
            arr[minIdx] = tmp;
        }
    }
}

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]

파이썬 구현은 아래와 같다.

def selection_sort(target):
    for i in range(len(target) - 1):
        min = target[i]
        minidx = i

        for j in range(i + 1, len(target)):
            if target[j] < min:
                min = target[j]
                minidx = j

        temp = target[i]
        target[i] = target[minidx]
        target[minidx] = temp


target = [4, 16, 31, 5, 4, 17, 1, 10, 15, 3, 16, 6, 7, 2, 2, 1, 5, 13, 17, 14, 4, 0]

selection_sort(target)

print(target)

[0, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 10, 13, 14, 15, 16, 16, 17, 17, 31]