본문으로 바로가기

[AL] 1. 정렬 알고리즘

category CS/Algorithm 2019. 3. 5. 01:29
1_정렬 알고리즘

1. 정렬 알고리즘 (Sorting Algorithm)

  1. 기본 개념
  2. Selection Sort
  3. Bubble Sort
  4. Insertion Sort
  5. Quick Sort
  6. Merge Sort
  7. Heap Sort

 

1. 기본 개념

1.1. 안정성 (Stability)

  • 같은 키 값을 가지는 레코드의 상대적인 위치가 유지되면 안정적(Stable) 이라고함
  • ex) 이름 순으로 정렬된 학생 리스트를 성적 순으로 정렬할 때, 성적이 같은 학생들의 순서가 그대로 보존되면 안정적임

 

1.2. 제자리 (In Place)

  • 입력 배열 이외의 추가 기억장소의 수가 상수 개를 넘지 않음

 

 

2. Selection Sort

n개의 원소를 가진 배열을 정렬할 때, 계속해서 교환하는 것이 아니라 비교하고 있는 값의 index를 저장해둔다. 그리고 최종적으로 한번만 교환을 수행한다.

 

2.1. 특징

  • 실행시간은 입력 순서에 민감 X
  • 안정적 X , 제자리 O
Space ComplexityTime Complexity (최선)Time Complexity (평균)Time Complexity (최악)
O(1)O(N^2)O(N^2)O(N^2)

 

2.2. 소스코드 (C++)

#include <iostream>
#define SIZE 10
using namespace std;

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

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

void selectionSort(){
    for(int i=0; i<SIZE-1; i++){
        int index = i;
        
        for(int j=i+1; j<SIZE; j++){
            if(arr[index] > arr[j]){
                index = j;
            }
        }
        
        // Swap
        int tmp = arr[i];
        arr[i] = arr[index];
        arr[index] = tmp;
    }
}

int main(int argc, const char * argv[]) {
    // 정렬 전
    printArr();
    
    // 선택 정렬
    selectionSort();
    
    // 정렬 후
    printArr();
    
    return 0;
}

 

 

3. Bubble Sort

n개의 원소를 가진 배열을 정렬할 때, 인접한 두 개의 데이터를 비교&교환 하면서 정렬을 진행하는 방식이다.

 

3.1. 특징

  • Reverse Sorted File 의 경우 최악
  • 안정적 O , 제자리 O
Space ComplexityTime Complexity (최선)Time Complexity (평균)Time Complexity (최악)
O(1)O(N^2)O(N^2)O(N^2)

 

3.2. 소스코드 (C++)

#include <iostream>
#define SIZE 10
using namespace std;

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

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

