written by yechoi

기수 정렬 자릿수를 기준으로 차례대로 데이터를 정렬하는 알고리즘 1의 자리수를 기준으로 오름차순으로 정렬 그 데이터를 다시 10의 자리수를 기준으로 오름차순으로 정렬 ... 반복 정렬하는 법 bucket[10] 에 자리수 별로 count 함. 19이면 bucket[9]++ 이런 식. 이 버켓을 누적함. bucket[i + 1] = bucket[i] + bucket[i + 1] 뒷 숫자부터 버켓에 담긴 인덱스 대로 집어 넣음. 맨 뒷 숫자가 37이고, bucket[7]이 3이라면 세번째 배열(result[2])에 넣는 것. 결과물 배열을 다시 원 배열에 복사 이 과정을 반복 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간 복잡도 #define MAX 10000 void radixSort(int *a, ..

퀵 정렬 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법 편향된 분할이 발생할 때 연산의 양이 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..