17강 정렬 | Notion

정렬

리스트의 항목들을 특정한 순서에 따라 배열하는 것

왜 하는가?

문제의 복잡도를 감소시킬 수 있습니다.

검색의 복잡도를 감소시킬 수 있습니다.
Bubble Sort

바로 옆에 있는 데이터와 비교하여, 더 작은 값을 앞으로 보내는 알고리즘

시간복잡도 : O(N^2)

data = [10,2,3,4,1,5,7,8]

for i in range(len(data)):
    for j in range(len(data)):
        if data[i] < data[j]:
            data[i], data[j] = data[j], data[i]

Selection Sort

가장 직관적인 접근 방법으로, 전체 데이터중 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘

시간복잡도 : O(N^2)

data = [10,2,3,4,1,5,7,9]

for i in range(len(data)):
    min_ = 99999
    for j in range(i, len(data)):
        if min_ > data[j]:
            min_ = data[j]
            idx = j

    data[i], data[idx] = data[idx], data[i]

Insertion Sort

앞부분에서부터 차례대로 이미 정렬되어있는 부분과 비교하여, 현재 데이터를 적절한 위치에 삽입하는 알고리즘

시간복잡도 : O(N^2)
```
data = [10,2,3,4,1,5,7,9]

for i in range(len(data)-1):
    j = i
    while j >= 0 and data[j] > data[j+1]:
        data[j], data[j+1] = data[j+1], data[j]
        j -= 1
```

Merge Sort

분할정복 방식으로, 우선 반으로 나누고, 나중에 합치는 단계에서 정렬을 하는 알고리즘

시간복잡도 : O(N*logN)

알고리즘

계속해서 리스트를 반으로 나눠줍니다.
다시 리스트를 병합하면서 정렬을 진행합니다.

sorted_data = [0]*8
numbers = [7,6,5,8,3,5,9,1]

def merge(data, m, middle, n):
    i = m
    j = middle + 1
    k = m
    # 작은 순서대로 배열에 삽입
    while i <= middle and j <= n:
        if data[i] <= data[j]:
            sorted_data[k] = data[i]
            i += 1
        else:
            sorted_data[k] = data[j]
            j +=1
        k += 1
    #남은 데이터도 삽입
    if i > middle:
        for t in range(j,n+1):
            sorted_data[k] = data[t]
            k += 1
    else:
        for t in range(i,middle+1):
            sorted_data[k] = data[t]
            k += 1

    for t in range(m,n+1):
        data[t] = sorted_data[t];

def mergeSort(data, m, n):
    if m < n:
        middle = (m + n) // 2
        mergeSort(data, m, middle)
        mergeSort(data, middle + 1, n)
        merge(data, m, middle, n)

mergeSort(numbers, 0, 7)
print(numbers)

Heap Sort

힙 트리구조를 이용한는 정렬 알고리즘

시간복잡도 : O(N*logN)

Heap

최소값이나 최대값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리
- 최대힙은 부모노드가 자식노드보다 큰 힙
- 최소힙은 부모노드가 자식노드보다 작은 힙
Heapify Algorithm

특정한 하나의 노드에 대해서 수행하는 것으로 하나의 노드를 제외하고는 최대힙이 구성되어있는 상태라고 가정합니다. 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘입니다.

알고리즘
1. 정렬해야하는 데이터에 대해서 Heapify Algorithm을 이용하여 힙 구조를 만듭니다.
2. root에 있는 데이터를 가장 뒤를 보내줍니다.
3. 나머지 데이터에 대해서도, 위의 과정을 반복합니다.

def heapify(unsorted, index, heap_size):
    largest = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
        largest = left_index
    if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
        largest = right_index
    if largest != index:
        unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
        heapify(unsorted, largest, heap_size)

def heap_sort(unsorted):
    n = len(unsorted)
    for i in range(n//2 - 1, -1, -1):
        heapify(unsorted, i, n)
    for i in range(n - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)

Quick Sort

분할정복 방식을 사용하여, 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나누면서 정렬하는 알고리즘

시간복잡도 : O(N*logN)

알고리즘

리스트에서 한 요소를 pivot으로 지정합니다.
pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로, 큰 요소들은 모두 pivot의 오른쪽으로 옮겨집니다.
pivot을 제외한 왼쪽과 오른쪽 리스트를 다시 정렬합니다.
이러한 과정을 더이상 분할이 불가능할 때까지, 계속 반복해서 진행합니다.

def quickSort(data, start, end):
    # 원소가 1개인 경우
    if start >= end:
        return
    # 키는 첫번째 원소
    key = start
    i = start + 1
    j = end
    # 엇갈릴 때 까지 반복
    while i <= j:
        # 키 값보다 큰 값을 만날 때 까지 이동
        while i <= end and data[i] <= data[key]:
            i += 1
        # 키 값보다 작은 값을 만날 때 까지 이동
        while data[j] >= data[key] and j > start:
            j -= 1
        # 엇갈린 상태면 키 값과 교체
        if i > j:
            data[key], data[j] = data[j], data[key]
        else:
            data[i], data[j] = data[j], data[i]

    quickSort(data, start, j - 1)
    quickSort(data, j + 1, end)

BEFORE

16강 해싱

18강 그래프 알고리즘

BEFORE

NEXT