정렬

1. Radix Sort?- Radix Sort는 여러 개의 자리수를 가진 정수나 문자열 데이터를 정렬할 때 효과적인 정렬알고리즘.- 숫자를 비교하는 것이 아니라, 자리수를 기준으로 정렬을 수행하며, - 각 자리수의 값을 이용해 한 번에 하나의 자릿수씩 정렬을 반복해 최종적으로 정렬을 완료함.2. Radix Sort의 종류2.1. LSD(Least Significant Digit)- 가장 오른쪽 자리수(일의 자리)부터 왼쪽으로 이동하면서 정렬- 일반적으로 정수를 정렬할 때 많이 사용됨2.2. MSD(Most Significant Digit)- 가장 왼쪽 자리수부터 시작하여 오른쪽으로 이동하면서 정렬- 문자열이나 사전순으로 정렬할 때 주로 사용됨  3. Radix Sort의 알고리즘(LSD 기준)- Rad..

1. Counting Sort?- Counting Sort는 정수로 표현할 수 있는 데이터에 대해 효율적으로 작동하는 O(n) 정렬 알고리즘.- 정렬의 대상이 되는 데이터 값의 범위가 명확할 때 주로 사용.- Counting Sort는 비교 정렬 알고리즘이 아닌 분포 정렬 알고리즘이다.  2. Counting Sort 알고리즘i) 입력 배열과 범위 설정- 주어진 입력 배열이 A라고 하고, 배열의 길이를 n이라고 하자.- 데이터 값은 0 이상 k이하인 양수라고 가정해보자. (이때 k == max(A)) ii) 카운트 배열 초기화- C라는 배열을 만들고, 길이를 k+1로 설정 (또는 max(A) - min(A)로 설정)- C[i]는 입력 배열에서 값이 i인 요소가 몇 번 등장하는지 저장함- C의 초기값은 전..

0. Intro- 7-1에서 우리는 Quicksort를 직접 구현해보았다.- 이번 챕터에선 Quicksort의 시간복잡도를 한번 구해보고자 한다.- 엄밀하게 증명을 통해 구하기 보단, 직관적으로 이해하기 쉽게 알아보고자 한다. 1. Best cases- 최선의 경우 분할할 때 정확히 절반을 계속 나누는 것을 의미한다.- 깊이는 O(logn)이고, 각 순환 호출에서의 비교 연산은 O(n)이다.- 따라서 최선의 상황의 시간복잡도는 O(nlogn)이 된다. 2. Worst Cases- 최악의 경우는 정렬하고자 하는 배열이 오름차순으로 정렬되어 있거나, - 내림차순으로 정렬되어 있는 경우이다.- 깊이는 O(n)이고, 각 순환 호출에서의 비교 연산은 O(n)이므로 - 따라서 최악의 상황의 시간복잡도는 O(n^2)..

0. Intro- 이번 7 챕터에서는 quicksort, 퀵정렬에 대해서 알아보고자 한다. 1. Quicksort(퀵정렬)- quicksort(퀵정렬)은 2-3에서 배웠던 mergesort(병합정렬)과 비슷하다.- divide-and-conquer(분할정복)알고리즘을 이용한다.- 평균적으로 매우 빠른 수행 속도를 보여주기 때문에 quicksort 라고 불린다. 2. Quicksort의 알고리즘 - QuickSort의 핵심은 분할(divide)하는 과정이다. - QuickSort는 배열을 작은 부분으로 쪼개서 정렬하는 방식으로 작동하며, 다음과 같은 과정을 거친다. i) Pivot 선택- 배열에서 임의의 기준이 되는 Pivot 요소를 선택한다.- Pivot을 선택하는 방식은 크게 4가지가 존재한다. a) ..