정렬 알고리즘 비교

알고리즘	평균 수행시간	최악 수행시간	알고리즘 기법	비고
버블 정렬(Bubble Sort)	O(n^2)	O(n^2)	비교와 교환	코딩이 가장 손쉬움
계수 정렬(Counting Sort)	O(n+k)	O(n+k)	비교환 방식	n이 비교적 작을 때만 가능함
선택 정렬(Selection Sort)	O(n^2)	O(n^2)	비교와 교환	교환의 횟수가 버블, 삽입정렬보다 작음
퀵 정렬(Quick Sort)	O(n long n)	O(n^2)	분할 정복	최악의 경우 O(n^2) 이지만, 평균적으로는 가장 빠름
삽입 정렬(Insertion Sort)	O(n^2)	O(n^2)	비교와 교환	n의 개수가 작을 때 효과적
병합 정렬(Merge Sort)	O(n long n)	O(n long n)	분할 정복	연결리스트의 경우 가장 효율적인 방식

---

버블 정렬(Bubble Sort)

void bubbleSort(int cnt) {
	if (cnt == N) {	// 정렬 끝
		return;
	}
	for (int i = 1; i < N - cnt; i++) {
		if (numbers[i - 1] > numbers[i]) {
			int temp = numbers[i];
			numbers[i] = numbers[i - 1];
			numbers[i - 1] = temp;
		}
	}
	bubbleSort(cnt + 1);
}

---

계수 정렬(Counting Sort)

void countingSort() {
	// 계수
	for (int i = 0; i < N; i++) {
		numbersCnt[numbers[i]]++;
	}
	// 계수 누적
	for (int i = 1; i <= maxN; i++) {
		numbersCnt[i] += numbersCnt[i - 1];
	}
	// 정렬
	for (int i = N - 1; i >= 0; i--) {
		sortedNumbers[numbersCnt[numbers[i]]-1]= numbers[i];
		numbersCnt[numbers[i]]--;
	}
}