정렬 (Sort) 알고리즘

정렬 알고라즘은 n개의 숫자가 주어졌을 때, 사용자가 지정한 기준에 맞개 정렬하여 출력하는 알고리즘이다.

예를 들어, n개의 숫자가 들어있는 배열을 오름차순 조건으로 작성하면 오름차순으로 된 배열을 출력으로 구할 수 있다.

 

정렬 알고리즘 종류에는 Selection Sort, Bubble Sort, Quick Sort, Insertion Sort, Shell Sort, Merge Sort, Heap Sort, Radix Sort 등이 있다.

 

 

📌 실행 방법에 따른 분류

비교식 정렬(comparative sort)와 분산식 정렬(distribute sort)가 있다.

 

비교식 정렬은 비교하고자 하는 각 키값들을 한 번에 두 개씩 비교하여 교환하는 방식으로 정렬을 실행하는 방법이고

 

분산식 정렬은 키값을 기준으로 하여 자료를 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식으로 실행하는 방법이다.

 

 

📌 알고리즘 성능

아래 표에서 complexity는 average case를 기준으로 한 계산복잡성입니다.

 

Algorithm	In-Place	Stable	comparison	Complexity
Bubble	○	○	○	O($n^2$)
Selection	○	○	○	O($n^2$)
Insertion	○	○	○	O($n^2$)
Shell	○	○	○	O($n^2$)
Merge	×	○	○	O(nlogn)
Heap	○	×	○	O(nlogn)
Quick	○	×	○	O(nlogn)
Counting	×	○	×	O(n+k)
Radix	×	○	×	d×O(n)
Bucket	×	○	-	O(n)

 

 

---

Bubble Sort (버블정렬)

 

인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.

정렬시 부가 메모리가 필요 없는 inplace sort 기법

•  - O($n^2$) 시간 복잡도를 가지는 가장 간단하지만 비효율적인 알고리즘

 

def BubbleSort(arr):
    for loop_count in range(len(arr) - 1, 0, -1):
        for idx in range(loop_count):
            if arr[idx] > arr[idx + 1]:
                temp = arr[idx]
                arr[idx] = arr[idx + 1]
                arr[idx + 1] = temp
    return arr

 

 

---

선택정렬(Selection Sort)

 

전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식이다.

1회 iteration마다 최소값(혹은 최대값)을 찾고 단 한번만 해당 요소 위치를 바꿔준다.

• O($n^2$) 시간 복잡도를 가져서 시간이 오래걸리는 알고리즘, But 버블정렬에 비해서는 조금 더 빠르다.

def SelectionSort(arr):
    for offset in range(0, len(arr) - 1):
        offset_minValue = offset
        for num in range(offset + 1, len(arr)):
            if arr[num] < arr[offset_minValue]:
                offset_minValue = num
        temp = arr[offset_minValue]
        arr[offset_minValue] = arr[offset]
        arr[offset] = temp
    return arr

 

 

---

삽입정렬(Insertion Sort)

 

삽입정렬은 1부터 n까지 Index를 설정하여 현재위치보다 아래쪽을 순회하며 현재위치의 값을 현재위치보다 아래쪽으로 순회하며 알맞은 위치에 넣어주는 정렬알고리즘이다.

 

모든 요소에 대해 앞에서부터 차례대로 이미 정렬된 배열(sorted list)과 비교하여 sorted list 내 자신의 위치를 찾아 삽입함으로써 정렬을 완성, 

 

삽입정렬은 이미 정렬이 되어있다면 O(n)의 시간복잡도를 가지게된다. 정렬이 되어있는 경우라면 한번 순회하며 체크만 하기 때문이며 Big-O 시간복잡도는 O(n²)이다.

• 성능의 편차가 굉장히 심한 정렬법

 

 

def InsertionSort(arr):
    for index in range(1, len(arr)):
        currentvalue = arr[index]
        position = index
        while position > 0 and arr[position - 1] > currentvalue:
            arr[position] = arr[position - 1]
            position = position - 1
    arr[position] = currentvalue
    
    return arr

 

def InsertionSort(array):
    for idx in range(1, len(array)):
        for j in range(idx, 0, -1):
            if array[j] < array[j - 1]:  
                array[j], array[j - 1] = array[j - 1], array[j]
                # 기존 첫 번째 값은 두 번째 값으로, 기존 두 번째 값은 첫 번째 값으로 스와핑
            else:  # 자기보다 작은 데이터를 만나면 그 위치에서 멈춘다.
                break

    return array

 

---

쉘 정렬 (Shell Sort)

 

일정한 간격(interval)으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법이다.

 

정렬되지 않은 배열의 경우 비효율적인 삽입정렬을 개선한 기법이다.

 

'간격'을 잘못 설정한다면 성능이 굉장히 안 좋아질수 있다.

 

 

