필요성

저는 숫자를 다루는 일을 했다보니 다른 알고리즘보다 정렬 함수에 상대적으로 익숙한 편이었습니다.

그렇지만 결과가 나오는 방법을 기억하고 사용만해왔고, 어떻게 데이터를 정렬해주는지는 이해한 적은 한 번도 없었습니다.

책을 읽다보니 정렬 알고리즘에도 다양한 종류가 있고 알고리즘마다 시간 복잡도와 사용 상황이 다르더라구요.

효율적인 알고리즘 작성을 위해서 다양한 정렬 알고리즘을 이해하고, 주어진 데이터 상황에 알맞은 알고리즘을 사용하도록 해봅시다!

Quick Sort

퀵 정렬은 하나의 파일을 기준값(Pivot, 피봇)보다 작은 원소들과 큰 원소들로 분할하고, 기준값 왼쪽에 는 작은 원소들을 오른쪽에는 큰 원소들을 정렬하는 방법입니다. 기준값을 기준으로 더이상 분할할 것이 없을 때까지 반복합니다.

Divide & Conquer

분할 정복 방법이란 문제의 크기를 줄이기 위해 가장 간단한 기본 단계를 재귀방법으로 반복해서 답을 찾는 방법입니다.

구현

분할 정복 구현 방법은 두 가지만 기억하면 됩니다.

  1. 기본 단계 만들기: 해결 가능한 가장 간단한 문제를 생각하고 구현하기.
    • 배열을 다루는 재귀 함수를 만들 때, 보통 기본 단계는 원소의 개수가 0 또는 1인 배열입니다.
  2. 재귀 함수 사용해서 주어진 문제가 기본 단계가 될 때까지 나누어 작게 만들기.
    • 재귀 함수를 호출할 때마다 호출의 대상(예시> 배열)의 크기가 점점 작아지도록 구현합니다.

예시

한 list에 있는 원소들을 모두 더하려고 할때 for문을 사용하는 방법을 다음과 같이 사용할 수 있지만,

이때 분할 정복 방법을 다음처럼 사용한다면 재귀함수를 호출할 때마다 호출되는 array의 크기를 줄일 수 있습니다.

def quicksort(array):
    if len(array)<=1: #기본 단계
        return array
    else:
        pivot = array[0] # 우선 임의로 0으로 설정했지만, 원래는 기준 원소를 무작위로 선택합니다.
        								 # 사실은 pivot 값에 따라서 평균 O(nlog2n)에서 최대 O(n^2)까지 정렬 속도가 달라집니다.
        less = [i for i in array[1:] if i <= pivot]
        great = [i for i in array[1:] if i > pivot]

        return quicksort(less) + [pivot] + quicksort(great)
print(quicksort([10,5,2,3]))

Insertion Sort

삽입 정렬은 이미 순서화된 파일에 새로운 레코드를 순서에 맞게 정렬하는 방법이며, 앞의 n-1개의 데이터와 n번째 데이터를 비교해서 n번째 데이터가 최솟값이면 첫 번째 위치로 보내는 방법을 반복합니다.

Selection Sort

선택 정렬은 n개의 레코드 중에 최솟값을 찾아 첫 번째 위치로 보내고, 나머지 n-1개 데이터에서 최솟값을 찾아 두 번째 위치에 놓는 방법입니다.

Bubble Sort

버블 정렬은 인접한 두 개의 레코드 즉, n-1번째와 n번째 레코드를 비교하여 크기에 따라 레코드 위치를 바꾸는 과정을 반복하는 방법입니다.

Heap Sort

힙 정렬은 전 이진 트리(complete binary tree)를 heap tree로 변환하여 정렬하는 방법입니다.

  • 변환 방법

    자식 노드와 부모 노드 중 큰 것을 위로 올려서 모든 트리에서 만족하게 변환을 반복한다.

2-Way Merge Sort

2-Way 합병 정렬은 이미 정렬된 2개의 파일을 한 개의 파일로 합병하는 정렬 방식입니다.