[Algorithm] Sort(Selection, Insertion, Bubble)

🚗 Selection Sort

선택 정렬을 데이터 중 가장 작은 값의 데이터를 선택하여 앞으로 보내는 정렬이다.

Selection Sort is a sort that selects the data with the smallest value and sends it forward.

 

Time complexity

$ = N + (N-1) + (n-2) + ... + 2 + 1  $

$ = \frac{N(N+1)}{2}\  $

$ = N * N $

$ = O(N^2) $

 

Best  : $N(O^2)$

Average : $N(O^2)$

Worst : $N(O^2)$

 

 

 

 

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        swap(arr[min_idx], arr[i]);
    }
}

 

 

 

🚓 Insertion Sort

삽입 정렬은 데이터를 순서대로 뽑아서 적절한 위치를 찾아 삽입함으로써 완성하는 정렬이다.

Insertion sort is a sort that is completed by extracting data in order and inserting it at an appropriate location.

 

쉽게 설명하자면 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하여 정렬을 완성한다.

Simply, sorting is completed by comparing all elements of the data array with the already sorted part of the array, finding their positions, and inserting them.

 

Time complexity

각 요소에 대해 자신의 이전의 모든 요소와 비교해야 한다.

Each element must be compared to all elements before it.

 

$ = 1 + 2 + ... (N-1) $

$ = \frac{(N-1)N}{2}\ $

$ = N * N $

$ = O(N^2) $

 

Best(Already Sorted) : $O(N)$ 

Average : $O(N^2)$

Worst : $O(N^2)$

 

 

#include <iostream>
using namespace std;

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

 

 

 

 

 

🚕 Bubble Sort

버블 정렬은 인접한 요소를 반복적으로 비교하고 필요한 경우 스왑하여 완성하는 정렬이다.

Buble sort is a sort that is completed by repeatedly compairing adjacent elements and swapping them if necessary.

 

Time complexity

각 요소에 대해 이전의 모든 요소와 비교해야 한다.

For each element, it must be compared to all previous elements.

 

Best : $O(N^2)$ 

Average : $O(N^2)$

Worst : $O(N^2)$

 

 

 

#include <iostream>
using namespace std;

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

}

 

 

 

🛺 QuickSort

퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다.

Quick sort is a sorting algorithm that uses divde and conquer and recursion.

 

퀵 정렬은 피봇이라는 개념을 사용한다.

Quick sort uses the concept of pivot.

 

피봇이란 쉽게말해서 정렬 될 기준 원소를 뜻한다.

Simply, pivot means the reference element to be sorted.

 

피봇을 어떻게 선택하냐에 따라 퀵 정렬의 성능이 달라진다.

The performance of quick sort varies depending on how you choose the pivot.

 

하지만 최적의 피봇을 선택하는것은 어렵기 때문에 임의로 선택을 하게되며 보통 배열의 처음, 중앙, 마지막 값을 선택한다.

However, because it is difficult to select the optimal pivot, it is chosen arbitarily, usually selecting the first, midle, and last values of the array.

 

Best : $O(NlogN)$ 

Average : $O(NlogN)$

Worst : $O(N^2)$

 

아래는 배열을 첫 원소를 피봇으로 선택하여 퀵 소트를 진행하는 예시다.

Below is an example of performing quicksort by selecting the first element of the array as the pivot

 

PIVOT : 밑줄 

LOW : 빨간색

HIGH : 파란색

 

 

 

 

 

 

🚙 HeapSort

힙 정렬을 이해하기 전 자료구조 힙에 대해 알아야 한다.

Before understanding heap sort, you must know about the data structure heap.

 

힙은 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조다.

A heap is type of complete binary tree and is a data structure created for a priority queue.

 

큐는 먼저 들어오는 데이터가 먼저 나가는 FIFO 형식의 자료구조인데, 우선순위 큐는 먼저 들어오는 데이터가 아니라 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조다.

A queue is a FIFO type data structure in which the data that comes in first goes out first, and a priority queue is a data structure in which the data with the highest priority goes out first, not the data thata comes in first.

 

그래서 부모노드와 서브트리간의 대소 관계가 성립되게 된다.

Therefore, the size relationship between the parent node and the subtree is established.

 

힙의 종류는 "최대 힙"과 "최소 힙"으로 나누어진다.

Heap types are divided into "max heap" and "min heap".

 

