[알고리즘] 정렬 (Sort) - 선택, 버블, 삽입, 합병, 퀵, 힙 정렬

1. 선택정렬 (Selection Sort)

첫 번째 자료를 두 번째 자료부터 끝까지 비교하여 가장 작은 값을 첫 번째로 놓고, 두 번째 자료를 세 번째 자료부터 끝가지 비교하여 가장 작은 값을 두 번째로 놓는 과정을 반복하여 정렬하는 방식

void SelectionSort(int arr[], int MAX) {
    int i, j;
    int min, temp;
 
    for (i = 0; i < MAX - 1; i++) {
        min = i;
        for (j = i + 1; j < MAX; j++) {
            if (arr[j] < arr[min]) min = j;
        }
 
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

void BubbleSort(int arr[], int MAX) {
    int i, j, temp;
 
    for (i = MAX-1; i > 0; i--) {
        for (j = 0; j < i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

3. 삽입정렬 (Insertion Sort)

두 번째 자료부터 시작하여 그 전 자료들과 비교하여 삽입위치를 지정하는 방식

void InsertionSort(int arr[], int MAX) {
    int i, j, temp;
 
    for (i = 1; i < MAX; i++) {
        temp = arr[i];
 
        for (j = i - 1; j >= 0 && arr[j]>temp; j--) {
            arr[j + 1] = arr[j];
        }
 
        arr[j + 1] = temp;
    }
}

 

4. 합병 정렬(Merge Sort)

하나의 리스트를 두 개의 균등한 크기로 분할 후 그 부분 리스트들을 정렬 한 후, 그 부분 리스트들을 다시 결합하여 정렬하는 방식

int sort[8]; // 임시 배열
 
// 결합
void Merge(int arr[], int left, int mid, int right) {
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;
 
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])
            sort[k++] = arr[i++];
        else
            sort[k++] = arr[j++];
    }
 
    // 오른쪽 리스트가 남았을 때
    if (i > mid) {
        for (l = j; l <= right; l++)
            sort[k++] = arr[l];
    }
    // 왼쪽 리스트가 남았을 때
    else {
        for (l = i; l <= mid; l++)
            sort[k++] = arr[l];
    }
 
    for (l = left; l <= right; l++) {
        arr[l] = sort[l];
    }
}
// 배열, 배열의 시작, 배열의 끝
void MergeSort(int arr[], int left, int right) {
    int mid;
 
    if (left < right) {
        mid = (left + right) / 2; // 중간위치
        MergeSort(arr, left, mid); // 앞쪽
        MergeSort(arr, mid + 1, right); // 뒤쪽
        Merge(arr, left, mid, right); // 다시 합치기
    }
}

 

5. 퀵 정렬(Quick Sort)

하나의 기준점(Pivot)을 잡고 Pivot의 앞에는 그보다 작은 자료들로, Pivot의 뒤에는 그보다 큰 자료들이 오도록 교환하여 두개의 리스트로 분할 후 그 분할된 리스트에 계속 반복하여 정리하는 방식

void QuickSort(int arr[], int start, int end) {
    int pivot = arr[start]; // 기준점을 시작점으로 잡음
    int left = start + 1;
    int right = end;
    int temp;
 
    while (left <= right) {
        while (arr[left] < pivot) {
            left++;
        } // 왼쪽부터 기준점보다 클때까지
        while (arr[right] > pivot) {
            right--;
        } // 오른쪽부터 기준점보다 작을때까지
 
        if (left <= right) {
            temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    } // 둘이 엇갈릴 때 까지
 
    if (start < end) {
        temp = arr[right];
        arr[right] = arr[start];
        arr[start] = temp;
 
        QuickSort(arr, start, right - 1);  //앞 리스트
        QuickSort(arr, right + 1, end);    //뒷 리스트
    } 
}

6. 힙 정렬(Heap Sort)

자료구조 힙(Heap)을 이용하여 정렬하는 방식

여기선 우선순위큐를 활용함

 

#include <iostream>
#include <queue>
using namespace std;
 
void HeapSort(int arr[],int MAX) {
    priority_queue<int, vector<int>, greater<int>> a;
    // 오름차순으로 나타나게함
 
    for (int i = 0; i < MAX; i++) {
      a.push(arr[i]); 
    }
 
    for (int i = 0; i < MAX; i++) {
        arr[i] = a.top();
        a.pop();
    }
}
 
 
int main() {
    int MAX = 5;
    int* arr =new int[MAX] { 1,3,2,4,5 };
 
    HeapSort(arr,MAX);
 
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << endl;
    }
 
}