목차
정렬 종류
비교 기반 정렬(Comparison Based Sorts)
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort
계수 정렬(Counting Sort)
개념
- non-comparison 기반 정렬에서 가장 간단한 정렬 방법입니다.
- 주어진 값의 범위가 한정적일 때 유용한 방법입니다. 주어진 값의 범위에 대한 count 배열을 생성해 줍니다. 그 후 해당 count 배열을 앞에서부터 누적합을 계산해 줍니다. 이럴 경우 이제 배열에서 특정값에 대한 시작 인덱스를 확인할 수 있습니다. 자세한 내용은 아래 참고
- 시간복잡도는 O(n+k)로 값의 범위(k)(최댓값과 최솟값의 차이)가 작으면 일반적인 정렬 방법인 O(nlogn) 보다 빠를 수 있습니다.
코드
- counting sort
-
def counting_sort(arr): shift = min(arr) K = max(arr) - shift + 1 counts = [0 for _ in range(K)] for item in arr: counts[item - shift] += 1 starting_index = 0 for i, count in enumerate(counts): counts[i] = starting_index starting_index += count sorted_arr = [0 for _ in range(len(arr))] for item in arr: sorted_arr[counts[item - shift]] = item counts[item - shift] += 1 return sorted_arr arr = [7, 3, 2, 5, 6, 10, 9, 8, 1] arr = counting_sort(arr) print(arr)
-
출처
'Computer Science > 자료구조(Data Structure)' 카테고리의 다른 글
[자료구조] 버킷 정렬(Bucket Sort) (0) | 2024.04.17 |
---|---|
[자료구조] 기수 정렬(Radix Sort) (0) | 2024.04.17 |
[자료구조] 퀵 정렬(Quick Sort) (0) | 2024.04.17 |
[자료구조] 병합 정렬(Merge Sort) (0) | 2024.04.16 |
[자료구조] 힙 정렬(Heap Sort) (0) | 2024.04.16 |