정렬 알고리즘 정리 모음

선택 정렬

- 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복한다.

- 시간복잡도는 O(N^2)이다.

=> 배열 순회하는 반복문(N) + 가장 작은 데이터를 찾는 반복문(N-1+N-2+...+2) = N * (N+1) / 2

<과정>

1) 바꿀 데이터의 인덱스를 i라 하고, 0(맨 앞)으로 초기화한다.

2) 가장 작은 데이터를 선택해 i 인덱스의 데이터와 바꾼다.

3) 그다음 작은 데이터를 선택해 i+1 인덱스에 있는 데이터와 바꾼다.

4) i가 배열의 마지막에 도착할 때까지 반복한다.

<구현>

def selection(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
            	min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
        
    print(arr)

 

삽입 정렬

- 배열에서 적절한 위치를 찾은 뒤에 해당 위치에 데이터를 삽입한다.

- 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 효율적이다.

- 시간 복잡도는 O(N^2)이다. 최선의 경우(데이터가 완전히 정렬된 경우)는 O(N)의 시간 복잡도를 가진다.

<과정>

1) 첫번째 데이터는 그 자체로 정렬되어 있다고 하자. 

2) 두번째 데이터부터 정렬된 데이터의 끝부터 처음까지 비교하면서 필요할 경우 삽입한다.

3) 마지막 데이터를 비교할 때까지 반복한다.

<구현>

def insertion(arr):
    for i in range(1, len(arr):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
    print(array)

 

버블 정렬

- 서로 인접한 두 원소의 대소 관계를 비교해가며 정렬하는 알고리즘.

- 시간 복잡도는 O(N^2)이다.

<과정>

1) 서로 인접한 두 원소를 비교한 후, 큰 원소를 뒤로 보낸다.

2) 1회전을 수행하면 가장 큰 자료가 맨 뒤로 이동한다.

3) 이 과정을 N번 수행한다.

<구현>

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

 

퀵 정렬

- 평균 시간 복잡도는 O(NlogN)이다. 최악의 경우에는 O(N^2)이다. pivot의 위치에 영향을 받기 때문이다.

- 데이터가 이미 정렬되어 있는 경우 느리게 동작한다.

<과정>

1) 배열에서 첫 번째 데이터를 pivot으로 한다. (마지막에 두어도 된다)

2) 배열을 분할하기 위해 left, right 배열을 준비한다.

3) 피벗을 제외한 배열을 왼쪽에서부터 순회하면서 pivot보다 값이 작은 경우 left 배열에 넣는다.

4) 같은 방법으로 순회하면서 pivot보다 값이 큰 경우 right 배열에 넣는다.

5) 처음 배열은 pivot보다 작은 값 배열, pivot, pivot보다 큰 값 배열로 나뉘어진다.

6) pivot을 제외한 두 배열에 대해 퀵 정렬을 재귀 수행한다.

7) pivot과 배열을 나눌 수 없을 때(주어진 배열의 원소가 하나일 때), 재귀를 종료한다.

<구현>

def quick_sort(arr):
    if len(arr) <= 1:
       return arr
       
    pivot = arr[0]
    left = []
    right = []
    
    for data in arr[1:]:
        if data <= x:
            left.append(data)
        else:
            right.append(data)
            
    return quick_sort(left) + [pivot] + quick_sort(right)

 

병합 정렬

- 항상 O(NlogN)의 시간복잡도를 갖는다.

- 추가적인 메모리 공간을 필요로 한다.

<과정>

1) 중간 지점을 정해서 주어진 배열을 절반씩 나눈다.

2) 나눈 두 배열에 대해 재귀 호출 한다. 

3) 두 배열을 값을 비교해가며 합친다.

<구현>

def merge_sort(arr, l, r):
    if r > 1:
       mid = (l+r) // 2
       
       left = arr[:mid]
       right = arr[:mid]
       merge_sort(left, l, m-1)
       merge_sort(right, m, r)
       
       i = j = k = 0
       while i < len(left) and j < len(right):
           if left[i] < right[i]:
               arr[k] = left[i]
               i+=1
           else:
               arr[k] = right[j]
               j+=1
           k+=1
       while i < len(left):
           arr[k] = left[i]
           i+=1
           k+=1
       while j < len(right):
           arr[k] = right[j]
           j+=1
           k+=1
       

 

