Chapter06. 정렬

ECC - 알고리즘/자료구조와 알고리즘 with 파이썬

Chapter06. 정렬

dlng23 2025. 5. 3. 19:03

06-1 정렬이란?

정렬: 순서가 없는 사물들을 순서대로 나열하는 것

무언가를 찾을 때, 효율적인 탐색을 위해 사용됨

정렬을 위해서는 서로 비교 가능해야 함

비교할 수 있는 모든 속성은 정렬의 기준이 될 수 있음

정렬 관련 용어

레코드(record): 정렬시켜야 할 대상

레코드는 여러 개의 필드(field)로 이루어짐

ex) 쇼핑몰에서 '상품'이란 레코드는 '이름', '가격', '제조' 등 다양한 필드를 가짐

키(key) or 정렬 키(sort key): 정렬의 기준이 되는 필드

정렬: 레코드들을 키(key)의 순서로 재배열하는 것

알고리즘이 단순하면 일반적으로 비효율적
ex) 삽입 정렬, 선택 정렬, 버블 정렬
효율을 높이기 위해서는 복잡한 알고리즘 사용해야 함
ex) 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬, 팀 정렬

안정성(stability)

입력 데이터에 같은 킷값을 갖는 레코드가 여러 개 있을 때, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것

제자리 정렬(in-place sorting): 입력 배열 이외에 추가적인 배열을 사용하지 않는 정렬

06-2 선택 정렬

선택 정렬(selection sort)

리스트에서 가장 작은 숫자를 하나씩 찾아 순서대로 저장하는 것

입력 리스트에서 가장 작은 값을 찾아 출력 리스트로 옮기는 과정을 입력 리스트가 공백 상태가 될 때까지 반복

선택 정렬의 문제점

정렬을 위해 입력 리스트 외에 추가적인 리스트가 필요

→ 제자리 정렬로 개선

최솟값이 선택되면 이 값을 출력 리스트에 저장하는 것이 아니라 입력 리스트의 첫 번째 요소와 교환

선택 정렬 알고리즘

선택 정렬 알고리즘(제자리 정렬 방식)

def selection_sort(A):
    n = len(A)  # 리스트의 크기
    for i in range(n-1): 
        least = i
        for j in range(i+1, n):
            if (A[j]<A[least]):
                least = j
        A[i], A[least] = A[least], A[i]    # A[i]와 A[least] 교환

외부 루프의 i는 정렬되지 않은 부분의 시작 인덱스로 0부터 n-2까지 순서대로 대입 됨

내부 루프의 최솟값을 찾는 범위는 i+1부터 n까지가 되어야 함

선택 정렬 테스트 프로그램

data = [6, 3, 7, 4, 9, 1, 5, 2, 8]
print("Original :", data)
selection_sort(data)
print("Selection :", data)

실행 결과

선택 정렬의 빠르기

선택 정렬의 비교 횟수

= (n-1) + (n-2) + (n-3) + … + (n-(n-2)) + (n-(n-1))

= (n-1) + (n-2) + (n-3) + … + 2 + 1

= (n(n-1))/2 ∈ O(n^2)

선택 정렬의 특징

알고리즘은 간단하지만, 시간 복잡도가 O(n^2)로 효율적이지 않음
안정성을 만족하지 않음
제자리 정렬로 추가적인 리스트가 필요하지 않음
자료의 구성에 상관없이 연산의 횟수가 결정된다는 장점이 있음
정렬할 리스트의 크기가 정해지면 리스트에 어떤 숫자가 어떻게 들어가 있는지와 무관하게 정렬에 걸릴 시간을 예측할 수 있음
리스트가 크지 않은 문제라면 충분히 사용할 수 있는 알고리즘

06-3 삽입

삽입 정렬(insertion sort)

정렬이 안 된 부분의 맨 앞의 숫자를 정렬된 부분의 적절한 위치에 끼워 넣는 과정을 정렬되지 않은 요소가 하나도 없을 때까지 반복

삽입 정렬 알고리즘

정렬된 부분 리스트에 요소를 끼워넣기 위해 해당 요소가 들어가야 할 정확한 위치를 찾아야 함

맨 앞의 요소부터 오른쪽으로 순서대로 움직이며 찾는 방법과 맨 뒤에서부터 앞으로 움직이며 찾는 방법 존재

두 방법 모두 같은 위치가 나오지만

두 번째 방법을 사용하면 비교할 때마다 정렬된 부분의 요소가 크면 그것을 한 칸 뒤로 미리 옮겨 놓을 수 있다는 장점이 존재

삽입 정렬 알고리즘

def insertion_sort(A):
    n = len(A)
    for i in range(1, n):   # i범위: 1 ~ n-1
        key = A[i]
        j = i-1
        while j >= 0 and A[j] > key:
            A[j + 1] = A[j]
            j -= 1
        A[j + 1] = key      # j+1이 A[i]가 삽입될 위치임

삽입 정렬의 빠르기

외부 루프는 항상 1에서 n-1까지 총 n-1 반복됨

내부 루프의 경우 입력 리스트의 자료가 어떤가에 따라 while 문이 한 번만에 끝날 수도, 여러 번 반복될 수도 있음

최선의 경우

입력 리스트가 이미 오름차순으로 정렬된 경우

while 문의 첫 번째 비교부터 조건을 만족하지 않아 한 번만에 빠져 나옴

외부 루프가 n-1번 반복, 내부 루프는 한 번만 처리됨

⇒ O(n)

최악의 경우

입력 리스트가 역순으로 정렬된 경우

끼워 넣을 위치가 항상 맨 앞이 되기때문에 while 문의 조건 검사를 항상 맨 앞까지 진행해야 함

A[i]를 삽입하기 위해 A[i-1]부터 A[0]까지 i개의 요소를 모두 비교해야 함

⇒ 삽입 정렬의 비교 횟수 = 1 + 2 + 3 + … + (n-2) + (n-1) = (n(n-1)) / 2 ∈ O(n^2)

삽입 정렬의 특징

입력의 구성에 따라 처리시간이 달라지는데, 최악의 상황에 대한 시간 복잡도가 O(n^2)로 효율적이지 않음
끼워 넣기를 위해 많은 레코드의 이동이 필요하므로 레코드의 크기가 큰 경우 선택정렬보다도 효율적이지 않음
제자리 정렬이고, 안정성도 충족
레코드 대부분이 이미 정렬된 경우라면 효율적으로 사용될 수 있음
최선의 경우에 대한 효율성이 매우 뛰어남

06-4 퀵 정렬

퀵 정렬(quick sort)

평균적으로 매우 빠른 수행 속도를 가짐

하나의 문제를 둘 또는 여러 개의 작은 부분 문제로 나누고, 부분 문제들을 각각 해결한 다음 결과를 모아서 원래의 문제를 해결하는 분할 정복 전략을 이용함

먼저 기준이 되는 값(pivot)을 선택하고 이 값보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 이동시킴 (퀵 정렬의 '분할'에 해당)

한 번의 분할이 끝나면 원래의 정렬 문제는 두 개의 문제로 나누어짐

이 작아진 문제들에 같은 분할과정을 적용하여 계속 분할을 하다가 크기가 1이 되면 이미 정렬된 것이므로 분할이 종료됨

퀵 정렬 알고리즘

def quick_sort(A, left, right):
    if left<right:      # 정렬 범위가 2개 이상인 경우
        q = partition(A, left, right)
        quick_sort(A, left, q-1)
        quick_sort(A, q+1, right)

partition() : 입력 리스트를 임의의 기준으로 나누고 그 기준의 위치(인덱스)를 반환하는 함수

분할

부분 리스트들의 내부가 정렬될 필요는 없음

피벗(pivot)을 중심으로 분리만 하면 됨

분할의 아이디어: 탐색-교환 과정을 반복

정렬할 리스트 A의 시작과 마지막 인덱스 left, right 가 주어지면

피벗을 선택하고 두 인덱스 low, high 준비 → 각각 왼쪽과 오른쪽 부분 리스트를 만드는 데 사용됨

(low = left + 1, hight = right로 초기화됨)

탐색: low를 오른쪽으로 high를 왼쪽으로 진행하면서 조건에 맞지 않는 요소를 찾는 과정

왼쪽 부분 리스트: A[low] <= pivot → 왼쪽 부분 리스트에 적합, low를 오른쪽으로 전진시키다가 A[low] > pivot 일 때 멈춤
오른쪽 부분 리스트: A[hight] > pivot → high를 왼쪽으로 전진시키다가 A[high] < pivot 이면 멈춤

low와 high 모두 조건이 맞지 않아 탐색이 중지되면 A[low]와 A[high] 교환

교환 후 다시 탐색 진행

위 과정을 반복하다 low와 high가 역전되면 탐색-교환 과정 종료

high 이하의 항목들은 피벗 이하의 값을 갖고, low 이상의 항목들은 피벗보다 큰 값을 가짐

pivot을 두 부분 리스트의 중앙으로 옮기기만 하면 됨 → 피벗과 high의 항목 교환

분할 알고리즘

