Gwangyong Jeong

tyjk32@gmail.com

Backend Engineer

Updated:

1. 개요

선택 정렬(Selection Sort)은 기준 하나를 선택해서 그 값과 나머지 전부를 비교하여, 올바른 순서로 되어있지 않은 경우 두 값을 서로 교환하는 방식으로 정렬하는 방법을 말한다. 예제를 통해 선택 정렬(Selection Sort)의 동작 방식에 대해 알아보도록 하자.

2. 예제

아래와 같이 5개의 값이 들어있는 배열을 오름차순으로 정렬해보도록 하자.

  1. 배열의 [0]을 기준으로 [0], [1]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 5가 [1]의 값인 4보다 크므로 자리가 바뀐다.

  2. 배열의 [0]을 기준으로 [0], [2]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 4가 [2]의 값인 1보다 크므로 자리가 바뀐다.

  3. 배열의 [0]을 기준으로 [0], [3]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 1이 [3]의 값인 3보다 작으므로 자리가 바뀌지 않는다.

  4. 배열의 [0]을 기준으로 [0], [4]의 값을 비교하여 [0]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [0]의 값인 1이 [4]의 값인 2보다 작으므로 자리가 바뀌지 않는다.

  5. 배열의 [0] 인덱스의 정렬이 완료되었다. 정렬 결과 가장 작은 값이 [0] 인덱스에 오게 되었다.

  6. 배열의 [1]을 기준으로 [1], [2]의 값을 비교하여 [1]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [1]의 값인 5가 [2]의 값인 4보다 크므로 자리가 바뀐다.

  7. 배열의 [1]을 기준으로 [1], [3]의 값을 비교하여 [1]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [1]의 값인 4가 [3]의 값인 3보다 크므로 자리가 바뀐다.

  8. 배열의 [1]을 기준으로 [1], [4]의 값을 비교하여 [1]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [1]의 값인 3가 [4]의 값인 2보다 크므로 자리가 바뀐다.

  9. 배열의 [1] 인덱스의 정렬이 완료되었다. 정렬 결과 두 번째로 작은 값이 [1] 인덱스에 오게 되었다.

  10. 배열의 [2]를 기준으로 [2], [3]의 값을 비교하여 [2]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [2]의 값인 5가 [3]의 값인 4보다 크므로 자리가 바뀐다.

  11. 배열의 [2]를 기준으로 [2], [4]의 값을 비교하여 [2]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [2]의 값인 4가 [4]의 값인 3보다 크므로 자리가 바뀐다.

  12. 배열의 [2] 인덱스의 정렬이 완료되었다. 정렬 결과 세 번째로 작은 값이 [2] 인덱스에 오게 되었다.

  13. 배열의 [3]을 기준으로 [3], [4]의 값을 비교하여 [3]의 값이 더 큰 경우 서로 자리를 바꿔준다. 여기서는 [3]의 값인 5가 [4]의 값인 4보다 크므로 자리가 바뀐다.

  14. 배열의 [3] 인덱스의 정렬이 완료되었다. 정렬 결과 네 번째로 작은 값이 [3] 인덱스에 오게 되었다.

  15. 배열의 [4] 인덱스의 정렬이 완료되었다. 정렬 결과 다섯 번째로 작은 값이 [4] 인덱스에 오게 되었다.

내림차순 정렬 시, 동일한 과정으로 비교해 나가며 기준 값이 비교 값보다 작은 경우, 자리를 바꿔서 더 큰 수가 기준 값이 되도록 정렬을 해나가면 된다.

3. 시간 복잡도

Best Average Worst
O(N^2) O(N^2) O(N^2)

첫 번째 수 기준 반복문 횟수 : N - 1

두 번째 수 기준 반복문 횟수 : N - 2

…

N-1 번째 수 기준 반복문 횟수 : 1

N 번째 수 기준 반복문 횟수 : 0

∴ 총 반복문 횟수 = n(n - 1) / 2

4. 구현 코드

4-1. C++

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/selectionSort.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
#include <vector>

using namespace std;

void selectionSortAscending(vector<int> v) {
    int size = v.size();

    for (int i = 0; i < size - 1; ++i) {
        for (int j = i + 1; j < size; ++j) {
            if (v[i] > v[j]) {
                int temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
        }
    }

    cout << "오름차순 정렬 후 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';
}

void selectionSortDescending(vector<int> v) {
    int size = v.size();

    for (int i = 0; i < size - 1; ++i) {
        for (int j = i + 1; j < size; ++j) {
            if (v[i] < v[j]) {
                int temp = v[i];
                v[i] = v[j];
                v[j] = temp;
            }
        }
    }

    cout << "내림차순 정렬 후 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';
}

int main(void) {
    ios_base::sync_with_stdio(false);

    vector<int> v = { 5, 4, 1, 3, 2 };

    cout << "정렬 전 : ";
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    cout << '\n';

    selectionSortAscending(v);
    selectionSortDescending(v);

    return 0;
}

[실행 결과]

4-2. JAVA

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/selectionSort.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {5, 4, 1, 3, 2};

        System.out.print("정렬 전 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr[i] + " ");
        System.out.println();

        selectionSortAscending(arr);
        selectionSortDescending(arr);
    }

    public static void selectionSortAscending(int[] arr) {
        int[] arr2 = arr.clone();
        int size = arr2.length;

        for(int i = 0; i < size - 1; ++i) {
            for(int j = i + 1; j < size; ++j) {
                if(arr2[i] > arr2[j]) {
                    int temp = arr2[i];
                    arr2[i] = arr2[j];
                    arr2[j] = temp;
                }
            }
        }

        System.out.print("오름차순 정렬 후 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr2[i] + " ");
        System.out.println();
    }

    public static void selectionSortDescending(int[] arr) {
        int[] arr2 = arr.clone();
        int size = arr2.length;

        for(int i = 0; i < size - 1; ++i) {
            for(int j = i + 1; j < size; ++j) {
                if(arr2[i] < arr2[j]) {
                    int temp = arr2[i];
                    arr2[i] = arr2[j];
                    arr2[j] = temp;
                }
            }
        }

        System.out.print("내림차순 정렬 후 : ");
        for(int i = 0; i < 5; ++i) System.out.print(arr2[i] + " ");
        System.out.println();
    }
}

[실행 결과]

Updated:

Leave a comment