[알고리즘] 정렬 - (1) 선택정렬, 버블정렬, 삽입정렬

정렬 알고리즘 gif

Selection sort 선택정렬	Θ(n^2)
Bubble sort 버블정렬
Insertion sort 삽입정렬
Quicksort 퀵정렬	최악 Θ(n^2), 평균 Θ(nlog2n)
Merge sort 병합정렬	Θ(nlog2n)
Heap sort 힙정렬	Θ(nlog2n)
Radix sort 기수정렬	Θ(n+k)
Counting sort 계수 정렬	Θ(d(n+k))

Selection Sort 선택정렬

selectionSort(A[], n) // 배열 A[1...n]을 정렬한다. 
{
	for last ← n downto 2 { 
		A[1...last] 중 가장 큰 수 A[k]를 찾는다;
		A[k] ↔ A[last]; // A[k]와 A[last]의 값을 교환 
	}
}

수행 시간은 모든 경우에 Θ(n^2)

Bubble Sort 버블정렬

버블정렬이 이름의 유래는 이번에 찾아보면서 처음 알게되었다
수면으로 올라오는 듯한 모습이라니 느낌 있지 않나요?

bubbleSort(A[], n) ▷ 배열 A[1...n]을 정렬한다. 
{
	for last ← n downto 2 { --------1 
		for i ← 1 to last -1 -----------2
			if (A[i]>A[i+1]) then A[i] ↔ A[i+1]; ▷ 교환 -----3
}

수행시간 Θ(n^2)

Insertion Sort 삽입정렬

insertionSort(A[], n) ▷ 배열 A[1...n]을 정렬한다. 
{
	for i ← 2 to n { -----------------1
		A[1...i]의 적당한 자리에 A[i]를 삽입한다. -------2
}

최악의 경우 Θ(n^2)