정렬 알고리즘

보통 코테 문제를 풀이할 때는 sort()함수를 사용하여 정렬하지만, 정렬을 실제로 구현하는 데에는 많은 방법이 존재한다.

정렬 알고리즘의 종류에는 Selection Sort(선택 정렬), Bubble Sort(버블 정렬), Quick Sort(퀵 정렬), Insertion Sort(삽입 정렬), Shell Sort(셸 정렬), Merge Sort(병합 정렬), Heap Sort(힙 정렬) 등이 있다.

정렬 알고리즘의 분류

정렬 알고리즘은 두가지 기준으로 분류가 가능하다.

실행 방법에 따른 분류

실행 방법에 따른 분류로는 비교식 정렬과 분산식 정렬이 있다.

비교식 정렬

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

분산식 정렬

분산식 정렬은 키값을 기준으로 여러 개의 부분 집합으로 분해하고, 각 부분 집합을 정렬하는 방법이다.

정렬 장소에 따른 분류

정렬 장소에 따른 분류로는 내부 정렬과 외부 정렬이 있다.

내부 정렬

내부 정렬은 정렬할 자료를 메인 메모리에 올려서 정렬하는 방식으로 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모리의 용량에 따라 제한된다.

• 교환 방식
  - Selection, Bubble, Quick
• 삽입 방식
  - Insert, Shell
• 병합 방식
  - 2-way, n-way
• 분배 방식
  - Radix
• 선택 방식
  - Heap, Tree

외부 정렬

외부 정렬은 정렬할 자료를 보조 기억 장치에서 정렬하는 방식으로 대용량의 보조 기억 장치를 사용하기 때문에 내부 정렬보다 속도는 떨어지지만 내부 정렬로 처리할 수 없는 대용량의 자료에 대한 정렬이 가능하다.

• 병합 방식
  - 2-way, n-way

알고리즘 성능

일반적으로 Quick Sort가 가장 빠르다고 알려져 있다. 최악의 경우 n^2이 발생하는데 이 경우는 피벗(기준값)이 최솟값이거나 최댓값일 경우에만 해당된다. 이를 피하기 위해 피벗을 랜덤으로 잡거나 Media-Of-Tree-Partitioning기법을 사용한다.

이미 정렬되어 있는 경우에는 Insertion Sort가 가장 빠르다.

• O(n^2)
  - Bubble, Selection, Insertion, Quick
• O(n log n)
  - Heap, Merge
• O(kn)
  - Radix

Code

Bubble Sort

인접한 원소 두개를 비교하여 교환하는 방식

첫번째 원소부터 마지막 원소까지 반복하며 비교하고, 첫번째 반복이 끝났을 때 최댓값이 가장 뒤에 오게 된다.

def Bubble_Sort(nums):
    for i in range(len(nums)):
        for j in range(len(nums)-i):
            if j+1<len(nums) and nums[j]>nums[j+1]:
                nums[j], nums[j+1]=nums[j+1], nums[j]
    return nums

Selection Sort

• 전체 원소에서 가장 작은 원소를 찾아 가장 앞과 교환한다.
• 전체 원소에서 두번째로 작은 원소를 찾아 두번째 자리와 교환한다.
• 전체 원소에서 세번째로 작은 원소를 찾아 세번째 자리와 교환한다.

def Selection_Sort(nums):
    for i in range(len(nums)):
        mn=i
        for j in range(i+1, len(nums)):
            if nums[j]<nums[mn]:
                mn=j
        if mn==i:
            continue
        nums[mn], nums[i]=nums[i], nums[mn]
    return nums

Insert Sort

정렬되어 있는 부분 집합에 정렬할 새로운 원소의 위치를 삽입하는 방법으로 두개의 부분집합으로 나눈다.

• 부분집합 S: 정렬된 앞 부분의 원소들
• 부분집합 U: 정렬되지 않은 나머지 원소들

U의 원소를 하나씩 꺼내 S의 마지막부터 비교하며 S에서의 자리를 찾아 삽입한다. 반복될 수록 S의 크기는 증가하고, U의 크기는 감소하며 U가 공집합이 되면 정렬이 완료된다.

def Insert_Sort(nums):
    for i in range(len(nums)):
        key=nums[i]
        idx=i
        while idx>0 and key<nums[idx-1]:
            nums[idx]=nums[idx-1]
            idx-=1
        nums[idx]=key
    return nums

Quick Sort

전체 원소에 대한 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬을 수행하는 방법

• 왼쪽 부분 집합에는 기준값보다 작은 원소들로 채워지고, 오른쪽 부분 집합에는 기준값보다 큰 원소들로 채워진다.
• 기준값(피벗)은 보통 가운데 위치한 수로 지정된다.
• 정렬할 자료들을 피벗을 기준으로 두 부분 집합으로 분할한다. (분할)
• 부분 집합의 원소들 중에서 피벗보다 작은 원소들을 왼쪽 부분 집합으로, 큰 원소들을 오른쪽 부분 집합으로 정렬하고, 부분 집합의 크기가 1이하로 충분히 작지 않으면 재귀 호출을 통해 다시 분할한다. (정복)

def Quick_Sort(nums, start, end):
    if start>=end:
        return
    mid=(start+end)//2
    pivot=nums[mid]
    left, right=start, end
    while left<=right:
        while nums[left]<pivot:
            left+=1
        while nums[right]>pivot:
            right-=1
        if left<=right:
            nums[left], nums[right]=nums[right], nums[left]
            left+=1
            right-=1
    if start<right:
        Quick_Sort(nums, start, right)
    if end>left:
        Quick_Sort(nums, left, end)