[알고리즘] 선택 정렬 (selection sort) 이란?

📚 선택 정렬 알고리즘이란?

선택 정렬은 제자리 정렬 알고리즘이라도 불린다. 선택 정렬은 정렬되지 않은 리스트에서 가장 작은(또는 큰) 원소를 선택하여 해당 원소를 리스트의 앞쪽부터 차례대로 정렬해 나가는 알고리즘이다. 리스트의 각 요소를 한번씩 검사하여, 해당 순서에 맞는 원소를 선택하고 그 자리에 배치한다.

 

1️⃣ 선택 정렬의 구체적 과정

 

1) 배열에서 최솟값을 찾아 배열의 맨 앞 요소와 교환한다.

 

2) 그 다음, 나머지 배열에서 다시 최솟값을 찾아 두 번째 요소와 교환

 

3) 이 과정을 배열이 정렬될 때까지 반복

 

2️⃣ 시간복잡도 비교

 

3️⃣ Java로 알아보는 선택 정렬

import java.util.*;

public class Main {
    public static void selection (int[] data) {
        for (int i = 0 ; i < data.length-1 ; i++) {
           int minIndex = i;
            for (int j = i + 1; j < data.length ; j++) {
                if (data[minIndex] > data[j]) {
                    minIndex = j;
                }
            }
            int temp = data[minIndex];
            data[minIndex] = data[i];
            data[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] sort = {5, 2, 9, 1, 5, 6};

        selection(sort);
        for (int i = 0 ; i < sort.length ; i++) {
            System.out.print(sort[i] + " ");
        }
    }
}

 

4️⃣ Python로 알아보는 선택 정렬

data = [5, 2, 9, 1, 5, 6]

def selections(arr):
    for i in range(len(arr)-1):
        temp = i
        for j in range(i+1, len(arr)):
            if data[temp] > data[j]:
                temp = j
        min = data[temp]
        data[temp] = data[i]
        data[i] = min

selections(data)

print(data)