1. Introduction 3중 병합 정렬은 전체 리스트를 3단계로 나눠 분할 정복하는 merge sort의 variation이다. 2. Approach 다음 코드는 파이썬에서 구현한 3중 병합 정렬이다. def threeWayMergeRun(arr, a, b): threeWaySplit(arr, a, b+1, arr[:]) def threeWaySplit(arr, low, high, clone): if high - low < 2: return mid1 = low + ((high - low) // 3) mid2 = low + 2 * ((high - low) // 3) + 1 threeWaySplit(clone, low, mid1, arr) threeWaySplit(clone, mid1, mid2, ar..

1. Introduction 병합 정렬은 프로그램 내장 방식으로 유명한 존 폰 노이만에 의해 제안된 정렬 알고리즘이다. 분할 정복법을 기반으로 하여 주어진 리스트를 분할하고 정렬하여 다시 병합한다. 병합 정렬은 최선, 최악, 평균 상황에서 항상 시간복잡도가 $O(nlog\; n)$임을 보장하며 stable한 알고리즘이다. 구현 방식에는 Top-down 방식과 Bottom-up 방식이 있다. 2. Approach 다음 이미지는 병합 정렬의 과정을 보여준다. 출처는 위키피디아. 다음 코드는 Top-down merge sort를 파이썬에서 구현한 것이다. def topDownMergeRun(arr, a, b): clone = arr[a:b+1] topDownMerge(clone) arr[a:b+1] = clo..

1. Introduction 쉘 정렬은 삽입 정렬이 어느정도 정렬된 리스트에서 좋은 효율을 보인다는 점에서 착안한 삽입정렬의 variation이다. gap에 따라, 떨어진 원소들을 먼저 정렬하고 gap을 줄여나가면서 정렬을 완성하는 정렬 알고리즘이다. 2. Approach 다음 이미지는 쉘 정렬의 과정을 보여준다. 출처는 위키피디아. 다음 코드는 파이썬으로 구현한 쉘 정렬이다. def shell(arr, a, b): n = b-a gap = n//3 + 1 while gap > 0: for i in range(a+gap,b+1): temp = arr[i] j = i while j >= gap and arr[j-gap] >temp: arr[j] = arr[j-gap] j -= gap arr[j] = tem..

1. Introduction 삽입 정렬은 원소가 들어갈 자리를 찾고 그 위치에 삽입한 뒤, 그 보다 큰 원소를 뒤로 밀어내는 방식의 정렬 알고리즘이다. 선택 정렬과 같이 $O(n^2)$의 시간 복잡도를 가지고 있다. 2. Approach 다음 이미지는 삽입 정렬의 과정을 보여준다. 출처는 위키피디아. 다음 코드는 파이썬에서 구현한 삽입 정렬이다. def insertion(arr, a, b): for i in range(a+1, b+1): key = arr[i] j = 0 for j in range(i-1, a-2, -1): if arr[j] > key: arr[j+1] = arr[j] else: break arr[j+1] = key 3. Discussion 삽입 정렬은 stable한 정렬에 속하며 in-..

1. Introduction 이중 선택 정렬은 한번의 루틴에서 최소값과 최대값을 같이 찾는 방식으로 정렬하는 선택정렬의 variation이다. 2. Approach 다음 코드는 파이썬에서 이중 선택 정렬을 구현한 것이다. def double_selection(arr, a , b): start = a end = b while start arr[max]: max = i arr[start], arr[min] = arr[min], arr[start] arr[end], arr[max] = arr[max], arr[end] start +..

1. Introduction 선택정렬은 각 루틴마다 최소(최대)값을 찾아 정렬하는 방식의 정렬 알고리즘이다. 버블 정렬과 그 variation들과 같은 $O(n^2)$알고리즘이지만, 저들과는 궤를 달리한다. 2. Approach 다음 이미지는 선택 정렬의 과정을 시각화 한것이다. 출처는 위키피디아. 다음 코드는 파이썬에서 구현한 선택정렬이다. def selection(arr, a, b): for i in range(a, b): min = i for j in range(i+1, b+1): if arr[j] < arr[min]: min = j arr[i], arr[min] = arr[min], arr[i] 3. Discussion 선택정렬은 stable한 정렬에 속하며 in-place한 알고리즘에 속한다. ..

1. Introduction 홀짝 정렬은 홀수부분과 짝수부분을 나눠서 정렬하는 버블 정렬의 variation이다. 칵테일 정렬과 같이 시간복잡도가 $O(n^2)$에 머물러 있지만 오리지널 버블 정렬보다 빠른 것으로 알려져 있다. 2. Approach 다음 이미지는 홀짝 정렬의 과정을 시각적으로 보여준다. 출처는 위키피디아. 다음 코드는 파이썬으로 구현된 홀짝 정렬이다. def odd_even(arr, a, b): isSorted = True while isSorted == True: isSorted = False for i in range (a, b, 2): if arr[i] > arr[i + 1]: arr[i], arr[i + 1]= arr[i + 1], arr[i] isSorted = True for..

1. Introduction 칵테일 정렬 (또는 칵테일-셰이커 정렬)은 버블 정렬의 Variation으로, 한번의 루틴마다 방향을 바꿔서 정렬하는 알고리즘이다. 버블 정렬에서 크게 바뀌지는 않았지만 일반적인 경우에서 버블 정렬보다 빠르다고 한다. 2. Approach 다음 이미지는 칵테일 정렬의 과정을 시각화한 것이다. 출처는 위키피디아. 양 끝을 왔다갔다 하면서 비교하는 인덱스가 배열의 중간으로 수렴하는 것을 볼 수 있다. 다음 코드는 칵테일 정렬의 파이썬 구현이다. def cocktail(arr, a, b): swapped = True while swapped == True: swapped = False for i in range (a, b): if arr[i] > arr[i + 1]: arr[i],..