[알고리즘] 정렬 Sorting

글의 요약 설명 부분. 

 

 

목차

 

---

SORTING 정렬

정렬(Sorting)이란 정해진 기준에 맞춰 데이터를 정리하는 알고리즘이다. 가장 흔한 예로 오름차순/내림차순 정렬이 있다.

정렬의 궁극적인 목적은 데이터를 빠르고 쉽게 찾을 수 있는 '탐색'에 있다.

 

int main()
{
    vector<int> v{ 1, 5, 3, 4, 2 };
 
    std::sort(v.begin(), v.end());
 
    BubbleSort(v);
    SelectionSort(v);
    InsertionSort(v);
}

int main()
{
    vector<int> v{ 1, 5, 3, 4, 2 };

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

    BubbleSort(v);
    SelectionSort(v);
    InsertionSort(v);
}

---

 

 

 

버블 정렬(Bubble Sort)

 

• (N-1) + (N-2) + ... + 3 + 2 + 1
•  등차수열의 합 = N * (N-1) / 2
•  0(N^2) 시간복잡도

void BubbleSort(vector<int>& v)
{
    const int n = (int)v.size();
 
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < (n - 1 - i); j++)
        {
            if (v[j] > v[j + 1])
            {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
            }
        }
    }
}

---

 

선택 정렬(Selection Sort)

 

• (N-1) + (N-2) + ... + 3 + 2 + 1
•  등차수열의 합 = N * (N-1) / 2
•  0(N^2) 시간복잡도

// [3][J][5][K][9]
// [3][5][9][J][K]
 

void SelectionSort(vector<int>& v)
{
    const int n = (int)v.size();
 
    for (int i = 0; i < n - 1; i++)
    {
        int bestIdx = i;
 
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < v[bestIdx])
                bestIdx = j;    // 가장 작은값을 가지는 인덱스를 bestIdx로 만들어줌
        }
 
        // 교환
        int temp = v[i];
        v[i] = v[bestIdx];
        v[bestIdx] = temp;
    }
}

 

---

 

Insertion Sort 삽입 정렬

0(N^2) 시간복잡도

 

[5][J][9][3][K]

[5]                 [J][9][3][K]
[5][J]             [9][3][K]
[5][9][J]         [3][K]
[3][5][9][J]     [K]
[3][5][9][J][K]

void InsertionSort(vector<int>& v)
{
    const int n = (int)v.size();
 
    // 0(N^2) 시간복잡도
    for (int i = 1; i < n; i++)
    {
        int insertData = v[i];
 
        int j; // 삽입되어야 하는 데이터
        for (j = i - 1; j >= 0; j--)
        {
            if (v[j] > insertData) // 이전 데이터와 비교하여 삽입되는 데이터가 더 크면
                v[j + 1] = v[j];   // 이전 데이터 뒤에 위치해준다
            else                   // 이전 데이터보다 작으면
                break;             // break로 빠져나간다.
        }
 
        v[j + 1] = insertData;
    }
}
 

 

---

 

마무리

버블 < 선택 < 삽입 정렬순으로 더 효율적인 정렬 방식이다. 

하지만 버블, 선택, 삽입 정렬 모두 시간복잡도가 N^2인 정렬 방식이다.

따라서 위의 3가지 정렬 방식은 지양해야 한다. 다른 게시물에 정리된 정렬 방식을 쓰는걸 권장한다.

 

 

 

출처: https://cooervo.github.io/Algorithms-DataStructures-BigONotation/

Big O cheat sheets

 

 

전체 코드

 

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <thread>
using namespace std;
 
// C# 자료구조/알고리즘
// -> A* OpenList (PQ)
// -> C# List = C++ vector
 
// PQ O(logN)
// Red-Black Tree 0(logN)
// Sorting
 
// [3][J][5][K][9]
// [3][5][9][J][K]
 
// 1) 버블 정렬 (Bubble Sort)
void BubbleSort(vector<int>& v)
{
    const int n = (int)v.size();
 
    // (N-1) + (N-2) + ... + 3 + 2 + 1
    // 등차수열의 합 = N * (N-1) / 2
    // 0(N^2) 시간복잡도
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < (n - 1 - i); j++)
        {
            if (v[j] > v[j + 1])
            {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
            }
        }
    }
}
 
// [3][J][5][K][9]
// [3][5][9][J][K]
 
// 2) 선택 정렬 (Selection Sort)
void SelectionSort(vector<int>& v)
{
    const int n = (int)v.size();
 
    // (N-1) + (N-2) + ... + 3 + 2 + 1
    // 등차수열의 합 = N * (N-1) / 2
    // 0(N^2) 시간복잡도
    for (int i = 0; i < n - 1; i++)
    {
        int bestIdx = i;
 
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < v[bestIdx])
                bestIdx = j;        // 가장 작은값을 가지는 인덱스를 bestIdx로 만들어줌
        }
 
        // 교환
        int temp = v[i];
        v[i] = v[bestIdx];
        v[bestIdx] = temp;
    }
}
 
 
// [5][J][9][3][K]
 
// [5]                [J][9][3][K]
// [5][J]            [9][3][K]
// [5][9][J]        [3][K]
// [3][5][9][J]        [K]
// [3][5][9][J][K]
 
// 3) 삽입 정렬 (Insertion Sort)
void InsertionSort(vector<int>& v)
{
    const int n = (int)v.size();
 
    // 0(N^2) 시간복잡도
    for (int i = 1; i < n; i++)
    {
        int insertData = v[i];
 
        int j; // 삽입되어야 하는 데이터
        for (j = i - 1; j >= 0; j--)
        {
            if (v[j] > insertData) // 이전 데이터와 비교하여 삽입되는 데이터가 더 크면
                v[j + 1] = v[j];   // 이전 데이터 뒤에 위치해준다
            else                   // 이전 데이터보다 작으면
                break;             // break로 빠져나간다.
        }
 
        v[j + 1] = insertData;
    }
}
 
 
int main()
{
    vector<int> v{ 1, 5, 3, 4, 2 };
 
    std::sort(v.begin(), v.end());
 
    //BubbleSort(v);
    //SelectionSort(v);
    InsertionSort(v);
}