기수 정렬 (Radix Sort)
1. 기수 정렬 Queue를 이용해서 각 자리수 별로 정렬 반복 ※ 기 (radix) : 특정 진수를 나타내는 숫자들 ex ) 10진수의 radix : 0, 1, 2, 3, ....., 8, 9 2진수의 radix : 0, 1 2. 기수 정렬 예제 ex ) 89, 70, 35, 131, 910 오름차순 정리하시오.
2022. 6. 11.
퀵 정렬 (Quick Sort)
1. 퀵 정렬 ▶ 분할정복 알고리즘 input 배열을 반복적으로 분할해서 계산하는 알고리즘이며, 평균 시간복잡도가 O(N*logN) 특정한 값 a을 기준으로 a보다 큰 수, a보다 작은 수를 나누자 ! ※ 특정한 값 a = pivot ※ 일반적으로 첫번째 원소를 pivot 값으로 설정한다. 2. 퀵 정렬 예제 ex ) 3 7 8 1 5 9 6 10 2 4 오름차순 정리하시오. #include int number = 10; int data[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; void show() { for (int i = 0; i < number; i++) { printf("%d ", data[i]); } } void quickSort(int* a, int start,..
2022. 5. 9.
버블 정렬 (Bubble Sort)
1. 버블 정렬 2개씩 비교해서 더 작은 것을 앞으로 자리바꿈 * 세로로 그려 보면, 가장 작은 것이 거품처럼 위로 (=맨 앞으로) 올라가는 형태 [ Algorithm ] 1. for pass = 1 to n-1 2. for i = 1 to n-pass 3. if (A[i-1] > A[i]) // 위의 원소가 아래의 원소보다 크면 4. A[i-1] ↔ A[i] // 자리바꿈 5. return A 2. 버블 정렬 예제 ex ) 1 10 5 8 7 6 4 3 2 9 오름차순 정리하시오. #include int main(void) { int a[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; int n = sizeof(a) / sizeof(int); int temp; for (int i ..
2022. 5. 4.
선택 정렬 (Selection Sort)
1. 선택 정렬 가장 작은 것을 맨 앞으로 가져오자 ! 2. 선택 정렬 예제 ex ) 1 10 5 8 7 6 4 3 2 9 오름차순 정리하시오. #include int main(void) { int a[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; int min, minIdx, temp; int n = sizeof(a) / sizeof(int); for (int i = 0; i < n-1; i++) { min = a[i]; minIdx = i; for (int j = i + 1; j < n; j++) { if (a[j] < min) { min = a[j]; minIdx = j; } } temp = a[i]; a[i] = a[minIdx]; a[minIdx] = temp; } for..
2022. 5. 3.
