[알고리즘 이론] 정렬(선택정렬, 삽입정렬, 퀵정렬, 계수정렬)

⚡️ 선택정렬

데이터가 무작위로 있을 때, 이중 가장 작은 데이터를 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸고 ... (반복)

#선택정렬
arr = list(map(int, input().split()))

for i in range(len(arr)):
    min_index = i
    for j in range(i + 1, len(arr)):
        if arr[j] < arr[min_index] :
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i] #swap

print(arr)

 

➰선택정렬의 시간복잡도 = O(n^2)

⚡️ 삽입정렬

2번째 원소부터 정렬시작. 자신의 앞 인덱스 숫자에 자기 자신보다 작은 수가 있으면 그 뒤에 삽입. 2 ~ n 까지 반복

#삽입정렬
arr = list(map(int, input().split()))

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

print(arr)

➰삽입정렬의 시간복잡도 = O(n^2)

삽입정렬은 최선의 경우 O(n)의 시간복잡도를 가짐. 삽입정렬은 거의 정렬되어 있는 상태의 데이터를 정렬할 때 매우 빠르다. (이경우,  퀵 정렬보다도 빠름)

⚡️ 퀵정렬

: 가장 많이 사용되는 알고리즘임

기준 데이터를 설정한 후 기준보다 큰 데이터와 작은 데이터의 위치를 변경함. 

기준 데이터를 pivot이라고 함.

 

👀 동작과정

1️⃣ 리스트의 첫번째 데이터가 피벗이 됨.

5 7 1 4 9 2 4 6 9 3

 

2️⃣ 피벗 설정 후 왼쪽에서부터 피벗보다 큰 데이터를, 오른쪽에서부터 피벗보다 작은 수를 탐색함

5 7(왼쪽) 1 4 9 2 4 6 9 3 (오른쪽)

 

3️⃣ 두 데이터 위치를 변경

5 3 1 4 9 2 4 6 9 7

 

위의 과정1,2,3을 왼쪽과 오른쪽이 교차하지 않을동안 반복함

1️⃣ 5 3 1 4 9 2 4 6 9 7

2️⃣ 5 3 1 4 9 2 4 6 9 7

3️⃣ 5 3 1 4 4 2 9 6 9 7

 

1️⃣ 5 3 1 4 4 2 9 6 9 7

2️⃣ 5 3 1 4 4 2 9 6 9 7   

-->❗️왼쪽에서부터 찾은 데이터와 오른쪽에서부터 찾은 데이터가 서로 엇갈림

오른쪽에서부터 찾은 피벗보다 작은 데이터와 피벗의 위치를 서로 바꿔줌

2 3 1 4 4 5 9 6 9 7 

피벗의 왼쪽에는 피벗보다 작은 수만, 오른쪽에는 큰 수만이 위치하게 됨. 피벗이었던 5를 기준으로 왼쪽과 오른쪽 리스트를 다시 과정 1, 2, 3을 통해 정렬함.

1️⃣ 2 3 1 4 4  | 5 |  1️⃣ 9 6 9 7 

2️⃣ 2 3 1 4 4  | 5 |  2️⃣ 9 6 9 7 

3️⃣ 2 1 3 4 4  | 5 |  3️⃣ 9 6 7 9

 

1️⃣ 2 1 3 4 4  | 5 |  1️⃣ 9 6 7 9

2️⃣ 2 1 3 4 4  | 5 |  2️⃣ 9 6 7 9 큰수없음(교차된거랑 똑같이 하면됨)

❗️ 1 2 3 4 4  | 5 | ❗️ 7 6 9 9

 

1️⃣ 1   | 2 |  1️⃣ 3 4 4    | 5 |    1️⃣ 7 6   | 9 |   1️⃣ 9  

#피벗 기준으로 왼쪽, 오른쪽으로 나눈 후 다시 퀵소트를 할때 데이터가 하나밖에 없으면 그냥 리턴

 1  | 2 |  1️⃣ 3 4 4    | 5 |    1️⃣ 7 6   | 9 | 9 

1  | 2 |  2️⃣ 3 4 4    | 5 |    2️⃣ 7 6   | 9 | 9 

1  | 2 |  ❗️ 3 4 4 (피벗과 작은수가 같은 인덱스에 있는 상태)   | 5 |    ❗️ 6 7   | 9 | 9 

 

1  | 2 | 3 | 1️⃣ 4 4  | 5 |  6  | 7  | 9 | 9  (데이터가 하나 남은 건 정렬된 것으로 볼 수 있으므로 리턴~)

1  | 2 | 3 | 2️⃣ 4 4  | 5 |  6  | 7  | 9 | 9

1  | 2 | 3 | ❗️ 4 4 (피벗과 작은수가 같은 인덱스에 있는 상태) | 5 |  6  | 7  | 9 | 9

 

1  | 2 | 3 | 4 | 4 | 5 |  6  | 7  | 9 | 9

 

와아아ㅏ아 정렬 끝!!👻ㅎㅎㅎ

 

➰퀵정렬의 평균 시간복잡도 = O(nlogn)

➰퀵정렬 최악의 경우일 때, 시간복잡도 = O(n^2)

✏️ 퀵정렬이 최악의 경우의 시간복잡도를 가질 때는, 데이터가 전부 정렬되어 있을 때임.

✏️ 데이터가 거의 정렬되어 있는 상태라면 삽입정렬이 빠르게 동작함. 전혀 정렬되어 있지 않다면 퀵정렬을 사용.

✏️ 파이썬의 기본 정렬 라이브러리를 사용한다면, nlogn의 시간복잡도를 보장해주기 때문에 언제든 사용해도됨ㅎㅎ

#퀵정렬
arr = list(map(int, input().split()))

def quick_sort(arr, start, end):
    if start >= end:
        return
    pivot = start    #1️⃣
    left = start + 1
    right = end
    while left <= right:
        #2️⃣
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        if left > right: #❗️
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else: #3️⃣
            arr[left], arr[right] = arr[right], arr[left]
    quick_sort(arr, start, right - 1)
    quick_sort(arr, right + 1, end)

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

 

⚡️ 계수정렬

: 특정한 조건이 있을 때만 사용할 수 있다. 모든 데이터가 양의 정수여야함. 데이터의 범위가 너무 크면 안됨(일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적)

➰ 계수정렬의 시간 복잡도는 데이터의 개수가 n, 데이터의 최댓값이 k일 때, O(n + k)를 보장

 

계수정렬 동작 방법 : 모든 범위를 담을 수 있는 크기의 리스트를 선언함. 리스트의 인덱스가 데이터값이 되고 리스트 안의 값이 데이터의 개수가 됨.

ex) 최댓값이 5라고 가정 (최댓값이 K일 때 K + 1칸의 배열 선언하기)

데이터 : 5 5 3 2 4 4 0 0

arr[0] = 2

arr[1] = 0

arr[2] = 1

arr[3] = 1

arr[4] = 2

arr[5] = 2

 

#계수정렬
data = list(map(int, input().split()))

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

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

➰ 계수정렬의 공간복잡도 = O(n + k)

 

⚡️ 파이썬의 정렬 라이브러리

1. sorted() : 정렬된 리스트를 반환해줌. 집합이나 딕셔너리 자료형을 입력 받아도 반환은 리스트로 해줌. 항상 nlogn의 시간복잡도를 보장.

2. sort() : 리스트 객체의 내장함수임. 별도의 리스트가 반환되는 것이 아니라 입력받은 리스트 내부를 바로 정렬시킴.