정렬 알고리즘 - 선택정렬, 삽입정렬, 퀵정렬, 계수정렬(카운트정렬)

정렬이란?

데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말합니다. 작은 숫자순으로 정렬하는 것을 내림차순 큰 숫자순으로 정렬하는 것을 오름차순 정렬이라고 합니다. 정렬알고리즘은 다양하지만 이번 포스트에서 선택정렬, 삽입정렬, 퀵정렬, 계수 정렬에 대해 설명하겠습니다.

 

선택정렬

선택 정렬은 말 그대로 선택한 값과 선택되지 않은 값 중 가장 작은 데이터와 바꾸는 정렬입니다.

예를 들어 1,3,2,4,5,0 이라는 리스트가 존재할 때 

1. 가장 처음 자리 숫자인 1을 선택하고 선택되지 않은 값 중 가장 작은 값인 0과 자리를 바꿔줍니다. 0,3,2,4,5,1

2. 두번 째 자리 숫자인 3을 선택하고 선택되지 않은 값 중 가장 작은 값인 1과 자리를 바꿔줍니다. 0,1,2,4,5,3

3. 세번 째 자리 숫자인 2을 선택하고 선택되지 않은 값 중 가장 작은 값이 2보다 크므로 넘어갑니다. 0,1,2,4,5,3

4. 네번 째 자리 숫자인 4을 선택하고 선택되지 않은 값 중 가장 작은 값이 3과 자리를 바꿔줍니다. 0,1,2,3,5,4

5. 다섯번 째 자리 숫자인 5을 선택하고 선택되지 않은 값 중 가장 작은 값이 4과 자리를 바꿔줍니다. 0,1,2,3,4,5

이 처럼 선택 정렬은 데이터가 N개 존재할 때 N-1 씩 반복하는 것을 알 수 있습니다.

 

코드로 표현

a = [1,3,2,4,5,0]

for i in range(len(a)):
    min_idx = i
    for j in range(i+1,len(a)):
        if a[min_idx] > a[j]:
            min_idx = j
        a[i],a[min_idx] = a[min_idx],a[i]
print(a)

 

 

리스트 길이에서 순서대로 min_idx 설정한 뒤 두번 째 for 문을 통해 이후 값 중에서 가장 작은 idx 를 찾은 뒤 두 숫자를 바꿔줍니다.

 

시간복잡도

현재 N-1을 반복하지만 for 문을 두개 사용하였기 때문에 빅오 표기법으로는 간단하게 N^2으로 표현할 수 있습니다.  정렬할 리스트가 작을 경우 상관없지만 만약 10000개의 숫자가 있는 리스트를 정렬해야할 경우 속도가 오래걸려 비효율적인 면이 있습니다.

 

삽입정렬

삽입정렬은 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입하는 정렬 알고리즘입니다. 특징으로는 맨 처음 데이터는 정렬이 되어있다고 가정합니다.

예를 들어 1,3,2,4,5,0 이라는 리스트가 존재할 때 

1. 두번 째 자리 숫자인 3이 1보다 크므로 오른쪽 자리에 값을 삽입합니다. 1,3 | 2,4,5,0

2. 세번 째 자리 숫자인 2가 1,3 중에서 삽입할 위치를 판단하게 되는데 1보다 크고 3보다 작으므로 사이에 삽입이 됩니다.1,2,3, |4,5,0

3. 네번 째 자리 숫자인 4가 1,2,3 중에서 가장 크므로 맨 오른쪽에 삽입하게 됩니다. 1,2,3,4, |5,0

4. 다섯번 째 자리 숫자인 5가 1,2,3,4 중에서 가장 크므로 맨 오른쪽에 삽입하게 됩니다. 1,2,3,4,5 |0

5. 여섯 번째 자리 숫자인 0이 1,2,3,4,5 중에서 가장 작으므로 맨 왼쪽에 삽입하게 됩니다. 0,1,2,3,4,5

 

코드로 표현

a = [1,3,2,4,5,0]


for i in range(1,len(a)):
    for j in range(i,0,-1):
        if a[j] < a[j-1]:
            a[j],a[j-1] = a[j-1],a[j]
        else:
            break

print(a)

시간복잡도

for 문을 두개 사용하였기 때문에 빅오 표기법으로는 간단하게 N^2으로 표현할 수 있습니다. 하지만 리스트가 정렬이 거의 다 되어있는 경우 N의 시간 복잡도를 가진다는 특징이 있습니다.

 

퀵정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 알고리즘입니다. 퀵정렬에서는 피벗이라는 것을 사용하게 됩니다. 큰 숫자와 작은 숫자를 비교하기 위한 기준 값이라고 생각하면 됩니다. 여러가지 퀵정렬 방식이 있지만 호어 분할방식으로 설명하겠습니다.

호어 방식에서는 리스트에서 첫번째 데이터를 피벗으로 정하게 됩니다.

예를 들어 1,3,2,4,5,0 이라는 리스트가 존재할 때 

크게 3가지로 분류해서 생각하면 쉽습니다. 기준 점, 기준점으로 왼쪽 값(피벗보다 작은 값), 기준점으로 오른쪽 값(피벗보다큰 값)

