정렬 기본

정렬은 어떤 기준에 따라 데이터를 순서대로 나열하는 것.

여러 가지 정렬 방법에 대해 알아보자.

 

1. 선택 정렬

처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸는 정렬방법이다.

 

선택정렬

from typing import List
# 선택 정렬
def SelectionSort(arr: List[int]) -> None:
    for i in range(len(arr)):
        minIndex = i
        for j in range(i+1, len(arr)):
            if arr[minIndex] > arr[j]:
                minIndex = j
        arr[i], arr[minIndex] = arr[minIndex], arr[i] # 스와프

    print(arr)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
SelectionSort(array)
***
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

2. 삽입정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 방식이다.

위, 선택정렬에 비해 일반적으로 효율적이다.

삽입정렬

# 삽입 정렬
def InsertionSort(arr: List[int]) -> None:
    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] # swap
            else:
                break
    print(arr)
    
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
InsertionSort(array)
***
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

3. 퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

퀵 정렬

 

# 퀵 정렬
def QuickSort(arr: List[int], start: int, end: int) -> None:
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = Partition(arr, start, end)

    QuickSort(arr, start, pivot - 1)
    QuickSort(arr, pivot + 1, end)

def Partition(arr: List[int], start: int, end: int) -> int:
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end

    while left <= right:
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        
        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
            pivot = right
        else:
            arr[left], arr[right] = arr[right], arr[left]

    return pivot

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
QuickSort(array, 0, len(array)-1)
print(array)

 

4. 계수 정렬

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

계수 정렬

# 계수 정렬
def RedixSort(arr: List[int]) -> None:
    # 모든 원소의 값이 0보다 크거나 같다고 가정
    # 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
    count = [0] * (max(arr) + 1)

    for i in range(len(arr)):
        count[arr[i]] += 1

    for i in range(len(count)):
        for _ in range(count[i]):
            print(i, end=" ") #등장한 횟수만큼 인덱스 출력

array = [7, 4, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
RedixSort(array)
***
0 0 1 1 2 2 3 4 4 5 6 7 8 9 9

 

출처 : (이코테 2021 강의 몰아보기) 4. 정렬 알고리즘 - YouTube