정렬 Sorting 정리

 

배웠으나 까먹고 또 배웠으나 헷갈리는 그래서 정리해 둬야겠다.

이미 배웠던 분들이 복기하는 용도로 사용하면 좋을 것 같다. 

---

시간 복잡도 ⍬(n² )

[정렬되지 않은 리스트의 크기를 n부터 시작해 하나씩 줄임]

Selection sort( 선택 정렬 ) : 제일 큰(작은) 수를 찾아서 제일 뒤(앞)로 보내기

코드보기

def selectionSort(A):
    for i in range(0, len(A)-1):
        min_num = i
        for j in range(i + 1, len(A)):
            if A[j] < A[min_num]:
                min_num = j
        A[i], A[min_num] = A[min_num], A[i]
        print(A)

selectionSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1])
# [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
# [0, 1, 3, 5, 4, 10, 8, 9, 2, 7]
# [0, 1, 2, 5, 4, 10, 8, 9, 3, 7]
# [0, 1, 2, 3, 4, 10, 8, 9, 5, 7]
# [0, 1, 2, 3, 4, 10, 8, 9, 5, 7]
# [0, 1, 2, 3, 4, 5, 8, 9, 10, 7]
# [0, 1, 2, 3, 4, 5, 7, 9, 10, 8]
# [0, 1, 2, 3, 4, 5, 7, 8, 10, 9]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]

Bubble sort( 버블 정렬 ) : 2개씩 비교해 가면서 큰 수가 점점 뒤로 가게 하기

코드보기

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


bubbleSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1])
# [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
# [0, 3, 7, 5, 4, 10, 8, 9, 2, 1]
# [0, 3, 5, 7, 4, 10, 8, 9, 2, 1]
# [0, 3, 5, 4, 7, 10, 8, 9, 2, 1]
# [0, 3, 5, 4, 7, 8, 10, 9, 2, 1]
# [0, 3, 5, 4, 7, 8, 9, 10, 2, 1]
# [0, 3, 5, 4, 7, 8, 9, 2, 10, 1]
# [0, 3, 5, 4, 7, 8, 9, 2, 1, 10]
# [0, 3, 4, 5, 7, 8, 9, 2, 1, 10]
# [0, 3, 4, 5, 7, 8, 2, 9, 1, 10]
# [0, 3, 4, 5, 7, 8, 2, 1, 9, 10]
# [0, 3, 4, 5, 7, 2, 8, 1, 9, 10]
# [0, 3, 4, 5, 7, 2, 1, 8, 9, 10]
# [0, 3, 4, 5, 2, 7, 1, 8, 9, 10]
# [0, 3, 4, 5, 2, 1, 7, 8, 9, 10]
# [0, 3, 4, 2, 5, 1, 7, 8, 9, 10]
# [0, 3, 4, 2, 1, 5, 7, 8, 9, 10]
# [0, 3, 2, 4, 1, 5, 7, 8, 9, 10]
# [0, 3, 2, 1, 4, 5, 7, 8, 9, 10]
# [0, 2, 3, 1, 4, 5, 7, 8, 9, 10]
# [0, 2, 1, 3, 4, 5, 7, 8, 9, 10]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]

 

[정렬된 리스트의 수를 하나씩 늘림]

Insertion sort( 삽입 정렬 ) : 원소를 정렬된 리스트 안에 넣는 행동을 반복 → 거의 정렬된 리스트가 주어지면 특히 빠름

코드보기

def insertionSort(A):
    for i in range(0, len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key
        print(A)

insertionSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1])
# [7, 0, 3, 5, 4, 10, 8, 9, 2, 1]
# [0, 7, 3, 5, 4, 10, 8, 9, 2, 1] 0 자리 찾아주기
# [0, 3, 7, 5, 4, 10, 8, 9, 2, 1] 3 자리 찾아주기
# [0, 3, 5, 7, 4, 10, 8, 9, 2, 1] 5 자리 찾아주기
# [0, 3, 4, 5, 7, 10, 8, 9, 2, 1]
# [0, 3, 4, 5, 7, 10, 8, 9, 2, 1]
# [0, 3, 4, 5, 7, 8, 10, 9, 2, 1]
# [0, 3, 4, 5, 7, 8, 9, 10, 2, 1]
# [0, 2, 3, 4, 5, 7, 8, 9, 10, 1]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]

 

---

시간 복잡도 ⍬(n logn)

Merge sort( 병합 정렬 ) : 원래 크기를 반으로 자르고 크기를 비교해 병합 (작은 문제로 만들고 해결)

코드보기

def mergeSort(A, l, r):
    if l >= r:
        return
    if l < r:
        q = (l + r) // 2
        print("mergeSort", A[l:q+1],A[q+1:r+1])
        mergeSort(A, l, q)
        mergeSort(A, q + 1, r)
        merge(A, l, q, r)


def merge(A, l, q, r):
    i = l
    j = q + 1
    t = 0
    tmp = [0 for i in range(r - l + 1)]
    print("merge")
    while i <= q and j <= r:
        if A[i] <= A[j]:
            tmp[t] = A[i]
            t += 1
            i += 1
        else:
            tmp[t] = A[j]
            t += 1
            j += 1
        print(tmp)
    # 남은 부분이 있다면 이어 붙이기
    while i <= q:
        tmp[t] = A[i]
        t += 1
        i += 1
    print(tmp)
    while j <= r:
        tmp[t] = A[j]
        t += 1
        j += 1
    print(tmp)
    # tmp 다시 A로 옮기기
    i = l
    t = 0
    while i <= r:
        A[i] = tmp[t]
        t += 1
        i += 1
    print('\n')


mergeSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1], 0, 9)
mergeSort [7, 0, 3, 5, 4] [10, 8, 9, 2, 1]
# mergeSort [7, 0, 3] [5, 4]
# mergeSort [7, 0] [3]
# mergeSort [7] [0]
# merge
# [0, 0]
# [0, 7]
# [0, 7]
# 
# 
# merge
# [0, 0, 0]
# [0, 3, 0]
# [0, 3, 7]
# [0, 3, 7]
# 
# 
# mergeSort [5] [4]
# merge
# [4, 0]
# [4, 5]
# [4, 5]
# 
# 
# merge
# [0, 0, 0, 0, 0]
# [0, 3, 0, 0, 0]
# [0, 3, 4, 0, 0]
# [0, 3, 4, 5, 0]
# [0, 3, 4, 5, 7]
# [0, 3, 4, 5, 7]
# 
# 
# mergeSort [10, 8, 9] [2, 1]
# mergeSort [10, 8] [9]
# mergeSort [10] [8]
# merge
# [8, 0]
# [8, 10]
# [8, 10]
# 
# 
# merge
# [8, 0, 0]
# [8, 9, 0]
# [8, 9, 10]
# [8, 9, 10]
# 
# 
# mergeSort [2] [1]
# merge
# [1, 0]
# [1, 2]
# [1, 2]
# 
# 
# merge
# [1, 0, 0, 0, 0]
# [1, 2, 0, 0, 0]
# [1, 2, 8, 9, 10]
# [1, 2, 8, 9, 10]
# 
# 
# merge
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 1, 2, 0, 0, 0, 0, 0, 0, 0]
# [0, 1, 2, 3, 0, 0, 0, 0, 0, 0]
# [0, 1, 2, 3, 4, 0, 0, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 0, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 7, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 7, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]

Quick sort( 퀵 정렬 ) : 기준을 잡고 그것보다 크면 오른쪽, 아니면 왼쪽 (해결해가면서 작은 문제로 만듬)

코드보기

def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q - 1)
        quickSort(A, q + 1, r)


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        # pivot보다 작을 경우 i와 j 같이 증가하다가 더 커지는 경우 j 만 증가함
        if A[j] < x:
            i += 1
            A[i], A[j] = A[j], A[i]
    # 피봇 자리 배치
    A[i + 1], A[r] = A[r], A[i + 1]
    print("pivot:",x, A[p:r])
    return i + 1


A = [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
quickSort(A, 0, 9)
print(A)
# pivot: 1 [0, 1, 3, 5, 4, 10, 8, 9, 2]
# pivot: 7 [3, 5, 4, 2, 7, 9, 10]
# pivot: 2 [2, 5, 4]
# pivot: 3 [3, 4]
# pivot: 5 [4]
# pivot: 8 [8, 10]
# pivot: 9 [9]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]

• 최악의 상황 : 제일 크거나 작은 값을 기준으로 잡아 분류가 일어나지 않으면? → 무작위로 3개 잡아서 중간값 사용

Heap sort( 힙 정렬 ) : heap 을 이용한 정렬, heap 을 build 한 후 위의 값을 pop 하면서 정렬 

• Heap의 build O(n)으로 하는 거 알고 계시나요? - leaf node가 n/2개 라 아래에서 부터하는 게 효율적임!

코드보기

import heapq


def heapSort(A):
    tmp = [x for x in A]
    heap_tmp = []
    for i in tmp:
        heapq.heappush(heap_tmp, -i)
    for i in range(len(tmp)-1, -1, -1):
        A[i] = -heapq.heappop(heap_tmp)


A = [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
heapSort(A)
print(A)

Shell sort( 쉘 정렬 ) : insertion sort를 더 효율적으로 하는 방법! gap 을 이용해 뭉텅이로 정렬해놔서 마지막 insertion sort 할 때 효율을 높임

시뮬레이션 : https://www.w3resource.com/ODSA/AV/Sorting/shellsortAV.html

---

특수 정렬 ⍬(n)

Counting sort( 계수 정렬 ): -O(n)~+O(n) 범위에 있는 정수일 경우에만 성립, 각 원소가 몇번 등장하는 지 Count 해 배열의 자리를 계산한 후 채워 나가는 방법 [영상자료 : https://www.youtube.com/watch?v=7zuGmKfUt7s]

Radix sort( 기수 정렬 ) : 모두 K 개 이하의 자릿수를 가진 자연수와 같은 경우에만 성립, 자릿수대로 정렬해 나가는 방법

Bucket sort( 버킷 정렬 ) : 원소들이 균등 분포일 때 사용가능, 0~1 사이의 값을 가진 데이터 배열일때 배열의 크기만큼 곱한 후, 각 버킷에 담기, 버킷별로 정렬 한 후 합친다 [영상자료 : https://www.youtube.com/watch?v=VuXbEb5ywrU]

 

 

 

["쉽게 배우는 자료구조 with 파이썬 - 문병로" 를 참고하여 작성하셨습니다.]