선택, 버블, 삽입 정렬

정렬

시간 복잡도 O(N^2)인 세 가지 정렬을 알아보자.

모두 N이 1~100 사이로 지정되고, 임의의 N 개의 숫자를 오름차순 정렬한다고 가정한다.

선택 정렬

• 첫 번째 for 문이 처음부터 끝까지 순회한다.
• 첫 번째 for 문의 인덱스를 idx라는 변수에 선언한다.
• 두 번째 for 문이 첫 번째 for 문의 다음 수 부터 순회한다.
• j에서 순회하는 배열의 수가 idx 번째 배열의 수 보다 작으면 idx를 j로 바꿔준다.
• 두 번째 순회가 끝나면 idx 번째 수와 첫 번째 for 문의 i번 째 수를 서로 교체한다.

#include <iostream>
using namespace std;
int main(void) {
    int arr[101];
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
    for (int i = 0; i < N; i++) {
        int idx = i;
        for (int j = i + 1; j < N; j++) {
            if (arr[j] < arr[idx]) idx = j;
        }
        int tmp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = tmp;
    }
    for (int i = 0; i < N; i++) cout << arr[i] << ' ';
    cout << 'endl';
}

버블 정렬

• 첫 번째 for 문이 처음부터 끝-1까지 순회한다.
• 두 번째 for 문은 항상 처음부터 끝 - i - 1까지 순회한다.
• 두 번째 for 문의 j번 째 수가 j + 1 번째 수 보다 크다면 두 수를 swap 한다.
• 두 번째 for 문이 끝나면 가장 큰 수가 가장 오른쪽에 위치하게 된다.
• 이를 첫 번째 for 문의 횟수만큼 반복하면 오름차순으로 정렬된다.

#include <iostream>
using namespace std;
int main(void) {
    int N;
    cin >> N;
    int arr[101];
    for (int i = 0; i < N; i++) cin >> arr[i];
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < N - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    for (int i = 0; i < N; i++) cout << arr[i] << ' ';
    return 0;
}

삽입 정렬

• 첫 번째 for 문이 처음+1부터 끝까지 순회한다.
• 두 번째 for 문은 항상 i-1부터 0까지 반대로 순회한다.
• 두 번째 for 문을 시작할 때, 첫 번째 for 문 인덱스의 수를 tmp에 저장한다.
• tmp에 저장된 수 보다 j에 있는 수가 크다면 j+1에 j 번째 수를 삽입한다.
• 크지 않다면 for 문을 종료하고 마지막으로 돌았던 j에 다음 인덱스에 tmp의 값을 삽입한다.
• for 문이 break 없이 돌았다면 -1 + 1인 0번째 인덱스에 tmp가 삽입된다.
• 이러한 과정을 거치면, 첫 번째 for 문이 진행될 때마다 큰 수는 오른쪽으로 이동하고 tmp는 자신의 순서에 맞게 삽입된다.

#include <iostream>
using namespace std;
int main(void) {
    int N;
    cin >> N;
    int arr[101];
    for (int i = 0; i < N; i++) cin >> arr[i];
    for (int i = 1; i < N; i++) {
        int tmp = arr[i];
        int j;
        for (j = i - 1; j >= 0; j--) {
            if (tmp < arr[j]) arr[j + 1] = arr[j];
            else break;
        }
        arr[j + 1] = tmp;
    }
    for (int i = 0; i < N; i++) cout << arr[i] << ' ';
    return 0;
}