졍's 기술 블로그

힙 정렬(Heap Sort)

병합 정렬(Heap Sort)이나 퀵 정렬(Quick Sort)만큼 빠른 정렬 알고리즘으로 힙 트리 구조(Heap Tree Structure)를 사용하는 정렬 방법

추가적인 배열이 필요하지 않다는 점에서 메모리 측면에서 병합 정렬(Merge Sort)에 비해 효율적이며 항상 O(N*logN)을 보장한다.

이론적으로는 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)보다 더 우위에 있다고 할 수는 있으나, 단순히 속도만 가지고 비교해보면 퀵 정렬(Quick Sort)이 평균적으로 더 빠르기 때문에 힙 정렬(Heap Sort)이 일반적으로 많이 사용되지는 않는다.

트리(Tree)

가지를 뻗어나가는 것 처럼 Data가 서로 연결되어 있는 자료구조

이진 트리(Binary Tree)

컴퓨터 안에서 Data를 표현할 때 데이터를 각 Node에 담은 뒤 Node를 두 개씩 이어붙이는 구조

Root: Tree의 최상단 Node

Leaf: Tree의 최하단 Node

완전 이진 트리(Complete Binary Tree)

Data가 Root Node부터 시작해서 자식 Node가 왼쪽 자식 Node, 오른쪽 자식 Node로 차근차근 뻗어나가는 구조의 이진 트리(Binary Tree)

힙(Heap)

최솟값이나 쵯댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리

최대 힙(Max Heap): 부모 노드가 자식 노드보다 큰 힙

-> 힙 정렬을 하기 위해서는 정렬할 데이터를 힙 구조로 변형해야 한다.

위쪽으로 보았을 때는 최대힙이 형성되어있으나 아래쪽으로보았을 때는 데이터 5를 가지는 노드 때문에 최대힙이 형성되어있지 않은 경우

☞ 해당 노드의 자식 노드 중 자신보다 큰 값과 위치를 변경(힙 생성 알고리즘 이용)

힙 생성 알고리즘(Heapify Algorithm)

특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 변경하는 알고리즘으로 한 번 위치를 바꾼 후 여전히 자식이 존재하는 경우 다시 자식 노드 중에서 더 큰 자식과 자신의 위치를 바꾸는 동작을 수행한다.

특정한 하나의 노드에 대해 수행하는 것으로 해당 하나의 노드를 제외하고는 최대 힙이 구성되어있는 상태가 가정되어 있어야 한다.

힙 생성 알고리즘의 시간 복잡도

데이터의 개수가 N개일 때 노드의 높이는 logN

한 번 자식 노드로 내려갈 때마다 노드의 개수가 2배씩 증가하기 때문에 O(logN)

하지만 실질적으로 비교에 필요한 노드의 개수는 N/2개이므로 결과적으로 시간 복잡도는 O(N)

힙 정렬 Sequence

더보기

순서대로 배열에 저장

 

힙 구조로 변경(상향식)

 

부모노드와 가장 마지막 집합의 노드를 변경

 

가장 마지막 노드를 제외한 노드만 이용해 힙 구조로 변경 + 부모노드와 집합의 가장 마지막 노드 위치 변경 동작 반복

 

결과

Code

#include <iostream>
using namespace std;
#define number 9

int heap[9] = {7, 6, 5, 8, 3, 5, 9, 1, 6};

