[알고리즘] 정렬 알고리즘

정렬 알고리즘이란?

정렬 알고리즘 이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 정렬을 위한 알고리즘들을 뜻한다.
정렬 알고리즘은 다양한 종류가 있는데,

• 선택정렬(Selection Sort)
• 삽입정렬(Insertion Sort)
• 퀵 정렬(Quick Sort)
• 계수 정렬(Count Sort)

위의 정렬 알고리즘에 대해 정리하고자 한다. 위의 알고리즘들을 선택한 기준은..
📚『이것이 코딩테스트다 with 파이썬』 에 나오기 때문이다.. ㅎㅎ

이외에도 병합 정렬(Merge Sort), 기수 정렬(Radix Sort)등이 있는데, 이것들은 나중에 정리하기로 한다.

---

선택정렬(Selection Sort)

선택정렬은 단순하게 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 이 데이터를 제외하고 다시 같은 과정을 반복함을 통해서 정렬하는 알고리즘 이다.
가장 작은 것을 선택해서 앞으로 보내는 과정을 반복한다고 생각하면 쉽다.

code

array = [7,5,3,6,4,1,2,9,0,8]
# selection sort(ascending)
for i in range(len(array)):# n-1번 반복
    # 가장 작은 수 찾아서 앞으로
    min_idx = i
    for j in range(i, len(array)):
        if array[min_idx] > array[j]:
            min_idx=j
    #swap
    array[i], array[min_idx] = array[min_idx], array[i]

시간복잡도: O(N^2)
선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정 O(N)을 N-1번 하면 정렬이 완료되므로 O(N^2)의 시간복잡도를 가진다.

---

삽입정렬 (Insertion Sort)

삽입정렬은 특정한 데이터를 적절한 위치에 '삽입'하므로 삽입 정렬이라고 부른다.
삽입정렬은 두번째 데이터 부터 시작하고, 특정 데이터 앞까지의 데이터는 정렬된 상태라고 가정한다.

따라서, 두번째 데이터 부터 시작하여 첫번째 원소와 비교하고, 보다 작으면 앞에 삽입한다.
정렬시 현재 비교하고 있는 데이터의 앞에는 이미 정렬된 형태이므로, 오름차순으로 정렬되어 있다고 가정 시 가장 큰 오른쪽 데이터 부터 차례로 비교하고, 자리를 바꾸는 것을 반복하면 최적의 위치에 데이터를 삽입하게 된다.
이 과정을 N-1번 반복하면, 정렬이 완료된다.

code

array = [7,5,3,6,4,1,2,9,0,8]
# Insertion sort(ascending)
for i in range(1,len(array)):# n-1번 반복
    print('sorted', array[:i])
    for j in range(i, 0, -1):
        print('i,j', i, j)
        if array[j] > array[j-1]: #현재 비교하는 데이터가 더 크면 그 자리에서 stop
            break
        array[j],array[j-1] = array[j-1],array[j]

시간복잡도: O(N^2)
데이터가 이미 정렬되어 있는 경우, O(N)까지 빨라져 효율적이다.

---

퀵 정렬 (Quick Sort)

퀵 정렬은 이름에서도 알 수 있듯, 정렬 알고리즘 중에 빠른 축에 속한다.
퀵 정렬은 기준 데이터(pivot)을 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 는 동작방식으로 구현된다.

피벗(pivot)을 설정하고 리스트를 분할하는 방법도 여러가지가 있는데, 가장 대표적인 방식은 호어 분할 방식으로 가장 첫번째 데이터를 피벗으로 선정한다는 방식이다.

따라서, 퀵정렬은 아래와 같은 방식으로 이루어진다.

1. 리스트에서 피벗을 설정(가장 첫번째 data)
2. 피벗을 제외, 왼쪽부터 탐색하여 피벗보다 큰 값 찾기
3. 피벗을 제외, 오른쪽 부터 탐색하여 피벗보다 작은 값 찾기
4. 피벗보다 큰 값과 피벗보다 작은 값의 위치를 swap한다. 단, 둘의 위치가 엇갈린 경우 피벗보다 작은 값과 피벗의 위치를 swap한다.
5. 위 과정을 통해 피벗을 기준으로 나뉜 왼쪽 리스트와 오른쪽 리스트에 대해 각각 같은 과정을 반복한다. => 각 리스트의 데이터 개수가 1개가 될 때까지 반복( 전체 리스트 정렬될 때 까지 )

code

array=[5,7,3,6,4,9,0,8,1,2]
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: #엇갈리지 않은 경우 -- 작은값(right)과 큰값(left)교체
            array[left], array[right] = array[right], array[left]
        
    #분할 이후(right --작은값위치에 pivot들어옴) 기준 왼쪽, 오른쪽도 sort
    quick_sort(array, start, right-1) 
    quick_sort(array, right+1, end)

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

퀵 정렬이 이루어지는 과정을 잘 생각한다면, 코드의 구조도 피벗보다 작은값과 큰 값을 찾아 리스트를 분할하고, 각 리스트에 대해 이를 반복하는 재귀함수의 구조가 잘 이해될 것이다.