def partition(A, left, right):
    pivot = A[left]
    low = left + 1
    high = right

    while (low < high):     # low와 high가 역전되지 않는 한 반복
        while low <= right and A[low] <= pivot:
            low += 1        # A[low]<=pivot이면 low를 오른쪽으로 진행

        while high >= left and A[high] > pivot:
            high -= 1       # A[high]>pivot이면 high를 왼쪽으로 진행
        
        if low < high:      # 역전이 아니면 두 레코드 교환
            A[low], A[high] = A[high], A[low]

    A[left], A[high] = A[high], A[left]
    return high

퀵 정렬의 빠르기

partition() 함수의 경우 외부 반복문 안에 있는 내부 반복문에서 사용된 비교 연산(피벗과 항목의 비교)이 가장 많이 반복됨

피벗을 제외한 모든 요소는 피벗과 반드시 한 번씩 비교되어야 함

전체 요소의 수가 n이라면 n-1번의 비교 필요

퀵 정렬은 입력의 구성에 따라 효율이 달라짐

최선의 경우

분할이 항상 리스트의 중앙에서 이루어지는 경우

n이 2의 거듭제곱이라고 가정하면 부분 리스트의 크기는 레벨에 따라 n/2, n/4 ... 처럼 절반으로 줄어듦

순환 호출 트리의 높이 k = log2(n)이 됨

트리의 각 레벨에서 여러 번의 partition()함수가 실행되는데, 하나의 레벨에서 피벗을 제외한 모든 요소를 비교해야 하므로 최대 n번의 비교 필요

⇒ 전체 비교 연산 횟수 n*k = nlog2(n)

O(nlog2(n))

최악의 경우

리스트가 계속 1, n-1 / 1, n-2 ... 와 같이 불균형하게 나누어지는 경우

위와 같이 불균형하게 나누어지는 경우 순환 호출의 깊이가 n이 되므로 전체 비교 연산의 수는 n^2에 비례하게 됨

⇒ O(n^2)

퀵 정렬의 특징

퀵 정렬은 제자리 정렬이지만 안정성은 만족하지 않고 최악의 경우는 O(n^2)인 알고리즘인데

그럼에도 왜 quick 정렬이란 이름을 갖게 된 것일까?

최악의 경우는 좋지 않지만, 평균적인 경우는 최선의 경우에 비해 추가적인 연산이 39% 정도만 늘어남
결국 평균적으로는 최선의 입력과 비슷한 속도가 나옴
병합 정렬이나 힙 정렬과 같은 다른 알고리즘과 비교해도 매우 빠른 것으로 알려져 있음
그 이유는, 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환하며, 한번 결정된 피벗들이 추후 연산에서 제외되는 등의 특징 때문
퀵 정렬의 성능을 더 개선하려는 방법으로 불균형 분할을 완화하기 위해 피벗을 리스트의 중앙값에 가깝도록 선택하는 방법이 있음
ex) 리스트의 왼쪽, 오른쪽, 중간의 3개의 요소 중에서 중간값을 선택하는 방법(median of three)이 많이 사용됨

06-5 기수 정렬

지금까지 다룬 리스트의 요소를 '비교'하여 정렬하는 알고리즘들을 비교 기반 정렬이라 부름

킷값을 비교하지 않고도 효율적인 비교 기반 정렬들보다 이론적으로 더 빨리 정렬할 수 있는 기수 정렬(radix sort) 방법이 존재

기수(radix): 숫자의 자릿수

기수 정렬은 자릿수의 값에 따라서 정렬함

여러 개의 큐 구조인 버킷(bucket)을 사용하여 값들을 적절히 배분해 놓았다가 순서대로 다시 모아 정렬

한 자리 자연수의 정렬

[8, 2, 7, 3, 5]를 정렬

십진수는 각 자리가 0에서 9까지의 값을 가지므로 10개의 버킷을 준비해야 함

버킷들이 준비되면 입력 데이터를 값에 따라 버킷에 넣음 (ex. 8 → 8번 버킷, 2 → 2번 버킷 ... )

모든 숫자를 넣은 후 0번 버킷부터 시작하여 9번 버킷까지 순차적으로 버킷 안의 모든 숫자를 출력

⇒ [2, 3, 5, 7, 8]을 얻음

여러 자리 자연수의 정렬

[28, 93, 39, 81, 62, 72, 38, 26]을 정렬

가장 간단한 방법은 0~99번까지의 100개의 버킷을 사용

그러나, 1의 자리와 10의 자리를 따로따로 정렬함으로써 더 적은 버킷을 사용하여 효과적으로 정렬할 수 있음