- 최대 힙(max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

A complete binary tree where the key values of the parent node are greater than or equal to the key values of the child nodes.

 

- 최소 힙(min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

A complet binary tree where the key values of the parent node are smaller than or equal to the key values of the child nodes.

 

 

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

In other words, when sorting a heap, a max heap can be configured for descending sorting, and a min heap cna be configured for ascending sorting.

 

힙 트리의 전체 높이가 거의 $\log_2n$이므로 하나의 요소를 힙에 삽입하거나 삭제할 떄 힙을 재정비 하는 시간이 $\log_2n$만큼 소요된다.

Since the total height of the heap tre is aprroximately $\log_2n$, it takes $\log_2n$ time to reorganize the heap when inserting or deleting one element from the heap. 

 

요소의 개수가 n개이므로 전체적으로 $O(n\log_2n)$의 시간이 걸린다.

Since there are n elements, it takes $O(n\log_2n)$ overall.

 

 

최대 힙의 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.

 

2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

 

ex) 최대 힙에 새로운 요소 8을 삽입

 

 

 

최대 힙의 삭제

최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.

 

삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.

 

힙을 재구성한다.

 

ex) 루트 노드 9를 삭제.

 

 

힘 정렬을 실행할 때 3 2 5 7 9 10 1 6 4 8 라는 배열을 정렬한다고 해보자.

 

 

 

 

정렬이 완료된 이후 해당 배열의 가장 마지막 배열의 값과 0번째 인덱스의 값을 변경한 뒤 힙 정렬을 진행할 배열의 크기를 1 줄여준다.

 

그리고 무한반복

 

이를 코드로 나타내면 아래와 같다.

 

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


void heapify(int arr[], int len, int root){
    int largest = root; 
    int left = 2*root + 1;
    int right = 2*root + 2;

    if(left < len && arr[left] > arr[largest]){
        largest = left;
    }
    if(right < len && arr[right] > arr[largest]){
        largest = right;
    }
    if(largest != root){
        swap(arr[root], arr[largest]);
        heapify(arr, len, largest);
    }
}


void heapSort(int arr[], int n){
    for(int i=n/2-1; i>=0; i--){
        heapify(arr, n, i);
    }
    for(int i=n-1; i>0; i--){
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

 

 

힙 정렬에서 아래의 링크를 참고하였습니다.

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

[알고리즘] 힙 정렬(heap sort)이란 - Heee's Development Blog

 

 

🚌Merge Sort

병합 정렬 또한 대표적인 분할 정복 방법을 사용한 알고리즘이다.

Merge sort is also a representative algorithm that uses the divde and conquer method.

 

병합 정렬은 정확히 반으로 나누고 나중에 정렬하는 방법인데, 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택한다.

Merge sort is a method of dividing the problem in half and sorting it later, it splits a large problem into two smaller problems, calculates them seperately, and then combines them later.

 

 

 

 

 

 

7 6 5 8 3 5 9 1 을 합병정렬을 이용하여 정렬을 진행해보겠다.

 

 

 

위와 같이 i와 j 를 비교하여 k에 넣은 뒤 각각을 한 칸씩 이동시켜주면서 정렬하는 과정을 반복한다.

 

이를 코드로 구현하면 아래와 같다.

 

 

#include <iostream>
using namespace std;


int sorted[100000];

void merge(int arr[], int left, int right){
    int middle = (left + right) / 2;
    int i = left, j = middle + 1, k = left;

    while(i <= middle && j <= right){
        if(arr[i] <= arr[j]){
            sorted[k++] = arr[i++];
        }else{
            sorted[k++] = arr[j++];
        }
    }

    // 먼저 끝까지 도달하는 경우 나머지도 다 넣어줘야 함
    if(i > middle){
        for(int l = j; l <= right; l++){
            sorted[k++] = arr[l];
        }
    } else {
        for(int l = i; l <= middle; l++){
            sorted[k++] = arr[l];
        }
    }

    // 정렬된 배열을 삽입
    for(int l = left; l <= right; l++){
        arr[l] = sorted[l];
    }
}


void mergeSort(int arr[], int left, int right){
    if(left < right){
        int middle = (left + right) / 2;
        mergeSort(arr, left, middle);
        mergeSort(arr, middle+1, right);
        merge(arr, left, right);
    }

}

 

 

 

합병정렬은 아래의 블로그를 참고하였습니다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog