📚 정렬 알고리즘

정렬(Sorting)이란?

이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 나열하는 작업이다.

데이터를 정렬하면 더욱 쉽고 빠르게 검색이 가능하다. 작은 데이터를 앞쪽에 두는 것을 오름차순(ascending order) 정렬이라 하고, 그 반대를 내림차순(descending order) 정렬이라고 한다.

정렬 알고리즘의 안정성

• 안정적인 알고리즘 : 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것
• 안정적이지 않은 알고리즘 : 정렬한 후에도 원래의 순서가 유지된다는 보장이 없는 것

내부 정렬과 외부 정렬

• 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
• 외부 정렬 : 정렬할 데이터가 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

버블 정렬(Bubble Sort)

이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다.

1) 이웃한 두 원소를 (n-1)번 비교하면 첫 번째 패스가 끝난다.
이때 가장 작은 원소가 맨 앞에 위치하게 된다.

2) 다음 패스에서는 맨 앞의 원소를 제외한 원소들을 (n-2)번 비교하여 두 번째로 작은 원소가 두 번째로 이동한다.

3) 마지막 원소까지 정렬(1번 비교)이 완료되면 정렬 작업이 종료된다.

버블 정렬은 서로 이웃한 원소만 교환하며, 원소를 비교하는 횟수는 다음과 같다.

(n-1) + (n-2) + ... + 2 + 1 = n (n-1) / 2

그런데 실제 원소를 교환하는 횟수는 배열의 원소들에 영향을 받기 때문에 평균값은 비교 횟수 전체의 절반인 n (n-1) / 4번이다.

버블 정렬 구현

def bubble_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]

• 알고리즘 개선 1 : 교환 횟수가 0이면 정렬이 완료된 것이므로 종료

def bubble_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        cnt = 0
        for j in range(n-1, i, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                cnt += 1 
        if cnt == 0:
            break

• 알고리즘 개선 2 : 특정 원소 이후에 교환이 이루어지지 않는다면 그 원소의 앞쪽은 이미 정렬된 것이므로 비교 범위를 줄임

def bubble_sort(a: MutableSequence) -> None:
    n = len(a)
    k = 0
    while k < n-1:
        last = n - 1
        for j in range(n-1, k, -1):
            if a[j-1] > a[j]:
                a[j-1], a[j] = a[j], a[j-1]
                last = j
        k = last

단순 선택 정렬 (Straight Selection Sort)

가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

단순 선택 정렬의 교환 과정

1) 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택한다.

2) a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환한다.

이 과정을 n-1번 반복하면 정렬이 완료된다.

단순 선택 정렬 구현

def selection_sort(a: MutableSequence) -> None:
    n = len(a)
    for i in range(n-1):
        min = i
        for j in range(i+1, n):
            if a[j] < a[min]:
                min = j
        a[i], a[min] = a[min], a[i]

단순 삽입 정렬 (Straight Insertion Sort)

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘

단순 삽입 정렬 방법

1) 맨 앞의 요소와 이웃한 요소를 비교하여 더 작은 요소를 맨앞에 둔다.

2) 세 번째 요소와 앞의 두 요소를 비교하여 적절한 위치에 둔다.

이 과정을 (n-1)번 반복하면 정렬이 완료된다.

단순 삽입 정렬의 종료

• 종료 조건 1
  정렬된 배열의 왼쪽 끝에 도달한 경우
  = 현재 원소가 가장 작은 경우

• 종료 조건 2
  tmp보다 작거나 키값이 같은 원소 a[j-1]을 발견할 경우
  = 현재 원소의 알맞은 위치를 찾은 경우