정렬(sort)

https://www.toptal.com/developers/sorting-algorithms

정렬 알고리즘 퍼포먼스

 

선택 정렬(Selection Sort)

가장 작은 값을 찾아서 0번 인덱스에, 두번째로 작은 값을 찾아 1번 인덱스에 · · · =>일일히 하나씩 비교하여 가장 작은 값을 선택해서 앞으로 보냄

시간 복잡도 : O(N^2)

#include<iostream>
using namespace std;

int main(void) 
{
	int i, j, min, index, temp;
	int array[6] = { 4,2,7,9,3,1 };
	
	for (i = 0; i < 6; i++) {
		min = array[i];
		index = i;
		for (j = i; j < 6; j++) {
			if (min > array[j]) {
				min = array[j];
				index = j;
			}
		}
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}

	for (i = 0; i < 6; i++) {
		cout << array[i];
	}

	return 0;
}

---

버블 정렬(Bubble Sort)

숫자 오름차순 정렬, 옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보냄

vs 선택정렬 : 선택정렬의 경우 첫번째부터 마지막 -> 두번째부터 마지막 ... 순 

버블 정렬의 경우는 첫번째부터 마지막 -> 첫번째부터 마지막-1 ... 순 ∴ 한 번 반복 시 젤 큰 값이 맨 뒤에 위치

 

ex) 4 2 7 9 3 1

(1) 4 vs 2 더 작은 것 앞으로 => 2 4 7 9 3 1

(2) 4 vs 7 더 작은 것 앞으로 => 2 4 7 9 3 1

(3) 7 vs 9 더 작은 것 앞으로 => 2 4 7 9 3 1

(2) 9 vs 3 더 작은 것 앞으로 => 2 4 7 3 9 1

· · ·

1번 반복 결과 2 4 7 3 1 9

 

가장 비효율적인 알고리즘 , 시간 복잡도 : O(N^2)

#include<iostream>
using namespace std;

int main(void) 
{
	int i, j, temp;
	int array[6] = { 4,2,7,9,3,1 };
	
	for (i = 0; i < 6; i++) {
		for (j = 0; j < 5 - i; j++) {
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}

	for (i = 0; i < 6; i++) {
		cout << array[i];
	}

	return 0;
}

---

삽입 정렬(Insertion Sort)

수를 적절한 위치에 삽입함 (필요할 때만) => 데이터가 이미 거의 정렬된 상태에 한해서 가장 빠른 알고리즘

자신보다 작은 것을 만날 때 그 위치에 삽입함

시간 복잡도 : O(N^2)

 

ex) 4 2 7 1 9 3

4 vs 2 => 4를 한 칸 뒤로 이동시킨 후 빈칸에 2 삽입 -> 2 4 7 1 9 3

1 vs 7 -> 1 vs 4 -> 1 vs 2 => 7, 4, 2 순으로 모두 한 칸 뒤로 이동시킨 후 빈칸에 1 삽입 -> 1 2 4 7 9 3

· · ·

#include<iostream>
using namespace std;

int main(void) 
{
	int i, j, key;
	int array[6] = { 4,2,7,9,3,1 };
	
	//index 0 은 이미 정렬된 것으로 봄
	for (i = 1; i <= 5; i++) {
		j = i;

		key = array[i];

		for (j = i - 1; j >= 0 && array[j] > key; j--) {
			array[j + 1] = array[j]; //오른쪽으로 이동
		}

		array[j + 1] = key;
	}

	for (i = 0; i < 6; i++) {
		cout << array[i];
	}

	return 0;
}

---

#include<iostream>
using namespace std;

int main(void) 
{
	int i, j, temp;
	int array[6] = { 4,2,7,9,3,1 };
	
	for (i = 0; i < 5; i++) { //j=i, j+1 때문에 i<5
		j = i;

		while (j >= 0 && array[j] > array[j + 1]) {
			temp = array[j];
			array[j] = array[j + 1];
			array[j + 1] = temp;
			j--;
		}
	}

	for (i = 0; i < 6; i++) {
		cout << array[i];
	}

	return 0;
}

---

퀵 정렬(Quick Sort)

divide and conquer

시간 복잡도 : O(N*logN)

이미 정렬 되어있는 경우(최악의 경우) 시간 복잡도 : O(N^2)

★Partition★

: pivot(기준값)을 기준으로 pivot보다 작은 값은 왼쪽에 큰 값은 오른쪽에 배치

 

---

병합 정렬(Merge Sort)

divide and conquer

=> divide : 반으로 나눔, conquer : 왼쪽과 오른쪽을 각각 정렬, combine : 정렬된 두개를 하나로 합병

시간 복잡도 : O(N*logN) ->최악의 경우에도 보장

하나의 큰 문제를 두개의 작은 문제로 분할한 뒤 각자 계산하고 나중에 합침(일단 반으로 나누고 나중에 정렬)

=>합치는 순간에 정렬을 수행

 

 

---

힙 정렬(Heap Sort)

힙 트리 구조(heap tree structure) 이용

시간 복잡도 : O(N*logN)

 

※이진 트리(binary tree) : 모든 노드의 자식 노드가 2개 이하인 노드

※완전 이진 트리 : 데이터가 루트(root)노드로 부터 시작하여 자식 노드가 왼쪽자식노드, 오른쪽 자식 노드로 차근차근 들어가는 구조의 이진트리(이진 트리의 노드가 중간에 비어있지 않고 가득 찬 구조)

※힙(heap) : 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리

-> 최대 힙 : 부모노드가 자식노드보다 큰 힙