한번 진행한 후 재귀함수 호출을 통해 피벗기준 왼쪽 값들 정렬, 똑같이 오른쪽 값들도 정렬한 후 합치면 됩니다.

1. 1이 피벗으로 설정되고 왼쪽에는 1보다 작은 값 0 이 삽입되고 오른쪽에는 1보다 큰 값 3,2,4,5가 삽입되게 됩니다. 0 | 1 | 3,2,4,5

2. 1을 기준으로 왼쪽 0은 더이상 정렬할 필요가 없고 오른쪽에서는 3을 피벗으로 설정하게 됩니다. | 3 |

3. 3보다 작은 값 2가 피벗 왼쪽에 삽입 4,5가 피벗 오른쪽에 삽입하게 됩니다. 0,1 //  2 | 3 | 4,5

4. 더 이상 정렬할 필요가 없으므로 정렬을 종료합니다. 0,1,2,3,4,5

 

코드로 표현

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[0]
    tail = arr[1:]
    left = [x for x in tail if x<= pivot]
    right = [x for x in tail if x> pivot]

    return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(a))

첫 숫자를 피벗으로 설정하고 피벗 기준 왼쪽과 오른쪽 값을 넣어준 뒤 재귀함수를 통해 더 이상 정렬하지 못할 때 까지 반복하고 리스트를 반환합니다.

 

시간복잡도

퀵정렬은 NlogN의 복잡도를 가지고 있어 앞에서 설명한 삽입정렬과, 선택정렬보다 훨씬 빠르게 동작합니다. 그 이유는 간단하게 피벗을 기준으로 쪼갠 뒤 재귀 함수를 반복해서 호출해도 호출할 때마다 정렬할 데이터가 계속해 줄기 때문이라고 생각하면 편합니다.

 

계수정렬(count sort)

앞에서 설명한 알고리즘과 다르게 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 알고리즘입니다. 이름 처럼 해당 숫자에 대한 인덱스에 계수를 세서 저장하는 리스트를 만든다고 생각하면 쉽습니다. 또한 계수정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현될 때 사용할 수 있습니다. 

예를 들어 1,3,2,4,5,0 이라는 리스트가 존재할 때  최소 숫자 0 최고숫자 +1 에 해당하는 인덱스 리스트를 만듭니다.

1. 0,1,2,3,4,5 이라는 리스트가 존재할 때 첫번 째 위치에 해당하는 숫자인 1이 있으므로 1위치에 +1을 기록합니다.

0	1	2	3	4	5
0	1	0	0	0	0

2. 0,1,2,3,4,5 이라는 리스트가 존재할 때 두번 째 위치에 해당하는 숫자인 3이 있으므로 3위치에 +1을 기록합니다.

0	1	2	3	4	5
0	1	0	1	0	0

3. 0,1,2,3,4,5 이라는 리스트가 존재할 때 세번 째 위치에 해당하는 숫자인 2가 있으므로 2위치에 +1을 기록합니다.

0	1	2	3	4	5
0	1	1	1	0	0

4. 0,1,2,3,4,5 이라는 리스트가 존재할 때 네번 째 위치에 해당하는 숫자인 4가 있으므로 4위치에 +1을 기록합니다.

0	1	2	3	4	5
0	1	1	1	1	0

4. 0,1,2,3,4,5 이라는 리스트가 존재할 때 다섯번 째 위치에 해당하는 숫자인 5가 있으므로 5위치에 +1을 기록합니다.

0	1	2	3	4	5
0	1	1	1	1	1

4. 0,1,2,3,4,5 이라는 리스트가 존재할 때 여섯번 째 위치에 해당하는 숫자인 0이 있으므로 0위치에 +1을 기록합니다.

0	1	2	3	4	5
1	1	1	1	1	1

이 숫자들을 인덱스 순서대로 카운트 된 숫자만큼 반환하면 0,1,2,3,4,5가 반환되어 정렬이 된 것을 확인 할 수 있습니다.

 

코드로 표현

a = [1,3,2,4,5,0]

count = [0] * (max(a)+1)
for i in range(len(a)):
    count[a[i]] +=1

for i in range(len(count)):
    for j in range(count[i]):
        print(i,end='')

count 리스트에 해당 숫자에 해당하는 위치에 +1 을 해줍니다.

count 리스트에서 해당 카운트 개수만큼 출력하고 카운트 개수만큼 출력을 다했으면 다음 인덱스에 해당하는 숫자를 카운트만큼 출력합니다.

 

시간복잡도

계수 정렬은 데이터 개수 N, 데이터 중 최대 값 크기 K일 때 빅오 표현법으로 N+K 만큼의 시간이 소요됩니다. 하지만 계수 정렬에서 데이터의 가장 큰 숫자만큼 표현하는 리스트를 만들어야 하기 때문에 0과 100000이라는 두개의 숫자를 정렬하려면 0부터 100000의 크기에 해당하는 리스트를 만들어야하기 때문에 메모리를 낭비하는 문제가 생길 수 있습니다. 따라서 데이터 크기가 한정되어 있고 많은 중복이 되어있을 때 사용하면 좋은 알고리즘입니다.