Sorting(정렬) 종류와 특징

Bubble, Counting, Selection, Insertion, Quick, Merge, Heap 정렬이 있다.

목표

• 정렬의 종류를 알아본다.
• 각 정렬별 특징을 배운다.
• Big-O notation
• 코드로 구현해보기

1. Bubble Sort (버블 정렬)

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식.

정렬 과정

1. 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝 자리까지 이동
2. 한 단계가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리에 위치함

코드

C++ 구현

	
#include<iostream>
using namespace std;

int main(){
    freopen("input.txt", "rt", stdin);
    int n, arr[101], tmp;
    cin>>n;

    for(int i = 0; i < n; i++){
        cin>>arr[i];
    }

    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - i - 1; j++){
            if(arr[j] > arr[j + 1]){    //오름차순
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    for(int i = 0; i < n; i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

시간복잡도

O(n^2)

참고동영상

버블소팅

2. Counting Sort (카운팅 정렬)

항목들의 순서를 결정하기 위해 집합에서 각 항목이 몇개씩 있는지 카운팅 하여, 선형 시간에 정렬하는 효율적인 알고리즘

제한사항

• 정수 혹은 정수로 표현 가능한 자료에 대해서만 적용 가능
  • 각 항목의 갯수를 카운팅 하기 위해, 정수 항목으로 인덱싱 되는 카운트들의 Array(배열)을 사용하기 때문임
• 카운트들을 위한 충분한 공간을 확보하기 위해서 집합 내의 가장 큰 정수를 알아야 함

정렬과정

1. 카운팅 배열을 하나 만든다. 입력데이터에 들어있는 숫자들이 몇개씩 들어 있는지 카운팅해야 하기 때문

예제

코드

시간복잡도

O(n + k) n은 항목의 갯수, k는 정수의 최대값

3. Selection Sort (선택 정렬)

• 배열의 처음 값을 기준으로 배열의 나머지 부분의 최소값(min value)을 찾아 처음 부분과 교환하면서 정렬.
• 2중 for문을 돌면서 배열의 최소값의 index(j)를 기억하고 있다가 처음 값(i)이랑 바꿈.
• 맨앞은 정렬되어 가면서 진행.

시간복잡도

O(n^2)

정렬과정

1. 주어진 배열에서 가장 처음(i = 0)을 select
2. select된 부분을 제외한 나머지 배열값 중에서 for문을 돌면서 최소값을 찾음, index를 기억.
3. 최소 값이 select한 값과 비교해서 크거나 작다면(desc, asc) select한 값과 교환
4. 맨 처음 위치를 제외한(처음위치는 증가) 나머지 리스트를 대상으로 반복.

예제 코드

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

int main(){
    //input exemple : {6 13 5 11 7 23 15}
    //freopen("input.txt", "rt", stdin);
    int n, min, tmp = 0;
    cin>>n;
    vector<int> v(n);

    for(int i = 0; i < n; i++){		//입력
        cin>>v[i];
    }

    for(int i = 0; i < n - 1; i++){
        min = i;	// 1. 처음 선택
        for(int j = i + 1; j < n; j++){
            if(v[j] < v[min]){		// 2.핵심
                 min = j;
            }
        }
        // swap(v[i], v[min]);		//3. 교환
        tmp = v[i];
        v[i] = v[min];
        v[min] = tmp;
    }

    for(int i = 0; i < n; i++){
        cout<<v[i]<<" ";
    }

    return 0;
}

선택정렬

4. Insertion Sort (삽입 정렬)

• 배열의 1부터 시작해서 N - 1까지 탐색을 할때, 기준값보다 작은 것이 있다면 지금까지 지나온 배열값들과 비교하면서 내려간다.
• 이때 배열을 밀어주면서 내려간다.
• 약간 버블쏘트 역순느낌이랄까..
• 배열값의 이동이 많다.

정렬 과정 (오름차순기준, ASC)

1. 2중포문으로 해결, i = 1부터 시작하며 이 비교기준값을 tmp에 저장한다.
2. i 인덱스보다 한칸 작은, 바로 직전의 값부터 0번째까지 쭉 내려가면서 비교.
3. 만약에 tmp 보다 큰 값이 있다면 밀어넣는다. 이런식으로 쭉 내려간다.

코드

//Insertion Sort
#include<iostream>
using namespace std;

int main(){
    int n, arr[101], tmp = 0, i, j;
    cin>>n;

    for(int i = 0; i < n; i++){
        cin>>arr[i];
    }

    for(i = 1; i < n; i++){
        tmp = arr[i];
        for(j = i - 1; j >= 0; j--){
            if(arr[j] > tmp){
                arr[j + 1] = arr[j];
            }else break;
        }
        arr[j + 1] = tmp;
    }

    for(int i = 0; i < n; i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

시간복잡도

O(n^2)

5. Quick Sort (퀵 정렬)

정렬 과정

코드

시간복잡도

퀵정렬

6. Merge Sort (병합 정렬)

Divide and Conquer Algorithm의 대표적인 예 작은 단위로 분할하여 로직에 맞게 merge 해나가는 자료구조.

머지 소트는 Divide and Conquer(분할정복) Algorithm의 대표적인 예제 이다. 크게 2가지 스텝으로 이뤄져 있다.

1) N개의 부분으로 나눠지게끔 지속적으로 작은 단위로 쪼개고(Divide) N개의 부분 각각은 길이가 1이여야 한다. 즉, 길게 늘어선 배열을 쪼개서 길이가 1일 떄까지 계속 쪼갠다는 뜯.

2) 모든 요소가 하나의 배열로 Merge(병합) 될 때까지 쪼개진 하위항목들을 조건(오름차순, 내림차순)에 맞게 Conquer(정복, 합쳐서) 새롭게 정렬된 하위 항목을 만든다.

좀 더 자세히 알아보자.

정렬 과정

• 분할(Devide) 1) 현제 입력받은 배열을 반으로 쪼갠다. mid를 계산한다(배열 시작 index + 마지막 index를 사용)/2. 2) 이를 배열의 길이가 0 이거나 1일 때까지 반복한다.

• 합병(Merge) 1) 코드

