[알고리즘] 정렬(Sorting) (1) 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

이것이 취업을 위한 코딩테스트다 with 파이썬

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

6장. 정렬

정렬 알고리즘 개요

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

- 이진 탐색의 전처리 과정

 

선택 정렬(Selection Sort)

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

선택 정렬 과정

Step 0. 초기 단계에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 '0'을 선택해 맨 앞의 '7'과 바꾼다

step 0

Step 1. 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택하여 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '5'와 바꾼다

step1

Step 2. 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택하여 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '5'와 바꾼다

step 2

Step 3. 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택하여 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '5'와 바꾼다

step 3

-- 중략 --

Step 8. 

Step 8

Step 9. 가장 작은 데이터를 앞으로 보내는 과정을 9번 반복한 상태는 다음과 같으며 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 따라서 이 단계에서 정렬을 마칠 수 있다.

Step 9

- 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료된다.

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, 2, 3, 4, 5, 6, 7, 8, 9]

스와프(Swap)

- 스와프(swap) : 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미

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

print(array)

# 출력
# [5, 3]

선택 정렬의 시간 복잡도

- O(N²) : 2중 반복문 사용되었기 때문

- 데이터의 개수가 10,000개 이상이면 속도가 느려짐

 

삽입 정렬(Insertion Sort)

- 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하여 정렬하는 것

- 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다

삽입 정렬 과정

Step 0. 첫 번째 데이터 7은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단한다. 7의 왼쪽으로 들어가거나 오른쪽으로 들어가는 두 경우만 존재한다. 오름차순 정렬 하고자하므로 7의 왼쪽에 삽입한다.

Step 1. 이어서 9가 어떤 위치에 들어갈지 판단한다. 삽입될 수 있는 위치는 총 3가지이며 현재 9와 5와 7보다 크기 때문에 원래 자리 그대로 둔다.

Step 2. 이어서 0이 어떤 위치에 들어갈지 판단한다. 0은 5, 7, 9와 비교했을 때 가장 작기 때문에 첫번째 위치에 삽입한다.

Step 3. 이어서 3이 어떤 위치에 들어갈지 판단한다. 0과 5 사이에 삽입한다.

-- 중략 --

Step 7.

Step 8.

Step 9. 이와 같이 적절한 위치에 삽입하는 과정을 N - 1번 반복하게 되면 다음과 같이 모든 데이터가 정렬된 것을 확인할 수 있다.

- 정렬이 이루워진 원소는 항상 오름차순을 유지하고 있다

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

for i in range(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²) : 2중 반복문 사용되었기 때문

- 리스트의 데이터가 거의 정렬되어 있는 최선의 경우 O(N)의 시간복잡도를 가지는 것이 가능하다.

 

퀵 정렬(Quick Sort)

- 정렬 알고리즘 중 가장 많이 사용되는 알고리즘

- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸어 정렬하는 것

- 피벗(Pivot) 사용 : 교환하기 위한 기준을 표현. 리스트에서 첫 번째 데이터를 피벗으로 정한다

퀵 정렬 과정

초기 데이터

< 파트 1 >

Step 0. 리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 5이다. 이후에 왼쪽에서부터 5보다 큰 데이터를 선택하므로 7이 선택되고, 오른쪽에서부터 5보다 작은 데이터를 선택하므로 4가 선택된다. 두 데이터의 위치를 서로 변경한다.

Step 1. 그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 찾은 뒤에는 두 값의 위치를 서로 변경하는데, 현재 9와 2가 선택되었으므로 이 두 데이터의 위치를 서로 변경한다.

Step 2. 그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾는다. 단 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 것을 알 수 있다. 이렇게 두 값이 엇갈린 경우에는 작은 데이터와 피벗의 위치를 서로 변경한다. 즉, 작은 데이터인 1과 피벗인 5의 위치를 서로 변경하여 분할을 수행한다.

Step 3. 분할 완료

이와 같이 피벗이 이동한 상태에서 5의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽은 모두 5보다 크다. 이렇게 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업을 분할(Divide) 혹은 파티션(Partition)이라고 한다.

< 파트 2 >

왼쪽 리스트에서 위와 같은 정렬을 진행한다.

< 파트 3 >

오른쪽 리스트에서 위와 같은 정렬을 진행한다.

- 재귀함수로 작성했을 때, 구현이 매우 간결해진다. 퀵 정렬이 끝나는 조건은 현재 리스트의 데이터 개수가 1인 경우이다.

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))

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

퀵 정렬의 시간 복잡도

- 평균 시간복잡도는 O(NlogN), 최악의 경우는 O(N²)

- 이미 데이터가 정렬되어 있는 경우에는 매우 느리게 동작한다

 

계수 정렬(Count Sort)

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

- 최악의 경우에도 수행시간 O(데이터의 개수 + 데이터의 최댓값) 을 보장한다.

- 특정한 조건 : 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때

계수 정렬 과정

- 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다. 처음에는 리스트의 모든 데이터가 0이 되도록 초기화 한다.

Step 0. 초기 단계 : 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

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

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

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

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

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

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

-- 과정 반복 --

Step 14. 7 5 9 0 3 1 6 2 9 1 4 8 0 5 2

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

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

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

- 결과적으로 위와 같이 리스트에는 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 인덱스를 출력하면 정렬된 결과를 확인할 수 있다.

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

# 모든 원소의 값이 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

계수 정렬의 시간 복잡도와 공간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최댓값의 크기를 K라고 할 때

- 시간 복잡도 : O(N + K)

- 공간 복잡도 : O(N + K)