chaetudy

개요

분할 정복 방법을 통해 리스트를 정렬한다.

피봇을 정한 뒤 피봇의 위치를 확정해 가며 정렬한다.

시간 복잡도

최악의 경우 O(n^2), 평균적으로 O(nlogn)이다.

대부분 컴퓨터 아키텍쳐 설계 상 퀵 소트 내부 루프의 캐시 히트율이 높기 때문에, 일반적인 경우에 시간 복잡도 O(nlogn)인 알고리즘보다 빠르다.

코드

void quick_sort(int* arr, int low, int high) {
	// base condition
	if (low >= high) return;

	// divide
	int i = low, j = low;
	int& pivot = arr[high];
	for (;  j < high; j++) {
		if (arr[j] < pivot) {
			swap(arr[i++], arr[j]);
		}
	}
	swap(arr[i], pivot);

	// conquer
	quick_sort(arr, low, i - 1);
	quick_sort(arr, i + 1, high);
}

ref

공부하면서 많이 도움이 되었던 영상

https://youtu.be/cWH49IKDIiI

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

개요

두 인접한 원소를 정렬해 나간다.

구현은 쉬우나 효율은 좋지 않은 편에 속한다. 대충 이런 정렬이 있구나 하고 알고 넘어가면 된다.

55 07 78 12 42  초기값[파란색은 sorting]
07 55 78 12 42  첫 번째 패스(pass)
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78  두 번째 패스(pass)
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78  세 번째 패스(pass)
07 12 42 55 78  네 번째 패스(pass)
07 12 42 55 78  다섯 번째 패스(pass)
07 12 42 55 78  정렬 끝

시간 복잡도

n-1, n-2, ... 1번을 반복하게 되며 이를 식으로 나타내면 n(n-1)/2이므로, O(n^2)이다.

코드

void bubble_sort(int* p, int size) { 
	for (int i = 0; i < size - 1; i++) { 
		for (int j = 0; j < size - i - 1; j++) { 
			if (p[j] > p[j + 1]) { 
				swap(p[j], p[j + 1]); 
			}
		}
	}
}

ref

https://todaycode.tistory.com/46