[Python] 정렬을 마친 두 배열을 병합 정렬하기 - merge()
import heapq # heapq 모듈 불러오기 a = [2, 4, 6, 8, 11, 13] b = [1, 2, 3, 4, 9, 16, 21] c = list(heapq.merge(a, b)) # 배열 a와 b를 병합하여 c에 저장 # c == [1, 2, 2, 3, 4, 4, 6, 8, 9, 11, 13, 16, 21] 만약 정렬되지 않은 두 배열 a, b를 병합 정렬해야 한다면 sorted(a + b)를 사용하여야 한다. 그러나 배열 a, b가 모두 정렬되어 있으므로 heapq 모듈의 merge() 함수를 이용하면 더 빠르게 병합 정렬할 수 있다.
[알고리즘] 쉘 정렬
쉘 정렬은 하나의 배열을 여러 개로 쪼개 각각 정렬하는 과정을 반복한 후, 마지막으로 한 번에 정렬하는 기법이다. 이 때, 특정 간격으로 떨어진 요소들을 모아 정렬하는 것이 특징이다. 다음 그림에서는 4칸씩 떨어진 2개의 요소들을 정렬하는 경우를 보여준다. 즉, (8, 7), (1, 6), (4, 3), (2, 5)를 각각 정렬한다. 그 후 2칸씩 떨어진 요소 4개씩, 즉 (7, 3, 8, 4), (1, 2, 6, 5)를 묶어 각각 정렬한다. 그러면 전체 배열은 최종적으로 (3, 4, 7, 8, 1, 2, 5, 6)이 되며, 최종적으로 이를 단순 삽입 정렬하면 된다. 세 번의 정렬 과정에서, 기준 간격은 4 -> 2 -> 1로 변한다. 그런데 이와 같이 간격들이 서로 배수가 되면, 이미 정렬한 원소들을 ..