입력 데이터: [28, 93, 39, 81, 62, 72, 38, 26]
1의 자리로 정렬	[81, 62, 72, 93, 26, 28, 38, 39]	10의 자리로 정렬	[28, 26, 39, 38, 62, 72, 81, 93]
10의 자리로 정렬	[26, 28, 38, 39, 62, 72, 81, 93] 정렬 성공	1의 자리로 정렬	~~[81, 62, 72, 93, 26, 28, 38, 39]~~ 정렬 실패

낮은 자리 수를 먼저 처리하고 다음에 높은 자릿수를 처리하면 성공적으로 정렬되는 것을 알 수 있음

십진법을 사용한다면 버킷은 항상 10개가 필요
만약 같은 입력을 2진수로 생각하고 정렬한다면 버킷은 2개만 있으면 됨. 그러나 이 경우 필요한 패스 수가 훨씬 많아지게 됨
버킷에 먼저 들어간 숫자가 먼저 나와야 함. 레코드들의 상대적인 순서가 유지되어야 하기 때문
따라서 버킷은 큐로 구현됨
버킷에 숫자를 넣는 것은 큐의 삽입(enqueue) 연산에 해당, 버킷에서 숫자를 읽는 연산은 큐의 삭제(dequeue) 연산에 해당

기수 정렬 알고리즘

기수 정렬 알고리즘

from collections import deque   # collections 모듈의 deque을 사용

