정렬 알고리즘은 동일한 순위의 데이터들이 정렬 후에도 순서가 보장되는 안정된(stable) 알고리즘과 그렇지 않은 알고리즘 두가지가 있다

내부 정렬과 외부 정렬

정렬은 메모리에서 수행한다. 하지만 너무 큰 데이터가 들어와 메모리 내에 전부 적재할 수 없으면 어떻게 될까? 이럴 땐 데이터를 쪼개 여러개로 나누고 외부에서 정렬 후 합치는 과정을 거쳐야 한다. 이를 외부 정렬이라 하고 여기에서도 여러 알고리즘이 있다

버블 정렬

• 모든 원소를 하나하나 비교해가며 바꾸는 정렬, 마치 거품이 일어나듯 바뀐다 해서 버블 정렬
• 복잡도 O(n^2)

개선 1

• 리스트를 한번 훑으면서 비교후, 교환하는 것을 패스라고 한다면, 특정 패스에서 교환이 일어나지 않았다면, 다음 패스에서도 교체할 부분이 없다는 것을 의미한다
• 따라서, 교체 횟수를 저장하거나 플래그를 세워서 교체가 일어나지 않았다면 다음 패스는 진행하지 않음으로서 비교 횟수를 줄인다

def bubble_sort_enhance(lst: list):
    length = len(lst)
    for i in range(length - 1):
        print(lst)
        exch = 0
        for j in range(i, length):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]
                exch += 1
        if exch == 0:
            break

개선 2

• 버블 정렬에서 마지막으로 교체가 일어난 부분의 인덱스의 앞은 이미 정렬된 상태이다
• 이를 이용해 마지막으로 교체가 일어난 인덱스를 last 인덱스로 두고, 여기까지만 정렬한다

def bubble_sort_enhance_2(lst: list):
    n = len(lst)
    k = 0
    while k < n - 1:
        last = n - 1
        print(lst)
        for j in range(n - 1, k, -1):
            if lst[j - 1] > lst[j]:
                lst[j - 1], lst[j] = lst[j], lst[j - 1]
                last = j
        k = last

개선 3 (쉐이커 정렬)

• 만약 [9,1,3,4,6,7,8] 와 같이 큰 수가 앞자리에 있다면 비교와 교체가 많이 일어나게 된다.
• 패스에서 한번씩 번갈아가며 앞자리의 큰 수를 뒤로 옮기고, 뒷자리의 작은 수를 앞으로 옮기면 ㅂ패스의 횟수가 줄어든다

def shaker_sort(lst: list):
    left = 0
    right = len(lst) - 1
    last = right
    while left < right:
        print(lst)
        for i in range(right, left, -1):
            if lst[i] < lst[i-1]:
                lst[i], lst[i-1] = lst[i-1], lst[i],
                last = i
            left = last
            
        for j in range(left, right):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j],
                last = j
            right = last

선택 정렬

리스트 내의 원소에서 가장 작은 원소를 선택해 맨 앞으로 보내는 정렬, 안정적이지 않다