시간복잡도 최악/최선 모든 경우에도 O(nlogn) 하지만, QuickSort의 최악의 경우인 O(n^2) 보다 성능이 떨어지는데 이는 추가적인 메모리(O(n))를 요구하기 때문이기도 하고, 퀵소트가 Locality of Reference(메모리 지역 참조성) 때문이기도 하다.

공간복잡도 O(n)의 추가적인 메모리를 필요로 한다. 하지만 Linked List(연결리스트) 경우에는 O(1)의 추가 공간만 필요함.

머지소트

7. Heap Sort (힙 정렬)

최대/최소 값을 빠르게 찾도록 만들어진 자료구조이다. Priority Queue를 Heap으로 구현 가능

Heap(힙) 이란?

• 최대, 최소 값을 빠르게 찾도록 만들어진 자료구조이다.
• 전체 자료를 정렬할 때 보다 가장 큰/작은 값 몇개만 필요할 때 가장 유용함.
• 완전 이진 트리 구조의 자료구조 이다.
• Heap을 사용해 우선순위 큐를 구현할 수 있다. (그 외, Sorted Linked List, Array / Unsorted LL, Array 도 가능)

• 힙 트리에서는 중복을 허용한다(Binary Search Tree 에서는 중복 혀용 X)

• Max Heap(최대 힙)
  • 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
• Min Heap(최소 힙)
  • 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
• Unstable 하지만 최악의 경우에도 최적의 성능보장, 추가메모리 X
• 배열을 사용해 힙을 구현

시간복잡도

O(nlogn)

Heap Tree의 level(depth)가 거의 ㅣog2n(완전 이진트리) 이므로 삽입/삭제 할 때 걸리는 시간이 log2n만큼 걸림. Tree의 Node수가 N개 임으로 전체적으로 O(nlogn)인 거임.

Quick Sort 와 Merge Sort 랑 같은 시간복잡도를 가진다. 하지만 MergeSort 와는 다르게 추가적인 메모리가 필요 없고 QuickSort와 다르게 최악의 경우 n^2의 성능보다 안정적이다.

정렬 과정

