정렬 알고리즘(Sorting Algorithm)

버블 정렬(Bubble Sort)

버블 정렬

• 기본 원칙은 1번과 2번 비교, 2번과 3번 비교.... n-1번과 n번째를 정렬하고, 다음은 n-1번째까지를 반복하는 정렬
• 최대 n(n-1)/2 번 정렬
• 시간 복잡도는 O(n^2)
• 성능면에서는 굉장히 비효율적

def bubble_sort(arr):
    for i in range(len(arr) - 1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

선택 정렬(Selection Sort)

선택 정렬

• 1번 부터 끝까지 비교하여 가장 작은 값을 1번에 놓고, 2번부터 비교하여 그 다음 작은 값 이런식으로 계속해서 비교
• 어떤 정렬방식으로 되어 있던 n(n-1)/2의 시간 소모
• 시간 복잡도는 O(n^2)
• 버블정렬보다 두배 정도 빠른 성능을 보임

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

삽입 정렬(Insertion Sort)

삽입 정렬

• k번째 원소를 1부터 k-1까지 비교하여 적절한 위치에 넣으며 한칸씩 뒤로 미루는 방식
• 이미 정렬된 알고리즘에 삽입/제거 시 효율적인 알고리즘
• 정렬이 된 형태에 따라 비효율적일 수 있음
• 시간복잡도는 O(n^2)

def insertion_sort(arr):
    for end in range(1, len(arr)):
        i = end
        while i > 0 and arr[i - 1] > arr[i]:
            arr[i - 1], arr[i] = arr[i], arr[i - 1]
            i -= 1

셸 정렬(Shell Sort)

• 삽입정렬을 보완한 알고리즘
• 삽입정렬과 달리 전체의 리스트를 한 번에 정렬하지 않음
• 이는 삽입정렬이 어느 정도 정렬된 배열에서 빠르게 동작하는 것을 활용하기 위함
• 정렬할 리스트를 간격을 두고 각 회전마다 간격을 절반으로 줄이는 방식
  • 간격은 홀수가 좋으며, 절반으로 줄일 떄 짝수인 경우 +1을 해주는 것이 좋음
• 시간복잡도 O(n^2)

병합 정렬(Merge Sort)

병합 정렬

• 원소의 개수가 0 또는 1개가 될 때까지 쪼갠 후 자른 순서의 역순으로 크기를 비교해 병합해 나가는 방식
• 병합된 부분은 이미 정렬이 되어 있으므로 전부 비교하지 않아도 제자리 찾아갈 수 있음
• 장점은 데이터 상태에 별 영향을 받지 않음
• 단점은 데이터 크기만한 메모리가 추가로 소모
• 시간복잡도는 O(nlogn)
• 예시

  병합 정렬

def merge_sort(arr):
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

힙 정렬(Heap Sort)

힙 정렬

• 완전 이진트리의 일종인 힙(heap)을 이용한 정렬 방식
• 최대 힙 혹은 최소 힙형태로 구현
• 새로운 값이 들어오면 해당 값을 마지막 노드에 넣은 뒤 부모노드와 비교하여 해당 값과 바꾸는 동작을 반복(최대 힙이면 부모노드 보다 큰지, 최소 힙이면 부모노드보다 작은지 확인)
• 이 후에 root 노드 값을 꺼낸 뒤 가장 마지막 노드를 root 노드에 넣고 자식 노드들과 조건 비교하며 재 정렬 진행
• 위의 동작을 반복하는 것을 통해 정렬
• 시간 복잡도는 O(nlogn)

퀵 정렬(Quick Sort)

퀵 정렬

• 평균적인 상황에서 최고의 성능을 발휘하는 알고리즘
• 적절한 원소를 기준(pivot)으로 정한뒤 그보다 작은 것을 앞으로, 큰 것을 뒤로 미루는 방식으로 정렬 진행
• 그리고 다시 앞 뒤로 나뉜 배열을 또 다른 기준을 정해 반복한다, 각 크기가 0 또는 1이 될 때까지 반복
• 시간 복잡도는 O(nlogn) 단, 피벗을 어떻게 잡느냐가 시간 복잡도에 가장 큰 영향을 미침
• 예시

  퀵 정렬 예시

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

정렬 알고리즘 시간 복잡도

시간 복잡도

참고

• 정렬알고리즘: https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.2.3
• 알고리즘 코드: https://www.daleseo.com/
• 정렬알고리즘 시간복잡도: https://www.bigocheatsheet.com/