본문 바로가기

정렬 알고리즘2

계수 정렬(Counting sort) 계수 정렬(Counting sort) 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작 정렬 알고리즘 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다. 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행시간 O(N+K)를 보장한다. 계수 정렬 동작 정렬할 데이터: [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 1. 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다 2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 시킨다. 3. 2번의 과정을 모든 데이터에 대해서 반복 한다. 4. 최종적으로 인덱스 별 카운트를 구한다. 원.. 2023. 6. 14.
퀵 정렬 (Quick sort) 퀵정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정 한다. 퀵 정렬이 빠른 이유 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(N㏒N)를 기대할 수 있습니다. 너비 X 높이 = N * ㏒N = N㏒N 퀵 정렬의 시간 복잡도 퀵 정렬은 평균의 경우 O(N㏒N)의 시간 복잡도를 가집니다. 최악의 경우 O(N²)의 시간 복잡도를 가집니다. array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(arr.. 2023. 6. 13.

티스토리툴바