• 1차원 배열로 구현 할 수 있다.
• 절렬이 안된 요소들을 1차원 배열에 담아둔 뒤 Max Heap Insert(push?)를 통해 차례로 삽입
• Max Heap 으로 구성된 배열에서 최대값부터 삭제하면 내림차순 max heap이 된다.

힙은 완전 이진트리이므로 삽입시에는 가장 마지막 노드 위치에, 추출시에는 루트가 삭제.

루트 노드의 인덱스를 i 라고 했을때, 왼쪽 자식 노드는 i*2, 오른쪽은 i*2 + 1 이고, 부모 노드는 자식노드 index 값을 i 라고 했을때 i / 2 이므로 부모와 자식에 대한 접근 연산이 단순 나눗셈, 덧셈으로 구현되어 접근이 편하다.

물론 이 경우 root 노트의 index 값은 1부터 시작합니다. 0부터 시작하는 경우는 부모와 자식에 대한 연산의 값이 조금 달라질 수 있습니다. 그러나 1부터 시작하는 경우의 장점은, 왼쪽 자식에 대한 접근이 곱하기 2로, 부모에 대한 접근이 나누기 2로 표현되므로 시프트 연산으로 구현할 수 있다는 점입니다.

• 최대 힙 삽입(Max Heap Insert)
  1. 기존 Heap에 새로운 값(노드)가 들어오면 배열 마지막에 삽입한다.
  2. 새로운 노드가 들어오면 부모 노드들과 비교하여 트리를 거슬러 올라가면서 교환 하든 말든 한다.
• 최대 힙 삭제(Max Heap Delete)
  1. 최대값을 반환해야 함으로 root 노드를 삭제
  2. 삭제된 root node 자리에 마지막 노드를 가져와서 대체한다
  3. tree를 내려가며 비교하면서 힙을 재구성 한다.

코드

처음에 max-heap으로 전체를 max-heap으로 만든 다음, max 값을 추출(O(logn))함으로써 구현 GeekforGeek code 참조함.

	#include <iostream> 
	using namespace std; 

	// To heapify a subtree rooted with node 'root' which is 
	// an index in arr[]. 'n' is size of heap 
	// heap을 구성하기를 heapify라 부름
	void heapify(int arr[], int n, int root) 
	{ 
		int largest = root; // Initialize largest as root 
		int left = 2*root + 1; // or left = (i + 1)*2 - 1 
		int right = 2*root + 2; // or right = (i + 1)*2 

		// If left child is larger than root 
		if (left < n && arr[left] > arr[largest]) 
			largest = left; 

		// If right child is larger than largest so far 
		if (right < n && arr[right] > arr[largest]) 
			largest = right; 

		// If largest is not root 
		if (largest != root) 
		{ 
			swap(arr[root], arr[largest]); 

			// Recursively heapify the affected sub-tree 
			heapify(arr, n, largest); 
		} 
	} 

	// main function to do heap sort 
	void heapSort(int arr[], int n) 
	{ 
		// Build heap (rearrange array) 
		for (int i = n / 2 - 1; i >= 0; i--) 
			heapify(arr, n, i); 

		// One by one extract an element from heap 
		for (int i=n-1; i>=0; i--) 
		{ 
			// Move current root to end 
			swap(arr[0], arr[i]); 

			// call max heapify on the reduced heap 
			heapify(arr, i, 0); 
		} 
	} 

	/* A utility function to print array of size n */
	void printArray(int arr[], int n) 
	{ 
		for (int i=0; i<n; ++i) 
			cout << arr[i] << " "; 
		cout << "\n"; 
	} 

	// Driver program 
	int main() 
	{ 
		int arr[] = {12, 11, 13, 5, 6, 7}; 
		int n = sizeof(arr)/sizeof(arr[0]); 

		heapSort(arr, n); 

		cout << "Sorted array is \n"; 
		printArray(arr, n); 
	} 

Big-O Notation(빅오표기법)

참고 동영상

big-o표기법 빅오 한글 빅오 영문 빅오 영문

참고 블로그

https://www.geeksforgeeks.org/heap-sort/ https://blog.weirdx.io/post/3126 https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html https://medium.com/@george.seif94/a-tour-of-the-top-5-sorting-algorithms-with-python-code-43ea9aa02889 https://hsp1116.tistory.com/33 https://unikys.tistory.com/357