선택 정렬 (Selection Sort)

선택 정렬은 매 차례마다 정렬되지 않은 원소들을 모두 확인하여 각 인덱스에 맞는 원소를 선택하여 해당 인덱스의 원소와 교환해주는 정렬입니다.

매 차례마다 남은 원소들을 모두 확인하기 때문에 시간 복잡도는 최악의 연산 횟수나 평균 연산 횟수나 O(N^2)입니다.

Selection Sort (SCPC)

그림을 통해 각 순서에 대해 설명하도록 하겠습니다.

1.  먼저 가장 작은 값을 첫 번째 값인 15로 지정하고, minimum index를 0으로 놓습니다.
2. 그 수의 뒤에 있는 모든 수와 비교하면서, minimum index에 있는 수보다 작은 수일 경우 minimum index를 해당 수의 인덱스로 바꿔줍니다.
3. 연산이 끝나면 마지막 수인 1이 minimum index가 되고 해당 수와 처음 인덱스를 바꿔줍니다.
4. 첫 번째 수는 제대로 정렬된 수이므로 다음 수인 4를 가장 작은 값으로 지정하고 minimum index를 1로 놓습니다.
5. (2),(3)의 과정을 실행합니다. 그러면 가장 작은 수는 3이므로 해당 수와 1번 인덱스의 수를 바꿔줍니다.

이러한 과정은 각각의 인덱스에 맞는 수를 하나하나 찾아가는 연산이라는 것을 알 수 있습니다.

다음은 C++로 선택정렬을 나타낸 것입니다.

#include <iostream>
using namespace std;
#define MAX 5005
int arr[MAX];
int N;
void Swap(int &a, int &b) {
    int temp =a;
    a = b;
    b = temp;
}

void selection_sort(int *arr, int size) {
    for (int i = 0; i < size; i++) {
        int minidx = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[minidx] > arr[j]) {
                minidx = j;
            }
        }
        Swap(arr[minidx], arr[i]);
    }
}
int main() {

    cin>>N;
    for(int i=0; i < N; i++) {
        cin>>arr[i];
    }
    selection_sort(arr, N);
    for (int i = 0; i < N; i++) {
        cout << arr[i] << ' ';
    }
    cout << endl;

    return 0;
}

다음은 Java 입니다.

import java.util.*;

public class Main {

    static void selection_sort(int arr[], int size) {
        for (int i = 0; i < size; i++) {
            int minidx = i;
            for (int j = i + 1; j < size; j++) {
                if (arr[minidx] > arr[j]) {
                    minidx = j;
                }
            }
            int temp = arr[minidx];
            arr[minidx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        int[] arr = new int[5005];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        selection_sort(arr, n);
        for (int i = 0; i < n; i++) {
            System.out.print(String.valueOf(arr[i]) + ' ');
        }
        System.out.println("");
    }

}

다음 시간엔 삽입 정렬에 대해 알아보겠습니다.