[이코테] chapter06 정렬

아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다.

정렬

: 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘

(1) 배경 지식

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

정렬은 다음 챕터에서 배울 이진 탐색의 전처리 과정이니 잘 알고 넘어가는 것이 중요하다.

정렬에는 종류가 매우 다양한데 이 장에서는 선택, 삽입, 퀵, 계수 정렬에 대해서만 다루겠다.

아래는 모두 무작위의 데이터를 오름차순으로 정렬하는 예제를 다룬다.

 

(2) 선택 정렬(Selection Sort)

: 가장 작은 것을 선택해, 정렬되지 않은 부분의 맨 앞에 두는 알고리즘

1️⃣예제

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

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

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

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

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

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

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

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

2️⃣소스코드

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)

3️⃣시간 복잡도

     선택 정렬은 N -1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 하고,

     매번 가장 작은 수를 찾기 위해 비교 연산이 필요하다.

     따라서 보통 N + (N - 1) + (N - 2) + ... + 2로 볼 수 있다.

     즉, N*(N+1)/2번의 연산을 수행하므로 빅오 표현법으로 아래와 같이 나타낼 수 있다.

O(N^2)

    물론 선택 정렬은 기본 정렬 라이브러리를 포함해, 매우 비효율적이다.

    그러나 특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 알아 두는 것이 좋다.

 

(3) 삽입 정렬(Insertion Sort)

: 특정한 데이터를 적절한 위치에 삽입하는 알고리즘

  첫 번째 데이터는 정렬 되어있다고 생각하므로 두 번째 데이터부터 정렬.

1️⃣예제

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

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

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

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

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

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

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

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

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

(10)    0 1 2 3 4 5 6 7 8 9  

2️⃣소스코드

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):
        if array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
        else:
            break
print(array)

3️⃣시간 복잡도

     선택정렬과 동일하게 두개의 중첩문으로 되어있어 시간복잡도는 아래와 같다.

O(N^2)

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

     따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제에서는 퀵정렬이나 다른 알고리즘보다 더 강력하다.

 

(4) 퀵 정렬(Quick Sort)

: 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

  퀵 정렬에서는 피벗(pivot)이 사용된다. 큰 숫자와 작은 숫자를 교환하기 위한 기준을 뜻한다.

  리스트에서 첫 번째 데이터를 피벗으로 정한다.

 

1️⃣예제

    아래의 예제에서 피벗은 분홍색, 피벗보다 큰 값은 남색, 작은 값은 연두색으로 나타내겠다.

    정렬이 완료된 값은 노란색으로 나타내겠다.

    (4)와 같이 큰 값과 작은 값이 엇갈린 경우 작은 값과 피벗을 바꾸어준다.
    그 뒤 5를 기준으로 왼쪽과 오른쪽을 같은 방법으로 퀵 정렬한다.

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

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

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

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

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

 

2️⃣소스코드

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

def quick_sort(array, start, end):
	if start >= end:
		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[right], array[left] = array[left], array[right]
       quick_sort(array, start, right - 1)
       quick_sort(array, right + 1, end)
       
 quick_sort(array, 0, len(array) - 1)
 print(array)

3️⃣시간 복잡도

      퀵정렬의 평균 시간 복잡도는 아래와 같다.

O(NlogN)

     

(5) 계수 정렬

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

  계수정렬은 앞서 다룬 3가지 정렬 알고리즘 처럼 직접 데이터 값을 비교한 뒤 위치를 변경하며 정렬하는 방식이 아니다!

  별도의 리스트를 선언하고, 그 안에 정렬에 대한 정보를 담는다.

 

1️⃣예제

    계수 정렬은 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성한다..

(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

(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

(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

(...)   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	1	2	3	4	5	6	7	8	9
2	2	2	1	1	2	1	1	1	2

출력결과: 0 0

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

출력결과: 0 0 1 1

...

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 6 7 8 9 9

 

2️⃣소스코드

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

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

3️⃣공간 복잡도

      계수 정렬의 공간 복잡도는 아래와 같다. (K는 데이터들 중 최댓값)

O(N + K)