[이코테] 정렬 알고리즘 정리

정렬(Sorting) 1️⃣ 2️⃣ 3️⃣ 4️⃣ 5️⃣

• 데이터를 특정한 기준에 따라서 순서대로 나열하는 것
• 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘

✔️ 선택 정렬

'매번 가장 작은 것을 선택'해서 맨 앞에 있는 데이터와 바꾼다(오름차순)

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]

⏰ 시간 복잡도 N * (N+1) / 2 -> (N^2 + N) / 2 -> O(N^2)
N-1 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다.
연산 횟수 N + (N-1) + (N-2) + (N-3) + ... + 2

⤵️ 삽입 정렬

'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?'

• 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적
• 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
• 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다는 점이 특징이다.

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

range(start, end, step)

⏰ 시간 복잡도 O(N^2)
선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용됨
🌟 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작, 최선의 경우 O(N)

⛳️ 퀵 정렬

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?'

⛳️ 피벗(Pivot)
큰 숫자와 작은 숫자를 교환할 떄, 교환하기 위한 기준

호어 분할 Hoare Partition
리스트에서 첫 번째 데이터를 피벗으로 정한다.

퀵 정렬 종료 조건 = 현재 리스트의 데이터 개수가 1개인 경우

array = [7, 5, 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, 0, len(array)-1)
print(array)

• 🌟 파이썬 장점을 살린 퀵 정렬 소스코드

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

⏰ 시간 복잡도 O(N^2)
평균적으로 시간 복잡도가 O(NlogN)이지만 최악의 경우 시간 복잡도가 O(N^2)다.
-> 기본 정렬 라이브러리를 이용하면 O(NlogN) 보장

➕ 계수 정렬(Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘.
데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다.
-> 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 함

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=' ') # 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

⏰ 시간 복잡도 O(N + K)
데이터 개수 N, 데이터 중 최댓값이 K일 때, O(N + K)
데이터 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다.
현존하는 정렬 알고리즘 중 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.

공간 복잡도 O(N + K)

🩵 파이썬의 정렬 라이브러리

sorted()
병합 정렬을 기반으로 만들어짐
-> 최악의 경우에도 O(NlogN)을 보장한다는 특징이 있음
리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력한다.

sort()
별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

sorted()나 sort()를 이용할 때는 key 매개변수를 입력으로 받을 수 있다.
key값으로는 하나의 함수가 들어가야 하며 이는 정렬 기준이 된다.

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

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

lambda 함수 사용 가능

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

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