시간복잡도: O(NlogN)
퀵 정렬의 평균 시간복잡도는 O(NlogN) 이다.
이는 배열이 절반씩 분할되는 경우를 생각해보면 이해가 쉽다. 길이가 8인 배열이 있다면, 분할된 리스트의 길이가 1이 될 때까지 리스트를 분할하는 횟수는 3 == log8이 된다.

하지만, 퀵정렬이 느린 경우도 있는데, 데이터가 이미 정렬되어 있는 경우이다. 이 경우에는, 가장 왼쪽 데이터를 피벗으로 삼게 되면 O(N^2)의 시간복잡도로 비효율적이다.

---

계수 정렬 (Count Sort)

계수 정렬은 위에서 설명한 알고리즘들과 달리, 비교 기반의 정렬알고리즘이 아니다. 계수 정렬은 특정 조건이 부합할 때만 사용이 가능하지만, 매우 빠른 정렬 알고리즘이다.

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

계수 정렬은 모든 범위의 데이터를 담을 수 있는 크기의 리스트를 선언하고, 이 리스트를 통해 정렬을 한다. 따라서, 일반적으로 가장 큰 데이터와 가장 작은 값의 차이가 1,000,000을 넘지 않을 때, 효과적으로 사용할 수 있다.

데이터의 모든 범위를 커버하는 리스트를 별도로 선언하고, 모든 데이터를 탐색하면서 해당 데이터 값의 인덱스에 값을 더한다. 이렇게 하면, 별도로 선언한 배열 자체가 정렬된 형태가 된다.

code

"""
계수정렬
조건: 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
=> 매우 빠르다. 
데이터 개수 == N, 데이터 중 최댓값==K 일 때, O(N+K) 보장.

일반적으로 가장 큰 데이터와 가장 작은 값의 차이가 1,000,000을 넘지 않을 때, 효과적으로 사용할 수 있다. 
모든 범위의 데이터를 담을수 있는 크기의 리스트를 선언해야 하기 때문이다.
비교기반의 정렬 알고리즘이 아님! 
"""
# 모든 원소의 값이 0보다 크거나 같다고 가정.
array=[1,4,3,8,6,0,9,2,5,3,7,4,4,3,1,8,7,9,5]
# 모든 데이터 범위를 포함하는 리스트 선언.
count = [0] * (max(array)+1)

for i in range(len(array)): #O(N)
    count[array[i]]+=1

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

시간복잡도: O(N+K)
데이터의 개수 = N, 데이터 중 최댓값 = K일 때, 조건을 만족한다면 O(N+K)를 보장한다.
N개의 data를 탐색한 후, 별도의 리스트에서 인덱스의 값을 확인할 때, K만큼의 반복을 수행하기 때문이다.
계수 정렬은 현존하는 정렬 알고리즘 중에서 기수 정렬과 더불어 가장 빠르다.
공간복잡도: O(N+K)
계수 정렬은 데이터의 개수는 적지만, 범위는 클 경우 매우 비효율적이다. 데이터의 개수에 상관없이 범위에 따라 별도의 리스트를 선언해야 하기 때문이다. 따라서 동일한 값을 가지는 데이터가 여러개 등장할 때 사용하기 적합하다.

---

파이썬의 정렬 라이브러리

파이썬은 정렬을 위한 라이브러리가 구현되어 있어 정렬 알고리즘을 직접구현하지 않아도 간단하게 정렬을 수행할 수 있다. 대부분의 프로그래밍 언어에서 제공하는 정렬을 위한 라이브러리는 O(NlogN)의 시간복잡도를 보장하며, 파이썬의 경우도 그렇다.

sorted()

sorted()는 리스트, 딕셔너리와 같은 iterable한 객체를 받아서 정렬된 형태의 리스트로 반환한다

code

#sorted()
array = [1,6,3,6,8,8,6,2,67,9,0]
result = sorted(array)

print('sorted', result)

# key 로 sort
pairs = [('성원', 25), ('다운', 23), ('재원', 26), ('범수', 30)]

key_sort = sorted(pairs, key=lambda x: x[1]) # key에 함수를 통해 정렬.
print('keysort', key_sort)

오름차순이 아닌 내림차순을 원할 경우, reverse=True를 parameter로 넘겨주면 된다.

또, key parameter로 함수를 넘겨주어 정렬에 사용할 기준 값을 지정해 줄 수 있다. 위 코드와 같이 lambda함수를 사용하면 간단하게 표현할 수 있다.

.sort()

.sort()는 list객체의 내장 함수로, [list].sort()와 같이 사용할 수 있다. 주의해야 할 점은, 반환값 없이 내부에서 바로 sort된다는 점이다.

sorted()와 같이 reverse, key 매개변수를 모두 사용할 수 있다.

code

"""
.sort() => list 의 method
return 없이 list가 바로 sort됨
"""
array = [1,6,3,6,8,8,6,2,67,9,0]
array.sort()
print('.sort', array)

---

📚 Reference

💡 『이것이 코딩테스트다 with 파이썬』, 나동빈 지음 을 읽고 공부하며 정리한 글입니다.

• 『이것이 코딩테스트다 with 파이썬』, 나동빈 지음
• python doc -- sorting
  https://docs.python.org/3/howto/sorting.html