본문 바로가기

파이썬 알고리즘/정렬 알고리즘

 (3)
기수 정렬 (Radix Sort) 기수 정렬 (Radix Sort) 제한적인 범위 내에 있는 숫자(ex. 주민등록번호, 학번, 계좌번호)에 대해서 각 자릿수 별로 정렬하는 알고리즘 기(radix) : 특정 진수를 나타내는 숫자들 10진수의 기 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 2진수의 기 : 0, 1 LSD 기수 정렬 Least Significant Digit(LSD) 기수 정렬 1의 자리부터 k자리로 정렬 수행 RL(Right-to-Left) 기수 정렬이라고도 함 MSD 기수 정렬 Most Significant Digit(MSD) 기수 정렬 k자리부터 1의 자리로 정렬 수행 LR(Left-to-Right) 기수 정렬이라고도 함 # LSD(RL) 기수 정렬 from collections import deque def..
힙 정렬 (Heap Sort) 이진 힙 (Binary Heap) 힙 조건(각 노드의 우선순위가 자식 노드의 우선 수위보다 높음)을 만족하는 완전 이진트리 최대 힙(Maximum Heap) : 가장 큰 값을 루트에 저장 최소 힙(minimum Heap) : 가장 작은 값을 루트에 저장 힙에서 부모와 자식 관계 A[i]의 왼쪽 자식 = A[2i] A[i]의 오른쪽 자식 = A[2i+1] A[i]의 부모 = A[i/2] (i가 홀수면 i/2에서 정수 부분만) 힙 정렬 (Heap Sort) 정렬할 입력으로 최대 힙을 만들어 가장 큰 수가 저장되어 있는 루트와 힙의 가장 마지막 노드를 교환(가장 큰 수를 배열의 맨 뒤로 옮김) 힙 크기를 1개 줄인 후 위배된 힙 조건을 해결하여 다시 힙 정렬 수행 루트 90과 힙의 마지막 노드 40을 바꾼 후..
쉘 정렬 쉘 정렬 삽입 정렬을 이용하여 배열 뒷부분의 작은 숫자를 앞부분으로 빠르게 이동시키고, 동시에 앞부분의 큰 숫자는 뒷부분으로 빠르게 이동시키는 정렬 알고리즘 간격(gap)을 이용 30 60 90 10 40 80 40 20 10 60 50 30 40 90 80 ◼ 간격(gap)이 5인 숫자 그룹 그룹1 : [30, 80, 50] 그룹2 : [60, 40, 30] 그룹3 : [90, 20, 40] 그룹4 : [10, 10, 90] 그룹5 : [40, 60, 80] 각 그룹 별로 삽입 정렬 수행 ▶ 30 30 20 10 40 50 40 40 10 60 80 60 90 90 80 처음보다 비교적 큰 숫자가 뒷부분으로, 작은 숫자가 앞부분으로 이동 그 다음에는 간격을 전에 설정한 것보다 작게 하여 다시 그룹별 삽..

티스토리툴바