정렬 정리

Nov 11, 2022

• 정렬 정리
  • 시간 복잡도 $O(n^2)$
    • 버블 정렬 (Bubble Sort)
    • 선택 정렬(Selection Sort)
    • 삽입 정렬(Insertion Sort)
  • 시간 복잡도 $O(n\log n)$
    • 병합 정렬(Merge Sort)
    • 힙 정렬(Heap Sort)
    • 퀵 정렬(Quick Sort)
  • 그외 정렬
    • 셸 정렬(Shell’s Sort) - $O(n^{1.25})$

정렬 정리

정렬 방법	최적	평균	최악	공간 복잡도
선택(selection)	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
버블(bubble)	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(n)$
삽입(insert)	$O(n)$	$O(n^2)$	$O(n^2)$	$O(n^2)$
병합(merge)	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$
퀵(quick)	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(n\log n)$
힙(heap)	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$
쉘(shell)	$O(n^{1.25})$	$O(n^{1.25})$	$O(n^{1.25})$	$O(n)$
계수(counting)	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$

시간 복잡도 $O(n^2)$

버블 정렬 (Bubble Sort)

구현이 쉽다는 것 외에는 아무런 장점이 없는 정렬

이미 정렬된 자료에선 1번만 돌면 되므로 최선의 성능을 보여줌($O(n)$), 따라서 중간에 정렬이 필요한 경우 바로 중단하고 정렬되지 않았음을 알리는데 사용할 수 있다.

BubbleSort(eles[])
	for i = 0 to eles[].length-1
		for j = 0 to i-1
			if eles[j] > eles[j+1]
				swap(ele[j], eles[j+1])
	return eles[]

선택 정렬(Selection Sort)

인간이 무의식적으로 사용하는 정렬 1

보통 버블 정렬 보다 2배 정도 빠르다.

SelectionSort(eles[])
	for i = 0 to eles[].length-2
		index = i
		for j = i + 1 to eles[].length-1
			if eles[index] > eles[j]
				index = j
		swap(eles[index], elses[i])
	return eles[]

삽입 정렬(Insertion Sort)

인간이 무의식적으로 사용하는 정렬 2

• 탐색 이외의 오버헤드가 적어 이미 정렬되어 있는 자료구조에서 자료를 하나씩 삽입, 제거할 때 좋다.
• 배열이 작은 경우에도 밀어내기 부분의 오버헤드가 적으므로 왠만한 알고리즘보다 좋다.

InsertionSort(eles[])
	for i = 1 to eles[].length-1
		j = i - 1
		key = eles[i]
		while eles[j] > key and j >= 0
			eles[j+1] = eles[j]
			j = j -1
		eles[j+1] = key
	return eles[]

좀더 자세한 설명은 알고리즘 성능 분석 참조

시간 복잡도 $O(n\log n)$

병합 정렬(Merge Sort)

병합 정렬

힙 정렬(Heap Sort)

자료구조인 힙을 이용한 정렬

추가적인 메모리가 전혀 필요하지 않고, 언제나 안정적인 $O(n\log n)$ 성능을 가진다.
하지만, 퀵 정렬이 컴퓨터 구조상 캐시 친화적이므로 보통 더 빠르다.

다만, 퀵 정렬은 최악의 상황에는 $O(n^2)$이므로, 추가적인 피봇 선택 알고리즘이 없을 경우 힙 정렬은 최악의 상황을 피할 수 있다.

퀵 정렬(Quick Sort)

보통 최고의 성능을 나타내는 정렬

피봇의 선택에 따라 성능이 크게 달라져, 피봇을 고르는 partition 알고리즘 또한 다양하게 존재한다.

그외 정렬

셸 정렬(Shell’s Sort) - $O(n^{1.25})$

삽입정렬을 띄엄띄엄 먼저 수행한 후, 거의 정렬된 배열을 삽입 정렬로 마무리하는 방식ㅅ