정렬(1)

정렬

정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다.
정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)가 가능해진다.

정렬 알고리즘은 모든 경우에 최적인 정렬 알고리즘인 없다.
데이터의 초기 상태에 대하여 가장 최적인 정렬 알고리즘을 떠올려야 한다.

이 페이지에서는 여러 정렬 알고리즘 중 선택, 삽입, 버블 정렬에 대해서 공부..

---

• Selection Sort (선택정렬)
• Insertion Sort (삽입정렬)
• Bubble Sort (버블정렬)

---

• Quick Sort (퀵정렬)
• Merge Sort (병합정렬)
• Shell Sort (쉘정렬)
• Heap Sort (힙정렬)

---

• Count Sort (계수 정렬)

---

선택정렬

설명 :

시간 복잡도 :
비교 횟수 : $(n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)$
이동 횟수 : swap() 함수 작업시 3번의 이동 = 3*(n-1)

전체 시간복잡도 : $O(n^2)$

C++로 구현한 선택정렬 :

#include <iostream>

using namespace std;

void showArr(int _arr[], int _size) {
    for (int i = 0; i < _size; i++)
    {
        cout << _arr[i] << " ";
    }
    cout << endl;
    
}

void swap(int _arr[], int a, int b){
    int temp = _arr[a];
    _arr[a] = _arr[b];
    _arr[b] = temp;
}

void selectionSort(int _arr[], int _size) {
    for (int i = 0; i < _size - 1; i++)
    {
        int least = i;
        for (int j = i+1; j < _size; j++)
        {
            if(_arr[least] > _arr[j]){
                least = j;
            }
        }
        swap(_arr, least, i);
        cout << "step " << i+1 << " : ";
        showArr(_arr, _size);
    }
    
}

int main(void) {

    int arr[] = {5, 3, 8, 5, 9, 1, 6, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "[before] : " ;
    showArr(arr, size);

    selectionSort(arr, size);
    
    cout << "[after] : ";
    showArr(arr, size);

    return 0;
}

---

삽입정렬

설명 :

시간 복잡도 :
최선의 경우 $O(n)$ : 이미 정렬되어 있는 경우, 비교 (n-1)번 (외부 루프)
최악의 경우 $O(n^2)$ : 역순으로 정렬되어 있는 경우

전체 시간복잡도 : $O(n^2)$
단, 대부분 정렬되어 있는 리스트를 정렬할 때 $O(n)$으로 매우 효율적이다

C++로 구현한 삽입정렬 :

#include <iostream>

using namespace std;

void showArr(int _arr[], int _size) {
    for (int i = 0; i < _size; i++)
    {
        cout << _arr[i] << " ";
    }
    cout << endl;
    
}

void swap(int _arr[], int a, int b){
    int temp = _arr[a];
    _arr[a] = _arr[b];
    _arr[b] = temp;
}

void insertionSort(int _arr[], int _size) {
    
    int i, j;

    for (i = 1; i < _size; i++)
    {
        int me = _arr[i];
        for (j = i-1; j >= 0; j--)
        {
            if(me < _arr[j]) {
                _arr[j+1] = _arr[j];
            }
            else {
                break;
            }
        }
        _arr[j+1] = me; 
        showArr(_arr, _size);
    }
    
    
}

int main(void) {

    int arr[] = {5, 3, 8, 5, 9, 1, 6, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "[before] : " ;
    showArr(arr, size);

    insertionSort(arr, size);
    
    cout << "[after] : ";
    showArr(arr, size);

    return 0;
}

---

버블정렬

설명 :

시간 복잡도 :
비교 횟수 : 최상, 평균, 최악 모두 일정 ➡️ $O(n^2)$

전체 시간복잡도 : $O(n^2)$

C++로 구현한 버블정렬 :

#include <iostream>

using namespace std;

void showArr(int _arr[], int _size) {
    for (int i = 0; i < _size; i++)
    {
        cout << _arr[i] << " ";
    }
    cout << endl;
    
}

void swap(int _arr[], int a, int b){
    int temp = _arr[a];
    _arr[a] = _arr[b];
    _arr[b] = temp;
}

void bubbleSort(int _arr[], int _size) {
    
    for (int i = 0; i < _size - 1; i++)
    {
        for (int j = 0; j < _size - 1 - i; j++)
        {
            if(_arr[j] > _arr[j+1]) {
                swap(_arr, j, j+1);
            }
        }
        showArr(_arr, _size);
    }
    
    
}

int main(void) {

    int arr[] = {5, 3, 8, 5, 9, 1, 6, 2, 7};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "[before] : " ;
    showArr(arr, size);

    bubbleSort(arr, size);
    
    cout << "[after] : ";
    showArr(arr, size);

    return 0;
}