[Algorithm] Week 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]  # swap

print(array)

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

---

선택 정렬의 시간 복잡도 : O(N^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)

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

 

---

삽입 정렬의 시간 복잡도: O(N^2) ~ (최선의 경우) O(N^2)

현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작함.

==> 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력함.

 

---

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자!

호어 분할 방식: 리스트에서 첫 번째 데이터를 피벗으로 정함.

1. 리스트의 첫 번째 데이터를 pivot으로 설정하고, 왼쪽에서부터 pivot보다 큰 데이터와 오른쪽에서부터 pivot보다 작은 데이터를 선택한다. 그리고 두 데이터를 swap한다.
2. 1번의 과정을 반복하다가 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 서로 엇갈렸다면 '작은 데이터'와 pivot을 swap한다.
3. 2번의 과정을 완료하면 pivot을 기준으로 왼쪽의 리스트는 pivot보다 작은 데이터들, 오른쪽에 있는 데이터는 모두 pivot보다 큰 데이터들이라는 점을 알 수 있다.
4. 왼쪽, 오른쪽 리스트에서도 각각 pivot을 설정하여 위의 1번, 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:
        # pivot보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1

        # pivot보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1

        if left > right:  # 엇갈렸다면 작은 데이터와 pivot swap
            array[right], array[pivot] = array[pivot], array[right]
        else:  # 엇갈리지 않았다면 작은 데이터와 큰 데이터 swap
            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:]  # pivot을 제외한 리스트

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

 

---

계수 정렬

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

'데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용 가능.

 

계수 정렬은 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에,

가장 큰 데이터와 가장 작은 데이터가 1,000,000을 넘지 않을 때 효과적으로 사용 가능함.

 

비교 기반의 정렬 알고리즘이 아닌, 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담음.

1. 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있도록 하나의 리스트를 생성함.
2. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료됨.

 

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)

기수 정렬과 더불어 가장 빠름.

 

계수 정렬의 공간 복잡도: O(N+K)

 

---

파이썬의 정렬 라이브러리

파이썬의 기본 정렬 라이브러리 ==> sorted()

• 시간복잡도 O(NlogN)을 보장함.
• 리스트, 딕셔너리 자료형을 입력받아도 리스트 자료형을 반환함.

 

리스트 변수가 하나 있을 때 내부 원소를 바로 정렬할 수도 있음. ==> sort()

 

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array)
array.sort()

print(result)
print(array)

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

 

---

key 매개변수를 입력으로 받을 수 있음.

key 값으로는 하나의 함수가 들어가야 함. 

 

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


def setting(data):
    return data[1]  # 두 번째 원소를 기준으로


result = sorted(array, key=setting)
print(result)

# 혹은 람다식으로 바로 작성 가능.
result2 = sorted(array, key=lambda x: x[1])
print(result2)

[('바나나', 2), ('당근', 3), ('사과', 5)]    # 동일한 결과 확인 가능.
[('바나나', 2), ('당근', 3), ('사과', 5)]

 

---

정렬 라이브러리의 시간 복잡도: O(NlogN) 을 보장함.

 

코딩 테스트에서 정렬 알고리즘이 사용되는 경우

1. 정렬 라이브러리로 풀 수 잇는 문제
2. 정렬 알고리즘의 원리에 대해서 물어보는 문제
3. 더 빠른 정렬이 필요한 문제