O(n^2) 정렬 알고리즘

삽입 정렬(Insertion Sort)

가장 기초적인 삽입 정렬에 대해서도 한번 알아보자.

시간 복잡도는 우선 아래 코드에서 보면 알 수 있지만 O(N^2)이다.

삽입정렬은 위의 두가지 방식처럼 움직인다.

즉, 현재 자신이 선택한 인덱스 k의 값을 key라 생각하고 

k~0까지 반복해 나가며 

k - 1의 값이 key보다 크면 k에 k -1 값을 넣고 k - 1에 key를 넣어주는 방식을 이용한다.

아래 코드를 보면 바로 이해를 할 수 있다.

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

#include <iostream> #include <cstdio>   using namespace std;   int arr[] = { 5,1, 2, 3,2,1 }; int n = 6; int cnt; void print() {     printf("[[ round :: %d ]]\n", ++cnt);     for (int i = 0; i < n; i++)         printf("%d ", arr[i]);     printf("\n"); } int main() {     for (int i = 1; i < n; i++) {         print();         int key = arr[i];         for (int j = i - 1; j >= 0; j--)         {             print(); // 지워도 되나 좀 더 정확한 순서를 파악 가능하다.             if (arr[j] > key) {                 arr[j + 1] = arr[j];                 arr[j] = key;             }             else                 break;         }     }     print();     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

    for (int i = 1; i < n; i++) { // key를 순회

        int key = arr[i]; // 현재 자신이 선택한 인덱스 값을 key로 지정

        for (int j = i - 1; j >= 0; j--) // ~0까지 반복해나가며

        {

            if (arr[j] > key) { // 현재 값이 key보다 크면

                arr[j + 1] = arr[j]; // j + 1에 j값을 넣고

                arr[j] = key; // j에 key 값을 넣는다.

            }

            else // 삽입 정렬은 앞이 무조건 정렬이 됨을 보장해주기에 else면 break;

                break;

        }

    }

결국 계속 설명하고자 했던 말이 위의 그림과 같은 말이다.

1을 처음에 key로 잡고 자신보다 큰값이면 swap해주는 방식이다.

선택 정렬(Selection Sort)

선택 정렬은 해당 인덱스를 기준으로 자신보다 작은 값이 있는 인덱스가 있다면 계속해서 메모해둔 뒤

마지막에 현재 시작 위치와 갱신된 인덱스의 값을 서로 swap해주면 된다.

시간 복잡도는 우선 아래 코드에서 보면 알 수 있지만 O(N^2)이다.

#include <iostream>
#include <cstdio>
 
#define SWAP(a, b){int t = a; a = b; b = t;}
using namespace std;
 
int arr[] = { 5,1, 2, 3,2,1 };
int n = 6;
int cnt;
void print() {
    printf("[[ round :: %d ]]\n", ++cnt);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    for (int i = 0; i < n; i++) {
        print();
        int idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[idx] > arr[j])
                idx = j;
        }
        SWAP(arr[idx], arr[i]);
    }
    print();
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

버블 정렬(Bubble Sort)

버블 정렬은 현재 인덱스와 그다음 인덱스의 값을 비교하여 현재 인덱스 값이 더 크다면 swap해주는 방식을 이용한다.

이때 버블 정렬은 수가 n개 있으면 n - 1번만 하면 된다.

그 이유는 버블 정렬이 한 라운드 실행될 때 마다 가장 마지막 인덱스에는 가장 큰 수가 정렬되게 되기에 최종적으로는 n - 1번만 정렬해주면 된다.

그리고 2중 포문 내부에서는 n - i - 1까지만 돌리면 되는데 그 이유는 n - i - 1는 뒤에서 i번째까지는 정렬되어있으니 i를 빼고 그리고 인덱스가 0부터 시작이기에 -1을 빼주는 것이다. 

시간 복잡도는 우선 아래 코드에서 보면 알 수 있지만 O(N^2)이다.

#include <iostream>
#include <cstdio>
#include <algorithm>
 
#define SWAP(a, b){int t = a; a = b; b = t;}
using namespace std;
 
int arr[] = { 5,1, 2, 3,2,1 };
int n = 6;
int cnt;
void print() {
    printf("[[ round :: %d ]]\n", ++cnt);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    for (int i = 0; i < n - 1; i++) {
        print();
        for (int j = 0; j < (n - i) - 1; j++)
            if (arr[j] > arr[j + 1])
                SWAP(arr[j], arr[j + 1]);
    }
    print();
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>