목록퀵소트 (1)

written by yechoi

정렬 - 퀵 정렬, 계수 정렬

퀵 정렬 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법 편향된 분할이 발생할 때 연산의 양이 O(N^2) c++의 algorithm 라이브러리에 sort() 함수는 퀵 정렬을 기반으로 하며 O(NlogN)을 보장 void quickSort(int start, int end) { if (start >= end) return ; int key = start; int i = start + 1; int j = end, int temp; while (i j) // 엇갈리지 않았다면 두 값을 서로 바꿔줌 swap(&a[key], &a[j]) else // 엇갈렸으면 피봇값과 작은 값을 바꿔줌 swap(&a[i], &a[j]) } quickSort(start, j - 1); quickSort(j + 1..
Born 2 Code/Data Structure 2020. 10. 15. 12:54
이전 Prev 1 Next 다음