✔ 정렬 방법

•  부분집합의 기준이 되는 간격을 변수 interval에 저장
•  한 단계가 수행될 때마다 interval의 값을 감소시키고 쉘 정렬을 순환 호출한다.
•  interval가 1이 될 때까지 반복한다.

 

def shellSort(arr):
    sublistcount = len(arr) // 2
    while sublistcount > 0:

        for startposition in range(sublistcount):
            gapInsertionSort(arr, startposition, sublistcount)

        print("After increments of size", sublistcount, "The list is", arr)

        sublistcount = sublistcount // 2
        
    return arr


def gapInsertionSort(arr, start, gap):
    for i in range(start + gap, len(arr), gap):

        currentvalue = arr[i]
        position = i

        while position >= gap and arr[position - gap] > currentvalue:
            arr[position] = arr[position - gap]
            position = position - gap

        arr[position] = currentvalue

 

 

---

병합정렬(Merge sort)

 

정렬할 리스트를 반으로 쪼개나가며 좌측과 우측 리스트를 계속하여 분할해 나간 후 각 리스트내에서 정렬 후 병합(merge) 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘이다.

 

가장 많이 쓰이는 정렬 알고리즘 중 하나 이며 시간복잡도는 최소 O(nlogn)을 보장하게 된다.

 

단점은 추가적인 메모리 필요하다.

 

 

def MergeSort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    leftlist = arr[:mid]
    rightlist = arr[mid:]
    L = MergeSort(leftlist)
    R = MergeSort(rightlist)
    
    i = j = 0
    result = []
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            result.append(L[i])
            i += 1
        else:
            result.append(R[j])
            j += 1
    result += L[i:]
    result += R[j:]
    return result

 

 

---

퀵정렬(Quick sort)

 

‘기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?’ 라느 아이디어에서 시작

 

pivot을 선정하여 pivot을 기준으로 좌측과 우측으로 pivot보다 작은값은 왼쪽 pivot보다 큰값은 오른쪽으로 재배치를 하고 계속하여 분할하여 정렬하는 알고리즘이다.

 

합병정렬과 달리 주어진 배열을 임의로 나누지 않기 때문에 대개는 효율적이지만, 피봇값이 잘못 선택되면 O(n²)이 될 수도 있다.

 

일반적으로 O(nlogn)의 시간복잡도를 가진다.

 

 

def QuickSort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end

    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]

    QuickSort(array, start, right - 1)
    QuickSort(array, right + 1, end)

    return array

 

def QuickSort(array):

    if len(array) <= 1:
        return array
    pivot = array[0]  # 피벗은 첫 번째 원소
    tail = array[1:]  # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot]  # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot]  # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return QuickSort(left_side) + [pivot] + QuickSort(right_side)

 

 

---

힙정렬(Heap sort)

 

최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

 

 

✔ 정렬 방법

 

1.  n 개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.
2.  최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드로부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4.  2와 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 HeapSort(unsorted):
    n = len(unsorted)
    # BUILD-MAX-HEAP (A) : 위의 1단계
    # 인덱스 : (n을 2로 나눈 몫-1)~0
    # 최초 힙 구성시 배열의 중간부터 시작하면
    # 이진트리 성질에 의해 모든 요소값을
    # 서로 한번씩 비교할 수 있게 됨 : O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(unsorted, i, n)
    # Recurrent (B) : 2~4단계
    # 한번 힙이 구성되면 개별 노드는
    # 최악의 경우에도 트리의 높이(logn)
    # 만큼의 자리 이동을 하게 됨
    # 이런 노드들이 n개 있으므로 : O(nlogn)
    for i in range(n - 1, 0, -1):
        unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
        heapify(unsorted, 0, i)
    return unsorted

 

 

---

 계수 정렬(Counting Sort)

 

입력값의 빈도를 세어서 이를 결과리스트의 인덱스로 활용한다.

입력리스트의 요소값을 해당하는 결과리스트 인덱스 위치에 채워 넣는 방식으로 정렬을 완성한다.

 

입력리스트의 최대값($k$)이 커지면 복잡도가 크게 높아지는 단점이 있다.

 

 

✔ 정렬 과정

다음과 같은 수열 A를 정렬 해야하는 상황을 생각해봅시다.

 

 

위 수열을 정렬하면 아래와 같은 수열 B를 얻습니다.

 

 

 

array = [0,5,7,9,8,4,6,1,5,0,6,3,5,2]

# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array)+1)

for i in range(len(array)):
    count[array[i]] += 1  # 각 데이터의 해당하는 인덱스의 값 증가
    
for i in range(len(count)):  
    for j in range(count[i]):
        print(i, end = ' ')   # 등장한 횟수만큼 인덱스 출력

 

 

 

<출처 : ratsgo's blog >

<출처 : Leopold >