Ch6 Sorting 6-1

📚 정렬(Sorting)

정렬(Sorting) 이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것.

• 프로그램을 작성할 때 가장 많이 사용되는 알고리리즘 중 하나.
• 이진 탐색의 전처리 과정 이기도 함.
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨.

1) 선택 정렬 (Selection Sort)

데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복.

• 가장 원시적인 방법으로 ‘가장 작은 것을 선택’ 한다는 의미.
• 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어짐.

선택 정렬 그림 설명

선택 정렬 소스코드 구현

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

for i in range(len(array)):
	min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
    	if array[min_index] > array[j]:
        	min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

print(array)

파이썬 스와이프

# 0 인덱스와 1 인덱스의 원소 교체하기
array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

실행 결과

0 1 2 3 4 5 6 7 8 9

선택 정렬의 시간 복잡도

• 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

• 구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다. 𝑁 + (𝑁 - 1) + (𝑁 - 2) + … + 2

• 이는 (𝑁² + 𝑁 - 2) / 2 로 표현할 수 있는데, 빅오 표기법에 따라서 O(N²) 이라고 작성한다.

선택 정렬을 사용하는 경우, 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려진다.

파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C 언어 기반, 다양한 최적화 테크닉이 포함되어 빠르게 동작한다.

선택 정렬은 기본 정렬 라이브러리와 다른 정렬 알고리즘에 비해 매우 비효율적이다.

---

2) 삽입 정렬 (Insertion Sort)

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

• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

• 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정.

• 두 번째 데이터부터 시작.
  • 첫 번째 데이터는 그 자체로 정렬되어 있기 때문이다.

삽입 정렬 그림 설명

삽입 정렬 소스코드

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

for i in range(1, len(array)):
	for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
    	if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
        	array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        	break

print(array)

실행 결과

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

삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N²) 이며, 선택 정렬과 마찬가지이다.

• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

• 최선의 경우 O(N)의 시간 복잡도를 가진다.

• 실행 시간 측면에서 선택 정렬에 비해 더 효율적.

• 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적.

  • 선택 정렬은 무조건 모든 원소를 비교하고 위치를 바꾼다.

---

3) 퀵 정렬 (Quick Sort)

정렬 알고리즘 중 가장 많이 사용 퀵 정렬과 병합 정렬은 빠르고, 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘.

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
• 피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵 정렬이 여러 가지 방식으로 구분된다.
  • 대표적 방식은 리스트의 첫 번째를 피벗으로 하는 호어 분할(Hoare partition)

    pivot : 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 ‘기준’

퀵 정렬 그림 설명

퀵 정렬 직관적 이해

퀵 정렬의 시간복잡도

• 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN) 를 기대할 수 있다.
  • 너비 X 높이 = 𝑁 × 𝑙𝑜𝑔𝑁 = 𝑁𝑙𝑜𝑔𝑁
  • 최악의 경우 O(N²) 의 시간 복잡도를 가진다.
  • 이미 데이터가 정렬되어 있는 경우 메우 느리게 동작한다. (삽입과 반대)

퀵 정렬 소스코드 구현

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복 
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

실행 결과

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

파이썬의 장점을 살린 구현

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

def quick_sort(array):
	# 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
    	return array
	
    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트
    
    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
    
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각자 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
print(quick_sort(array))

퀵 정렬과 다른 정렬 비교

---

4) 계수 정렬 (Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘

• 앞서 다뤘던 3가지 정렬 알고리즘처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식(비교 기반의 정렬 알고리즘)이 아니다.
• 데이터의 개수가 𝑁, 데이터(양수) 중 최댓값이 𝐾일 때 최악의 경우에도 수행 시간 O(N + K) 를 보장한다.
• 데이터의 크기가 제한되어 있을 때에 한해서 데이터의 개수가 매우 많더라도 빠르게 동작.
• 계수 정렬은 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 특징.
• 일반적으로 max와 min의 차이가 1,000,000을 넘지 않을 때, 효과적으로 사용할 수 있다.
  • ex) [0, 999999] 이런 상황에서는 계수 정렬 사용 x => 리스트의 크기가 100만 개가 되도록 선언해야 해서 비효율적임.
• 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합
  • ex) 성적의 경우 100점을 맞은 학생이 여러 명일 수 있기 때문에 이런 경우에선 효율적임.

계수 정렬 그림 설명

계수 정렬 결과

계수 정렬 소스코드 구현

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

실행 결과

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

---

5) 파이썬 정렬 라이브러리

sorted()

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

result = sorted(array)
print(result)

sort()

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

array.sort()
print(array)

key를 활용한 코드

array = [('바나나', 2), ('사과', 5), ('당근', 3)] # 리스트의 데이터가 튜플로 구성

def setting(data):
	return data[1] # 두 번째 원소를 기준으로 설정

result = sorted(array, key=setting)
print(result) # [('바나나', 2), ('당근', 3), ('사과', 5)]

정렬 라이브러리의 시간복잡도 이미 잘 작성된 함수이므로 직접 퀵 정렬을 구현할 때보다 훨씬 효과적

• 최악의 경우에도 O(NlogN) 보장.

• 병합 정렬과 삽입 정렬의 아이디어를 더한 알고리즘.

  단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용

코딩 테스트에서 정렬 알고리즘이 사용되는 경우

1. 정렬 라이브러리로 풀 수 있는 문제

• 단순히 정렬 기법을 알고 있는지 물어보는 문제.
  • 기본 정렬 라이브러리로 쉽게 풀 수 있음.

2. 정렬 알고리즘의 원리에 대해 물어보는 문제

• 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알아야 함.

3. 더 빠른 정렬이 필요한 문제

• 퀵 정렬 기반의 정렬 기법으로는 풀 수 없다. 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나, 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 함.