int main(void){
    // 최대 힙 구조 만들기
    for(int i=1;i<number;i++){
        int c = i;
        do{
            // root: 자기 자신의 부모
            int root = (c - 1) / 2;
            // 부모의 값보다 자식의 값이 크면 두 원소 위치 변경
            if(heap[root] < heap[c]){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }

            // 자식의 부모로 이동해 반복적으로 힙 구조 만들기
            c = root;
        } while(c!=0);
    }

    // 크기를 줄여가며 반복적으로 힙 구성
    for(int i=number - 1;i>=0;i--){
        // root node와 가장 마지막 node의 위치 변경
        int temp = heap[0]; // 0번째 index = root node
        heap[0] = heap[i];
        heap[i] = temp;

        // 다시 최대 힙 구조 만들기
        int root = 0;
        int c = 1;
        do{
            // c: root의 자식
            c = 2 * root + 1;
            // 자식 중에 더 큰 값 찾기
            // 왼쪽과 오른쪽 중 더 큰 값을 c에 담음
            if(heap[c] < heap[c+1] && c < i - 1){
                // 왼쪽 값보다 오른쪽 값이 더 크면 오른쪽 node의 index가 c에 저장됨
                c++;
            }

            // root보다 자식이 더 크면 root와 자식을 교환
            if(heap[root] < heap[c] && c < i){
                int temp = heap[root];
                heap[root] = heap[c];
                heap[c] = temp;
            }
            // c를 root로 이동시켜 반복
            root = c;
        } while(c < i);
    }

    for(int i=0;i<number;i++)
        cout << heap[i] << ' ';
    return 0;
}

출력

1 3 5 5 6 6 7 8 9

시간 복잡도

항상 O(N*logN)의 시간 복잡도를 보장한다.

C++ 언어의 경우 훌륭한 정렬 관련 Library가 존재한다.

기본 사용법

Code - 기본

#include <iostream>
#include <algorithm> // sort()는 algorithm library에 포함되어있음
using namespace std;