def radix_sort(A):
    queues = []
    for i in range(BUCKETS):
        queues.append(deque())

    n = len(A)
    factor = 1                  # 가장 낮은 자리부터 시작
    for d in range(DIGITS):     # 각 자릿수에 대해 처리
        for i in range(n):      # 모든 항목을 따라 큐에 삽입
            queues[(A[i]//factor) % BUCKETS].append(A[i])
        
        i = 0
        for b in range(BUCKETS):
            while queues[b]:
                A[i] = queues[b].popleft()
                i += 1
        factor += BUCKETS       # 그다음 자릿수로 간다.
        print("step", d+1, A)   # 처리과정 출력용 문장

리스트의 각 항목 A[i]에 대해 해당 버킷을 결정하여 추가. 해당 버킷은 A[i]를 factor로 나눈 몫(A[i]//factor)의 1의 자리(%BUCKETS)

factor에 버킷의 수 BUCKETS를 곱해 다음 자릿수에 대해 처리함

기수 정렬 테스트 프로그램

import random       # 난수 발생을 위해 random 모듈 포함 
BUCKETS = 10        # 10진법 사용
DIGITS = 4          # 최대 4자릿수 숫자를 정렬함함

# 리스트 내포(list comprehension)로 난수 10개로 이루어진 리스트 생성
data = [random.randint(1, 9999) for _ in range(10)]
radix_sort(data)
print("Radix:", data)

실행 결과

기수 정렬의 빠르기

외부 루프는 리스트의 크기와 상관없이 최대 자릿수만큼 반복됨

최대 자릿수: d

내부 반복문은(11행) 입력 리스트의 크기인 n번 반복되고 다른 반복문(15~16행)도 모든 버킷에 들어 있는 요소의 수 n만큼 반복됨

⇒ dn에 비례하는 시간이 걸림

기수 정렬의 특징

비교 기반 정렬의 이론적인 하한선을 깰 수 있음

아무리 좋은 비교 기반 정렬 알고리즘도 nlog2(n)에 비례하는 시간 이상 걸리는 것으로 알려져 있는데,

기수 정렬은 O(dn)의 복잡도를 가짐. d는 단계의 수인데, 대부분은 크지 않은 값을 가짐

치명적인 단점도 존재

정렬에 사용되는 킷값이 자연수로 표현되어야만 적용할 수 있음
만약 리스트의 요소가 실수이거나 한글, 한자라면 적용이 어려움
버킷을 위한 추가적인 메모리가 필요
많은 공간을 확보해놓고 처리시간을 줄이는 방법에 해당 ('공간을 팔아서 시간을 버는' 전략을 사용한 알고리즘)

06-6 파이썬의 정렬함수 활용하기

파이썬에서 제공하는 정렬함수를 이용할 수 있음

리스트의 sort() 메서드

파이썬의 리스트는 정렬을 위해 sort() 메서드 제공

sort(): 리스트를 오름차순으로 정렬

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

data.sort()

⇒ data: [1, 2, 3, 4, 5, 6, 7, 8, 9]

만약 리스트를 역순으로 정렬하고 싶다면 키워드 인수인 reverse를 True로 설정하면 됨

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

data.sort(reverse=True)

⇒ data: [9, 8, 7, 6, 5, 4, 3, 2, 1]

파이썬의 내장 함수 sorted()

파이썬에 내장된 함수인 sorted는 오름차순으로 정렬된 새로운 리스트를 반환함

원래의 리스트(data)는 수정되지 않음

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

result = sorted(data)

⇒ data: [6, 3, 7, 4, 9, 1, 5, 2, 8] / result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

키워드 인수 reverse를 사용하여 내림차순으로도 정렬할 수 있음

result = sorted(data, reverse=True)

⇒ result: [9, 8, 7, 6, 5, 4, 3, 2, 1]

복잡한 레코드의 정렬

만약 정렬해야 하는 대상이 정수나 실수와 같은 단순한 값이 아니라 복잡한 레코드인 경우

예를 들어, 다음과 같은 3차원 공간상의 점들이 리스트인 경우

data = [(62, 88, 81), (50, 3, 31), (86, 53, 42), (73, 47, 4), (89, 9, 8), (47, 88, 55), (19, 18, 20), (15, 1, 88), (90, 6, 60), (41, 92, 19)]

data의 각 항목은 점의 좌표 (x, y, z)를 나타내는데, 파이썬의 튜플(tuple)로 저장되어 있음

하나의 레코드에 3개의 필드가 있으므로, 정렬을 위해서는 기준을 정해야 함

ex)

기준 1: x값의 오름차순으로 정렬
기준 2: y값의 내림차순으로 정렬
기준 3: 크기의 오름차순으로 정렬. 이때 크기는 sqrt(x^2 + y^2 + z^2)

파이썬의 정렬 함수는 정렬의 기준을 지정하기 위해 키워드 인수 key를 제공

key에 정렬 기준을 반환하는 함수를 지정

예를 들어, 기준 1과 같이 x값으로 정렬하기 위해서 다음과 같이 레코드에서 키(해당 필드)를 반환하는 함수를 만들고, 키워드 인수에서 그 함수를 지정하면 됨

def keyfunc(p):		# 레코드 p에서 키를 반환하는 함수. p=(x,y,z)
	return p[0]	# p의 첫 번째 요소(p[0], x값)를 키로 반환
    
print("data :", data)
x_inc = sorted(data, key = keyfunc)
print("x_inc :", x_inc)

실행 결과

data : [(62, 88, 81), (50, 3, 31), (86, 53, 42), (73, 47, 4), (89, 9, 8), (47, 88, 55), (19, 18, 20), (15, 1, 88), (90, 6, 60), (41, 92, 19)]
x_inc : [(15, 1, 88), (19, 18, 20), (41, 92, 19), (47, 88, 5 5), (5이, 3, 31), (62, 88, 81), (73, 47, 4), (86, 53, 42), (89, 9, 8), (90, 6, 60)]

람다 함수를 이용한 키 지정

람다식은 def 키워드로 작성되지 않고 lambda란 키워드로 만드는 특별한 함수

형식: lambda 인자(argument) : 식(expression)

lambda p: p[0] 		# 리스트나 튜플 p에서 0번째 항목 반환

# 위의 코드를 적용하여 기준 1로 정렬하는 코드
x_inc = sorted(data, key = lambda p: p[0])

# 기준 2를 이용해서 정렬, 내림차순 정렬
y_dec = sorted(data, key = lambda p: p[1], reverse=True)

print("data :", data)
print("y_dec :", y_dec)

실행 결과

data : [(62, 88, 81), (50, 3, 31), (86, 53, 42), (73, 47, 4), (89, 9, 8), (47, 88, 55), (19, 18, 20), (15, 1, 88), (90, 6, 60), (41, 92, 19)]
y_dec : [41, 92, 19), (62, 88, 81), (47, 88, 55), (86, 53, 42), (73, 47, 4), (19, 18, 20), (89, 9, 8), (90, 6, 60), (50, 3, 31), (15, 1, 88)]

기준 3으로 정렬

import math
magni = sorted(data, key= lambda p: math.sqrt(p[0]*p[0]+p[1]*p[1]+p[2]*p[2]))
print("data :", data)
print("magni :", magni)

실행 결과

data : [(62, 88, 81), (50, 3, 31), (86, 53, 42), (73, 47, 4), (89, 9, 8), (47, 88, 55), (19, 18, 20), (15, 1, 88), (90, 6, 60), (41, 92, 19)]
magni : [(19, 18, 20), (50, 3, 31), (73, 47, 4), (15, 1, 88), (89, 9, 8), (41, 92, 19), (90, 6, 60), (86, 53, 42), (47, 88, 55), (62, 88, 81)]