[Algorithm] Selection Sort (선택 정렬) 이해하기

- 목차

 

* 소개

선택 정렬 ( selection sort ) 는 가장 일반적이고 직관적인 정렬방법입니다.

배열의 가장 크거나 작은 수를 찾아 정렬되어야 할 위치로 이동시킵니다.

 

예를 들어, 가장 큰 수를 찾아 배열의 첫번째 위치에 두고,

두번째 큰 수를 찾아 두번째 자리에 둡니다.
이러한 동작을 배열이 정렬될 때 까지 반복합니다.

 

가장 큰 수를 찾아 알맞게 정렬시키는 방식이 직관적이기 때문에

정렬 알고리즘 중에서 가장 이해하기 쉬운 정렬 방식입니다.

간단하게 시간복잡도를 살펴보겠습니다.  
만약 배열의 길이가 n 이라고 한다면,
모든 수들 중에서 가장 크거나 작은 수를 찾는데에 n 의 시간이 소요됩니다.

왜냐하면 모든 값들을 일일이 비교해야하기 때문입니다.

그리고 나머지 모든 값들도 가장 그거나 작은 수를 찾는 과정을 반복해야합니다.

그래서 n 의 시간이 소요됩니다.

 

과정 1 ) 모든 값들의 크기 비교 -> n 시간 소요.

모든 값들에 대해 반복적으로 "과정 1" 을 적용 -> n 시간 소요.

 

그렇게하여 총 n^2 의 시간이 소요됩니다.

 

* 예시

 

무작위로 나열된 수들이 있다고 가정하겠습니다.

그리고 오름차순 정렬을 시도해보겠습니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

무작위로 나열된 수들 중에서 가장 작은 수를 찾아야합니다.

 

첫번째로 작은 값을 찾습니다.

 

1.

5와 4를 비교하니 4 가 작으므로 2번째 값이 가장 작은 값으로 선택됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

2.

4와 7를 비교하니 4 가 작으므로 2번째 값이 가장 작은 값으로 유지됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

3.

4와 6를 비교하니 4 가 작으므로 2번째 값이 가장 작은 값으로 유지됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

4.

4와 9를 비교하니 4 가 작으므로 2번째 값이 가장 작은 값으로 유지됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

5.

4와 2를 비교하니 2 가 작으므로 6번째 값이 가장 작은 값으로 선택됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

6.

2와 3 를 비교하니 2 가 작으므로 6번째 값이 가장 작은 값으로 유지됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

7.

2와 1 를 비교하니 1 가 작으므로 8번째 값이 가장 작은 값으로 선택됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

8.

1와 8 를 비교하니 1 가 작으므로 8번째 값이 가장 작은 값으로 유지됩니다.

5, 4, 7, 6, 9, 2, 3, 1, 8

 

가장 작은 값으로 선택된 8번째 값인 1 이 배열의 첫번째 위치로 이동합니다.

 

1, 5, 4, 7, 6, 9, 2, 3, 8

 

 

아래의 배열에서 두번째로 작은 값을 찾습니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

1.

5와 4를 비교하니 4 가 작으므로 3번째 값이 가장 작은 값으로 선택됩니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

2.

4와 7를 비교하니 4 가 작으므로 3번째 값이 가장 작은 값으로 유지됩니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

3.

4와 6를 비교하니 4 가 작으므로 3번째 값이 가장 작은 값으로 유지됩니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

4.

4와 9를 비교하니 4 가 작으므로 3번째 값이 가장 작은 값으로 유지됩니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

5.

4와 2를 비교하니 2 가 작으므로 7번째 값이 가장 작은 값으로 선택됩니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

6.

2와 3 를 비교하니 2 가 작으므로 7번째 값이 가장 작은 값으로 유지됩니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

7.

2와 8 를 비교하니 2 가 작으므로 7번째 값이 가장 작은 값으로 유지됩니다.

1, 5, 4, 7, 6, 9, 2, 3, 8

 

두번째로 작은 값으로 선택된 7번째 값인 2 이 배열의 첫번째 위치로 이동합니다.

 

1, 2, 5, 4, 7, 6, 9, 3, 8

 

이러한 방식의 정렬이 모든 값에 적용됩니다.

 

* 코드

<Python Code by chat GPT>

def selection_sort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):
        # Find the minimum element in the remaining unsorted array
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # Swap the found minimum element with the element at index i
        arr[i], arr[min_index] = arr[min_index], arr[i]

 

<Javascript Code by chat GPT>

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the index of the minimum element in the remaining unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the minimum element with the current element (at index i)
    const temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

 

 

<Java Code by chat GPT>

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;

            // Find the index of the minimum element in the remaining unsorted portion
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the minimum element with the current element (at index i)
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

 

 

<Go Code by chat GPT>

package main

import "fmt"

func selectionSort(arr []int) {
	n := len(arr)

	for i := 0; i < n-1; i++ {
		minIndex := i

		// Find the index of the minimum element in the remaining unsorted portion
		for j := i + 1; j < n; j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}

		// Swap the minimum element with the current element (at index i)
		arr[i], arr[minIndex] = arr[minIndex], arr[i]
	}
}