int main(void){
    int a[10] = {4, 7, 6, 2, 1, 5, 8, 10, 3, 9};
    sort(a, a+10); // 정렬할 배열의 메모리 주소, 정렬할 마지막 원소의 메모리 주소
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

Code - 정렬할 기준 정하는 방식

#include <iostream>
#include <algorithm>
using namespace std;

// 오름차순 정렬
bool comp_up(int a, int b){ // true, false를 기준으로 정렬 기준을 판단
    return a < b; // a가 b보다 작으면 정렬
}

// 내림차순 정렬
bool comp_down(int a, int b){
    return a > b; // a가 b보다 크면 정렬
}

int main(void){
    int a[10] = {4, 7, 6, 2, 1, 5, 8, 10, 3, 9};
    sort(a, a+10, comp_up);
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    sort(a, a+10, comp_down);
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

출력

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

Code - Data를 묶어서 정렬

#include <iostream>
#include <algorithm>
using namespace std;

// class: 하나의 객체를 정의함으로써 여러 개의 변수를 정의
// 일종의 새로운 자료형
class Student{
public:
    string name;
    int score;
    // 생성자: 특정 객체 초기화
    Student(string name, int score){
        this->name = name;
        this->score = score;
    }
    // 정렬 기준: 점수가 낮은 순서
    bool operator <(Student &student){
        return this->score < student.score;
    }
};

bool compare(int a, int b){
    return a > b;
}

int main(void){
    // 5명의 학생
    Student students[] = {
        Student("student1", 90),
        Student("student2", 80),
        Student("student3", 79),
        Student("student4", 66),
        Student("student5", 78)
    };
    sort(students, students+5); // 이미 Class 안에 정렬 기준을 정의해두었으니 변수의 이름만 넣어주면 됨
    for(int i=0;i<5;i++)
        cout << students[i].name << " ";
    cout << endl;
    return 0;
}

출력

student4 student5 student3 student2 student1

Code - Pair library를 이용한 정렬

#include <iostream>
#include <algorithm>
#include <vector> // 연결리스트 형태로 표현되는 자료구조
using namespace std;

int main(void){
    // 한 쌍의 데이터를 묶어서 사용할 수 있는 library
    // 기본적으로 first, second 인자를 가짐
    vector<pair<int, string>> v;
    v.push_back(pair<int, string> (90, "student1"));
    v.push_back(pair<int, string> (79, "student2"));
    v.push_back(pair<int, string> (88, "student3"));
    v.push_back(pair<int, string> (69, "student4"));
    v.push_back(pair<int, string> (95, "student5"));

    sort(v.begin(), v.end());

    for(int i=0;i<v.size();i++){
        cout << v[i].second << ' ';
    }
    return 0;
}

출력

student4 student2 student3 student1 student5

Code - 정렬 기준을 명시하는 Pair 사용

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool comp(pair<string, pair<int, int>> a,
          pair<string, pair<int, int>> b){
    // 성적이 같으면 생년월일이 더 느린 학생이 높은 우선순위 가짐
    if(a.second.first == b.second.first)
        return a.second.second > b.second.second;
    // 성적이 다르면 성적이 더 높은 학생이 높은 우선순위 가짐
    else
        return a.second.first > b.second.first;
}

int main(void){
    vector<pair<string, pair<int, int>>> v;
    v.push_back(pair<string, pair<int, int>> ("student1", pair<int, int>(90, 970416)));
    v.push_back(pair<string, pair<int, int>> ("student2", pair<int, int>(87, 990722)));
    v.push_back(pair<string, pair<int, int>> ("student3", pair<int, int>(93, 891130)));
    v.push_back(pair<string, pair<int, int>> ("student4", pair<int, int>(87, 920631)));
    v.push_back(pair<string, pair<int, int>> ("student5", pair<int, int>(84, 950718)));

    sort(v.begin(), v.end(), comp);

    for(int i=0;i<=v.size();i++)
        cout << v[i].first << ' ';
    return 0;
}

출력

student3 student1 student2 student4 student5

병합 정렬

: 대표적인 분할 정복 방법을 채택한 알고리즘으로 O(NlogN)의 시간 복잡도를 가지는 정렬 알고리즘

특징

-. 일단 반으로 정확히 나누고 나중에 합치는 방식으로, 퀵 정렬(Quick Sort)와 다르게 Pivot 값이 존재하지 않는다.

-. 기존 데이터를 담을 추가적인 배열이 필요하다는 점에서 메모리 활용은 비효율적이다.

-. 초기 단계에는 모두 원소가 1인 상태로 분할되어있으며, 한 번 병합할 때마다 2의 배수만큼 씩 병합한다.

-. 너비는 N이지만 높이는 logN이기 때문에 전체 시간 복잡도는 NlogN이다.

더보기

너비? 높이?

너비: i와 j를 비교해 더 작은 값을 k 위치에 저장

        N번의 시도 후 정렬 완료

높이: 너비 정렬을 총 logN 번 반복하면 정렬 완료

병합 정렬(Merge Sort) Sequence

더보기

코드

#include <iostream>
using namespace std;
#define number 8

int sorted[8]; // 정렬된 배열. 반드시 전역 변수로 선언.

void merge(int a[], int m, int middle, int n){
    // m: 정렬할 배열의 시작 지점
    // middle: 정렬할 배열의 중간 지점
    // n: 정렬할 배열의 끝 지점

    int i = m;
    int j = middle+1;
    int k = m;

    // 작은 순서대로 배열에 삽입
    while(i<=middle && j <= n){
        // i가 j보다 더 작으면 새로운 배열에 저장
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        }
        // 그렇지 않으면 j 값 저장
        else{
            sorted[k] = a[j];
            j++;
        }
        k++; // 한 번 저장하면 k 증가
    }

    // 남은 데이터 삽입
    // i가 먼저 끝났다면 j 모두 새로운 배열에 저장
    if(i > middle){
        for(int t = j; t <= n; t++){
            sorted[k] = a[t];
            k++;
        }
    }
    // j가 먼저 끝났으면 i 모두 새로운 배열에 저장
    else{
        for(int t = i;t<=middle;t++){
            sorted[k] = a[t];
            k++;
        }
    }

    // 정렬된 배열을 실제 배열에 삽입
    for(int t = m; t <= n; t++){
        a[t] = sorted[t];
    }
}

void merge_sort(int a[], int m, int n){
    // 크기가 1보다 큰 경우 return
    if(m < n){
        int middle = (m+n) / 2;
        merge_sort(a, m, middle); // middle을 기준으로 왼쪽 병합정렬
        merge_sort(a, middle+1, n); // middle을 기준으로 오른쪽 병합정렬
        merge(a, m, middle, n); // 정렬 후 합치기
    }
}

int main(void){
    int arr[number] = {7, 6, 5, 8, 3, 5, 9, 1};
    merge_sort(arr, 0, number-1);
    for(int i=0;i<number;i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

출력

1 3 5 5 6 7 8 9

시간 복잡도

병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 NlogN을 보장한다.

☞ 퀵 정렬이 가지는 한계(Pivot 값에 따라 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가짐)를 보완할 수 있음.

백준 사이트

초심자라면 단계별로 풀어보기, 알고리즘 분류에서 문제 풀어보는 게 좋다.

그 중에서도 단계별로 풀어보기에서 정렬해보기부터 시작하면 좋다.

기본적으로 1초에 1억 번 정도 연산한다고 생각하고 문제 풀면 됨.

1. 수 정렬하기(2750)

https://www.acmicpc.net/problem/2750

데이터의 개수가 최대 1,000개. N^2 = 1,000,000개

N^2 알고리즘으로 풀어도 크게 문제 없이 해결 가능하다.

#include <iostream>
using namespace std;

void Print(int *data, int N){
    for(int i=0;i<N;i++)
        cout << data[i] << endl;
}

void Selection_Sort(int *data, int N){
    int tmp, min, idx = 0;
    for(int i=0;i<N;i++){
        min = 1001;
        for(int j=i;j<N;j++){
            if(min > data[j]){
                min = data[j];
                idx = j;
            }
        }

        tmp = data[i];
        data[i] = data[idx];
        data[idx] = tmp;
    }
}

void Bubble_Sort(int *data, int N){
    int tmp = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(data[j] > data[j+1]){
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

int main(void){
    int N;
    int data[1000];

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> data[i];

    Selection_Sort(data, N);
    Bubble_Sort(data, N);
    //Insert_Sort(data, N);
    //Quick_Sort(data, N);
    Print(data, N);
    return 0;
}

2. 세수정렬

https://www.acmicpc.net/problem/2752

#include <iostream>
using namespace std;
#define N 3

int arr[3]={0,};

void Input(){
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << " ";
}

void Insertion_Sort(){
    int j, tmp;
    for(int i=0;i<N-1;i++){
        j = i;
        while(arr[j] > arr[j+1]){
            tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            j--;
        }
    }
}

int main(void){

    Input();
    //Selection_Sort();
    Insertion_Sort();
    Output();

    return 0;
}

3. 수 정렬하기 2

https://www.acmicpc.net/problem/2751

#include <iostream>
using namespace std;

int N;
int arr[1000000+10];

void Input(){
    cin >> N;
    for(int i=0;i<N;i++)
        cin >> arr[i];
}

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << "\n";
}

void Quick_Sort(int start, int end){
    
    if(start >= end)
        return;

    int mid = start;
    int i = start+1;
    int j = end;
    int tmp;

    while(i <= j){
        // 오른쪽으로 가면서 pivot값보다 큰 값 찾기
        while(arr[mid] >= arr[i]){
            i++;
        }

        // 왼쪽으로 가면서 pivot값보다 작은 값 찾기
        while(arr[mid] <= arr[j] && start < j){
            j--;
        }

        // 엇갈렸으면 pivot 값과 작은 값 변경
        if(i > j){
            tmp = arr[j];
            arr[j] = arr[mid];
            arr[mid] = tmp;
        }
        // 엇갈리지 않았으면 두 값 변경
        else{
            tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = arr[j];
        }
    }

    // start, end 다시 조정해 재귀
    Quick_Sort(start, j-1);
    Quick_Sort(j+1, end);
}

int main(void){
    Input();
    Quick_Sort(0, N-1);
    Output();
}

선택 정렬, 버블 정렬, 삽입 정렬의 한계

: O(N*N)은 데이터 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘이다.

2^10 = 1,000

2^20 = 1,000,000

log(2)N = (N이 1,000,000일 때) 20

퀵 정렬(Quick Sort)

: 대표적인 분할 정복 알고리즘으로 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 후 배열을 반으로 나누는 정렬 알고리즘

퀵 정렬(Quick Sort) Sequence

더보기

기준값 = 피벗(Pivot)

왼쪽에서 오른쪽으로 이동하면서 Pivot 보다 큰 값 하나 선택

오른 쪽에서 왼쪽으로 이동하면서 Pivot보다 작은 값 하나 선택

작은 값의 index < 큰 값의 index: Pivot과 작은 값 교환

작은 값의 index > 큰 값의 index: 작은 값과 큰 값 교환

 

Code

#include <iostream>
using namespace std;

int number = 10;
int Data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void quickSort_up(int *data, int start, int end){
    // start: 정렬을 수행하는 부분집합의 첫 번째 원소
    // end: 정렬을 수행하는 부분집합의 마지막 원소

    // 원소가 1개인 경우
    if(start >= end){
        return;
    }

    int key = start; // pivot

    int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
    int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
    int tmp;

    // 엇갈리는 경우 while 탈출
    while(i <= j){
        // i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
        while(data[i] <= data[key]){
            i++;
        }

        // j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
        // index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
        while(data[j] >= data[key] && j > start){
            j--;
        }

        // 엇갈린 경우 pivot값과 현재 data 변경
        if(i > j){
            tmp = data[j];
            data[j] = data[key];
            data[key] = tmp;
        }
        // 엇갈리지 않은 경우 i와 j index의 data 변경
        else{
            tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }

    // 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
    quickSort_up(data, start, j-1); // 왼쪽 data
    quickSort_up(data, j+1, end); // 오른쪽 data
}

void quickSort_down(int *data, int start, int end){
    // start: 정렬을 수행하는 부분집합의 첫 번째 원소
    // end: 정렬을 수행하는 부분집합의 마지막 원소

    // 원소가 1개인 경우
    if(start >= end){
        return;
    }

    int key = start; // pivot

    int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
    int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
    int tmp;

    // 엇갈리는 경우 while 탈출
    while(i <= j){
        // i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
        while(data[i] >= data[key]){
            i++;
        }

        // j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
        // index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
        while(data[j] <= data[key] && j > start){
            j--;
        }

        // 엇갈린 경우 pivot값과 현재 data 변경
        if(i > j){
            tmp = data[j];
            data[j] = data[key];
            data[key] = tmp;
        }
        // 엇갈리지 않은 경우 i와 j index의 data 변경
        else{
            tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }

    // 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
    quickSort_down(data, start, j-1); // 왼쪽 data
    quickSort_down(data, j+1, end); // 오른쪽 data
}

int main(void){
    quickSort_up(Data, 0, number-1); // 오름차순
    for(int i=0;i<10;i++){
        cout << Data[i] << " ";
    }
    cout << endl;
    quickSort_down(Data, 0, number-1); // 내림차순
    for(int i=0;i<10;i++){
        cout << Data[i] << " ";
    }
    return 0;
}

출력

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

만약 아래 배열을 정렬한다면?

선택 정렬의 시간 복잡도: N^2 = 100

퀵 정렬의 시간 복잡도: 

1 2 3 4 5 => 5 * 5 = 25

6 7 8 9 10 => 5 * 5 = 25

-> 25 + 25 = 50

∴ O(NlogN)의 시간복잡도를 갖는 알고리즘을 이용하면 100만개 정도의 데이터는 어렵지 않게 정렬이 가능하다.

시간복잡도

평균 : N*logN

최악의 경우: N^2

만약 이미 오름차순 정렬되어있는 배열을 퀵정렬을 이용해 오름차순 정렬한다면?

=> 분할 정복의 이점을 사용하지 못하고 있으므로, 이런 경우에는 insertion sort를 사용하는 게 효율적이다.

삽입 정렬(Insertion Sort)

: 각 숫자를 적절한 위치에 삽입하는 정렬 방법으로, 정렬 대상 숫자를 기준으로 앞의 원소들은 이미 정렬이 되어 있다고 가정한다.

적절한 위치?
선택 정렬(Selection Sort)와 버블 정렬(Bubble Sort)은 무조건 위치를 변경하는 정렬 방식으로, 이미 정렬이 이루어져 있는 상황에서도 반드시 반복을 수행한다.
반면에, 삽입 정렬(Insertion Sort)은 필요할 때만 위치를 변경한다.

Insertion Sort Sequence

더보기

코드

#include <iostream>
using namespace std;

int main(void){
    int i, j, tmp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<9;i++){
        j = i;
        while(arr[j] > arr[j+1]){
            tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            j--;
        }
    }

    for(i=0;i<10;i++)
        cout << arr[i] << " ";
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도 

최악의 경우 : 10 + 9 + 8 + 7 + ... + 1

=> O(N*N)

Insertion Sort(삽입 정렬)은 특정 조건에서는 속도가 빠르다.

더보기

특정 조건?

만약 Insertion Sort(삽입 정렬)을 이용해 아래 배열을 정렬한다면?

→ 거의 정렬된 상태의 배열의 경우 효율적인 정렬 알고리즘으로, 자원 소모가 적으며 연산 자체도 적게 수행한다.
    (= Quick Sort / Heap Sort / Merge Sort와 비슷하거나 더 빠르게 정렬 수행)

∴ Insertion Sort(삽입 정렬)는 O(N^2)의 시간 복잡도를 가지는 정렬 알고리즘 중 가장 강력한 알고리즘이다.

 

 

버블 정렬(Bubble Sort)

: 옆에 있는 값과 비교해 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법

버블 정렬 Sequence

더보기

한 번 반복이 끝났을 때 가장 큰 값이 가장 마지막 위치로 이동

코드

#include <iostream>
using namespace std;

int main(void){
    int i, j, tmp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        for(j=0;j<9-i;j++){ // i for문이 1번 반복될 때마다 가장 마지막 위치의 원소는 채워지기 때문에 idx 9-i까지만 확인
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

    for(i=0;i<10;i++){
        cout << arr[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 1) / 2

= N * (N - 1) / 2

= O(N^2)

실제로 실행시켜보면 Bubble Sort가 Selection Sort보다 더 느리게 작동한다.
: Bubble Sort는 당장 옆에 있는 것과 비교해 자리를 바꾸는 연산을 수행하며, 자리를 바꾸는 연산은 총 3번의 연산을 필요로 하기 때문에 컴퓨터가 실질적으로 수행해야하는 명령어가 더 많기 때문이다.
반면에 선택 정렬은 가장 작은 수를 찾아 마지막에 한 번만 자리를 바꾸는 연산을 수행한다.

참고로, 정렬 알고리즘 중 가장 느린 건 Bubble Sort이다.

선택 정렬(Selection sort)

: 가장 작은 것을 선택해서 가장 앞으로 보내는 알고리즘

코드

#include <iostream>
using namespace std;

int main(void){
    // 선택 정렬: 가장 작은 것을 선택해서 가장 앞으로 보내자
    int i, j, min, idx, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        min = 9999;
        for(j=i;j<10;j++){
            if(min > array[j]){
                min = array[j];
                idx = j;
            }
        }
        tmp = array[i];
        array[i] = array[idx];
        array[idx] = tmp;
        cout << array[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 9) / 2

=> N * (N - 1) / 2

∴ O(N^2)