힙 정렬

- 배열이 힙 성질을 만족하는지 검사하면서 값을 교환하는 방식.

- in-place 정렬로, 추가 메모리가 필요하지 않다.

- 삽입, 삭제에 O(logN), N개의 데이터를 빼내는 데 O(N)이므로 시간복잡도는 O(NlogN)이다.

- 배열로 구현했기 때문에 인덱스 접근이 빠르다.

<과정>

1) 힙에 데이터를 전부 넣는다. (삽입)

2) 힙에서 데이터를 하나씩 뽑아 배열의 마지막 인덱스부터 채워 넣는다. (삭제)

<구현>

heapq 모듈을 사용하여 간단히 구현할 수 있다.

import heapq
def heap_sort(arr):
    heapq.heapify(arr)
    
    for i in range(len(arr)):
       val = heapq.heappop(arr)
       print(val)

 

계수 정렬

- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용한다.

- 별도의 배열을 선언하고 그 안에 정렬된 값을 넣는다. 그래서 계수 정렬은 비교 기반의 알고리즘이 아니다.

- 데이터의 개수를 N, 최대값 크기를 K라고 했을 때, 시간 복잡도는 O(N + K)이다. 

- 공간 복잡도는 O(N+K)이며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.

<과정>

1) 가장 큰 데이터와 가장 작은 데이터의 차이 + 1 크기의 배열을 선언한다. 모든 범위를 담을 수 있어야 하기 때문이다.

2) 배열을 0으로 초기화한다.

3) 데이터가 담긴 배열을 순회하면서 데이터 값에 해당하는 인덱스 위치의 데이터를 1씩 증가시킨다.

4) 계수를 저장한 배열을 순회하면서 그 값만큼 해당 인덱스값을 출력한다.

ex. [0, 1, 3, 2, 1] => 1, 2, 2, 2, 3, 3, 4

<구현>

def count_sort(arr):
    count_amount = max(arr) - min(arr) + 1
    count_arr = [0 for _ in range(count_amount)]
    
    for a in arr:
       count_arr[a] += 1
    
    for i, c in enumerate(count_arr):
        for i in range(c):
            print(i)
    

 

기수 정렬

- 자리수에 따라 정렬을 하는 방식으로, 비교 연산을 하지 않는다.

- 추가적인 메모리 공간이 필요하다.

- 계수 정렬보다 넓은 범위를 정렬할 수 있다.

- 정수 자료형에서 매우 빠르고, 문자열도 효율이 좋다.

<과정>

1) 배열을 만들고, 10개의 queue를 초기화한다.

2) 데이터가 있는 배열을 순회하면서 1의 자리수에 해당하는 값인 인덱스의 큐에 데이터를 넣는다.

3) 모든 큐의 데이터를 순서대로 빼서 배열에 다시 넣는다.

4) 다음 자리수에 해당하는 값을 기준으로 다시 큐에 데이터를 넣는다. 다음 자리수에 해당하는 데이터가 없을 때까지 반복한다.

<구현>

def countingSort(arr, exp1):
    n = len(arr)
    output = [0] * (n)
    count = [0] * (10)
    
    for i in range(0, n):
        index = (arr[i] / exp1)
        count[int(index % 10)] += 1
 
    for i in range(1, 10):
        count[i] += count[i - 1]
 
    i = n - 1
    while i >= 0:
        index = (arr[i] / exp1)
        output[count[int(index % 10)] - 1] = arr[i]
        count[int(index % 10)] -= 1
        i -= 1
 
    i = 0
    for i in range(0, len(arr)):
        arr[i] = output[i]
 
def radixSort(arr):
    max1 = max(arr)
    exp = 1
    while max1 / exp > 0:
        countingSort(arr, exp)
        exp *= 10