void bubbleSort(){
    for(int i=SIZE-1; i>=1; i--){
        for(int j=0; j<i; j++){
            if(arr[j] > arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // 정렬 전
    printArr();
    
    // 버블 정렬
    bubbleSort();
    
    // 정렬 후
    printArr();
    
    return 0;
}

 

 

4. Insertion Sort

n개의 원소를 가진 배열을 정렬할 때, 2번째 인덱스부터 마지막 인덱스까지 피봇으로 설정한다. 피봇값을 이전의 노드와 비교하여 피봇이 더 작다면 교환을 수행한다. 이 과정을 마지막 인덱스까지 반복해준다.

 

4.1. 특징

  • Almost Sorted File 의 경우 가장 유리함
  • 안정적 O , 제자리 O
Space ComplexityTime Complexity (최선)Time Complexity (평균)Time Complexity (최악)
O(1)O(N)O(N^2)O(N^2)

 

4.2. 소스코드 (C++)

#include <iostream>
#define SIZE 10
using namespace std;

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

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

void insertionSort(){
    for(int i=1; i<SIZE; i++){
        int index = i;
        
        while(1){
            if(arr[index-1] > arr[index]){
                int tmp = arr[index-1];
                arr[index-1] = arr[index];
                arr[index] = tmp;
                index--;
            }else{
                break;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // 정렬 전
    printArr();
    
    // 삽입 정렬
    insertionSort();
    
    // 정렬 후
    printArr();
    
    return 0;
}

 

 

5. Quick Sort

Sorting 기법 중, 가장 빠르다고 알려졌지만 Worst Case 에서는 O(n^2) 의 시간복잡도를 가진다.

Quick Sort 역시 Divede-and-Conquer 방식으로 정렬이 이루어진다. Devide 과정에서 pivot 이라는 개념이 사용된다.

또한 Merge Sort 가 균등한 분할 방식이라면, Quick Sort 는 비균등한 분할 방식이다.

pivot 을 기준으로 좌측은 pivot 보다 작은 값, 우측은 pivot 보다 큰 값이 위치도록 Partition 된다. 이렇게 나뉜 좌, 우측을 다시 재귀적으로 Quick Sort 를 시키면 또 partition 과정이 적용된다. 이 때, 이 과정에서 pivot 으로 설정된 값은 다음 재귀과정에 포함시키지 않도록 주의해야한다. pivot 은 이미 정렬된 위치를 찾았기 때문이다.

 

5.1. 특징

  • 안정적 X , 제자리 O
  • dummy key 필요
Space ComplexityTime Complexity (최선)Time Complexity (평균)Time Complexity (최악)
O(1)O(NlogN)O(NlogN)O(N^2)

 

5.2. 소스코드 (C++)

먼저 마지막 값을 피봇으로 설정한다. 그런 다음, LEFT 와 RIGHT 값을 조건에 맞게 탐색한다.

LEFT 는 PIVOT 보다 큰 값을 만날 때 까지, 우측으로 이동한다.

RIGHT 는 PIVOT 보다 작은 값을 만날 때 까지, 좌측으로 이동한다.

LEFT, RIGHT 모두 조건에 맞는 값을 발견했으면 이 두 값을 교환 한다.

LEFT index ≥ RIGHT inex 의 상황이 온다면 Pivot 값과 LEFT 값을 교환해준뒤, 다시 피봇을 설정하여 위의 과정을 반복한다.

#include <iostream>
#define SIZE 10
using namespace std;

int partition(int *arr,int l,int r){
    int p = arr[r];
    int i = l - 1;
    int j = r;
    
    while(1){
        do { i++; } while(arr[i] < p);
        do { j--; } while(arr[j] > p);
        
        if(i >= j) break;
        
        // i - j 교환
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    // i - p 교환
    int tmp = arr[i];
    arr[i] = arr[r];
    arr[r] = tmp;
    
    return i;
}

void QuickSort(int *arr,int l,int r){
    if(r > l){
        int pivot = partition(arr,l,r);
        QuickSort(arr, l, pivot-1);
        QuickSort(arr, pivot+1, r);
    }
}

void printArr(int *arr){
    for(int i=1; i<=SIZE; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cout << "----------[Quick Sort]----------\n";
    int arr[SIZE+1] = {0,6,2,8,1,3,9,4,5,10,7};
    
    cout << " [정렬 전] : ";
    printArr(arr);
    
    QuickSort(arr,1,SIZE);
    
    cout << " [정렬 후] : ";
    printArr(arr);
    
    cout << "--------------------------------\n";
    return 0;
}

 

 

6. Merge Sort

Divide-and-Conquer 방식의 정복 방법이다.

Merge Sort 는 전체 원소를 하나의 단위로 분할한 후, 분할한 원소를 다시 병합하는 정렬 방식이다.

병합시 Sorting 과정을 살펴보면, 우선 병합하려고 하는 크기의 메모리를 할당한 다음, 두 개의 원소에 대해 각각을 비교하여 할당된 메모리에 집어 넣는 방식이다.

 

6.1. 특징

  • 안정적 O , 제자리 X
Space ComplexityTime Complexity (최선)Time Complexity (평균)Time Complexity (최악)
O(N)O(NlogN)O(NlogN)O(NlogN)

 

6.2. 소스코드 (C++)

#include <iostream>
#define SIZE 10
using namespace std;

void Merge(int *arr,int l,int r,int m){
    int tmp[SIZE+1];
    
    int i = l;
    int j = m+1;
    int k = l;
    
    // 추가 배열에 정렬
    while(i<=m && j<=r){
        if(arr[i] < arr[j]){
            tmp[k] = arr[i++];
        }else{
            tmp[k] = arr[j++];
        }
        k++;
    }
    
    // 나머지 넣기
    if(i>m){
        for(int p=j; p<=r; p++){
            tmp[k++] = arr[p];
        }
    }else{
        for(int p=i; p<=m; p++){
            tmp[k++] = arr[p];
        }
    }
    
    // 추가 배열 → 원래 배열
    for(int p=l; p<=r; p++){
        arr[p] = tmp[p];
    }
}

void MergeSort(int *arr,int l,int r){
    if(r > l){
        int m = (l+r) / 2;
        
        MergeSort(arr, l, m);
        MergeSort(arr, m+1, r);
        Merge(arr,l,r,m);
    }
}

void printArr(int *arr){
    for(int i=1; i<=SIZE; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cout << "----------[Merge Sort]----------\n";
    int arr[SIZE+1] = {0,6,2,8,1,3,9,4,5,10,7};
    
    cout << " [정렬 전] : ";
    printArr(arr);
    
    MergeSort(arr,1,SIZE);
    
    cout << " [정렬 후] : ";
    printArr(arr);
    
    cout << "--------------------------------\n";
    return 0;
}

 

 

7. Heap Sort

최대힙(부모노드의 키값이 자식노드보다 큼) 또는 최소힙(부모노드의 키값이 자식노드보다 작음) 를 구성해 정렬하는 방법이다.

내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소힙을 구성해야 한다.

 

7.1. 특징

  • 안정적 X , 제자리 O
Space ComplexityTime Complexity (최선)Time Complexity (평균)Time Complexity (최악)
O(1)O(NlogN)O(NlogN)O(NlogN)

 

7.2. 소스코드 (C++)

#include <iostream>
#define SIZE 10
using namespace std;

void swap(int *arr,int a,int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void heapify(int *arr,int h,int m){
    int v = arr[h];
    
    int i;
    for(i=2*h; i<=m; i*=2){
        if(i < m && arr[i] < arr[i+1]) i++;
        
        if(v >= arr[i]) break;
        else arr[i/2] = arr[i];
    }
    
    arr[i/2] = v;
}

void heapSort(int *arr,int len){
    for(int i=len/2; i>=1; i--){
        heapify(arr, i, len);
    }
    for(int i=len; i>=1; i--){
        swap(arr,1,i);
        heapify(arr, 1, i-1);
    }
}

void printArr(int *arr){
    for(int i=1; i<=SIZE; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cout << "----------[Heap Sort]----------\n";
    int arr[SIZE+1] = {0,6,2,8,1,3,9,4,5,10,7};
    
    cout << " [정렬 전] : ";
    printArr(arr);
    
    heapSort(arr,SIZE);
    
    cout << " [정렬 후] : ";
    printArr(arr);
    
    cout << "--------------------------------\n";
    return 0;
}

 

 

 

테스트 소스코드

#include <iostream>
#define SIZE 10
using namespace std;

void swap(int *arr,int a,int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void printArr(int *arr){
    for(int i=1; i<=SIZE; i++){
        cout << arr[i] << " ";
    }
    cout << "\n";
}

void SelectionSort(int *arr){
    for(int i=1; i<SIZE; i++){
        for(int j=i+1; j<=SIZE; j++){
            if(arr[i] > arr[j])
                swap(arr,i,j);
        }
    }
}

void BubbleSort(int *arr){
    for(int i=SIZE; i>1; i--){
        for(int j=1; j<i; j++){
            if(arr[j] > arr[j+1])
                swap(arr,j,j+1);
        }
    }
}

void InsertionSort(int *arr){
    for(int i=2; i<=SIZE; i++){
        int j = i;
        while(1){
            if(arr[j] < arr[j-1]){
                swap(arr,j,j-1);
                j--;
            }else{
                break;
            }
        }
    }
}

// Merge Sort
void Merge(int *arr,int l,int r,int m){
    int tmp[SIZE+1];
    
    int i = l;
    int j = m + 1;
    int k = l;
    
    while(i<=m && j<=r){
        if(arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    
    if(i > m){
        for(int p=j; p<=r; p++){
            tmp[k++] = arr[p];
        }
    }else{
        for(int p=i; p<=m; p++){
            tmp[k++] = arr[p];
        }
    }
    
    for(int p=l; p<=r; p++){
        arr[p] = tmp[p];
    }
}

void MergeSort(int *arr,int l,int r){
    if(l < r){
        int m = (l+r) / 2;
        
        MergeSort(arr, l, m);
        MergeSort(arr, m+1, r);
        Merge(arr, l, r, m);
    }
}

// Quick Sort
int partition(int *arr,int l,int r){
    int p = arr[r];
    int i = l-1;
    int j = r;
    
    while(1){
        do { i++; } while(arr[i] < p);
        do { j--; } while(arr[j] > p);
        
        if(i >= j) break;
        
        swap(arr,i,j);
    }
    swap(arr,i,r);
    
    return i;
}

void QuickSort(int *arr,int l,int r){
    if(l < r){
        int pivot = partition(arr, l, r);
        
        QuickSort(arr, l, pivot-1);
        QuickSort(arr, pivot+1, r);
    }
}

// Heap Sort
void Heapify(int *arr,int h,int m){
    int v = arr[h];
    
    int i;
    for(i=h*2; i<=m; i*=2){
        if(i<m && arr[i]<arr[i+1]) i++;
        
        if(arr[i] <= v) break;
        else arr[i/2] = arr[i];
    }
    
    arr[i/2] = v;
    
    return ;
}

void HeapSort(int *arr,int len){
    for(int i=len/2; i>=1; i--){
        Heapify(arr,i,len);
    }
    for(int i=len; i>=1; i--){
        swap(arr,1,i);
        Heapify(arr,1,i-1);
    }
}

void sorting(int kind){
    int arr[SIZE+1] = {0,6,2,8,1,3,9,4,5,10,7};
    
    switch (kind) {
        case 1:{
            // MergeSort
            cout << "--------[Selection Sort]--------\n";
            cout << " [정렬 전] : ";
            printArr(arr);
            
            SelectionSort(arr);
            
            cout << " [정렬 후] : ";
            printArr(arr);
            
            cout << "--------------------------------\n\n";
        }break;
            
        case 2:{
            // QuickSort
            cout << "----------[Bubble Sort]---------\n";
            cout << " [정렬 전] : ";
            printArr(arr);
            
            BubbleSort(arr);
            
            cout << " [정렬 후] : ";
            printArr(arr);
            
            cout << "--------------------------------\n\n";
        }break;
            
        case 3:{
            // MergeSort
            cout << "--------[Insertion Sort]--------\n";
            cout << " [정렬 전] : ";
            printArr(arr);
            
            InsertionSort(arr);
            
            cout << " [정렬 후] : ";
            printArr(arr);
            
            cout << "--------------------------------\n\n";
        }break;
        case 4:{
            // MergeSort
            cout << "----------[Merge Sort]----------\n";
            cout << " [정렬 전] : ";
            printArr(arr);
            
            MergeSort(arr,1,SIZE);
            
            cout << " [정렬 후] : ";
            printArr(arr);
            
            cout << "--------------------------------\n\n";
        }break;
            
        case 5:{
            // QuickSort
            cout << "----------[Quick Sort]----------\n";
            cout << " [정렬 전] : ";
            printArr(arr);
            
            QuickSort(arr,1,SIZE);
            
            cout << " [정렬 후] : ";
            printArr(arr);
            
            cout << "--------------------------------\n\n";
        }break;
            
        case 6:{
            // MergeSort
            cout << "----------[Heap Sort]-----------\n";
            cout << " [정렬 전] : ";
            printArr(arr);
            
            HeapSort(arr,SIZE);
            
            cout << " [정렬 후] : ";
            printArr(arr);
            
            cout << "--------------------------------\n\n";
        }break;
            
        default:
            break;
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    for(int i=1; i<=6; i++){
        sorting(i);
    }
    
    return 0;
}

결과

--------[Selection Sort]--------
 [정렬 전] : 6 2 8 1 3 9 4 5 10 7 
 [정렬 후] : 1 2 3 4 5 6 7 8 9 10 
--------------------------------

----------[Bubble Sort]---------
 [정렬 전] : 6 2 8 1 3 9 4 5 10 7 
 [정렬 후] : 1 2 3 4 5 6 7 8 9 10 
--------------------------------

--------[Insertion Sort]--------
 [정렬 전] : 6 2 8 1 3 9 4 5 10 7 
 [정렬 후] : 1 2 3 4 5 6 7 8 9 10 
--------------------------------

----------[Merge Sort]----------
 [정렬 전] : 6 2 8 1 3 9 4 5 10 7 
 [정렬 후] : 1 2 3 4 5 6 7 8 9 10 
--------------------------------

----------[Quick Sort]----------
 [정렬 전] : 6 2 8 1 3 9 4 5 10 7 
 [정렬 후] : 1 2 3 4 5 6 7 8 9 10 
--------------------------------

----------[Heap Sort]-----------
 [정렬 전] : 6 2 8 1 3 9 4 5 10 7 
 [정렬 후] : 1 2 3 4 5 6 7 8 9 10 
--------------------------------

Program ended with exit code: 0

 

저작자표시

'CS > Algorithm' 카테고리의 다른 글

[AL] 6. Union-Find 알고리즘  (0) 2019.04.05
[AL] 5. 자료구조 (Heap, Hash)  (0) 2019.04.01
[AL] 4. 자료구조 (Graph)  (0) 2019.04.01
[AL] 3. 자료구조 (Linked List, Stack, Queue)  (0) 2019.03.28
[AL] 2. 자료구조 (Tree)  (0) 2019.03.11
댓글 , 엮인글
SuperM
블로그 이미지 슈퍼마리호 님의 블로그
MENU
CATEGORY
VISITOR 오늘 / 전체

티스토리툴바