정렬

 

정렬 (Sorting)

데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.

 

---

선택 정렬(Selection Sort)

정렬된 왼쪽 리스트와 정렬 안된 오른쪽 리스트를 가정하고, 오른쪽 리스트에서 최소값을 선택하여 오른쪽 리스트의 첫번째 수와 교환한다.

 

• 선택 정렬의 소스코드

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

for i in range(len(arr)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(arr)):
        if arr[min_index] > arr[j]:
            min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i] # 교환

print(arr)

 

• 선택 정렬의 시간 복잡도

(n -1) + (n - 2) + ... + 2 = n(n - 1) / 2 = O(n²)

 

---

삽입 정렬(Insertion Sort)

정렬된 왼쪽 리스트와 정렬 안된 오른쪽 리스트를 가정하고, 오른쪽 리스트의 첫번째 값을 선택하여 정렬된 왼쪽 리스트에 적절한 위치를 찾아 삽입한다.

* 상대적 위치가 바뀌지 않음

 

• 삽입 정렬의 소스코드

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

for i in range(1, 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]
        else:   # 자신보다 작은 데이터를 만나면 멈춘다.
            break

print(arr)

 

• 삽입 정렬의 시간복잡도

- 최선의 경우(이미 정렬되어 있는 경우) : O(n)

- 최악의 경우(역순으로 정렬되어 있는 경우) : O(n²)

 

---

퀵 정렬(Quick Sort)

pivot을 기준으로 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

- 리스트의 첫 번째 데이터를 pivot이라 정한다.

- pivot을 기준으로 큰 데이터와 작은 데이터를 교환하고, 엇갈린 위치에서 작은 데이터와 피벗위치를 교환한다.

- pivovt을 기준으로 왼쪽리스트와 오른쪽 리스트에서 각각 다시 정렬을 수행한다. 

 

• 퀵 정렬의 소스코드

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

def quick_sort(arr):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료한다.
    if len(arr) <= 1:
        return arr
    
    pivot = arr[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(arr))

 

• 퀵 정렬의 시간복잡도

- 최선의 경우(균등하게 분할 되는 경우) : O(nlogn)

T(n) = (n - 1) + 2*T(n / 2)

T(1) = 0

- 최악의 경우(불균등한 경우, 정렬된 리스트를 정렬하는 경우) : O(n²)

 

---

계수 정렬(Count Sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있으며, 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다. 계수 정렬을 이용할 때는 '모든 범위를 담을 수 있는 크기의 리스트를 선언'해야 하기 때문이다.

 

정리하자면 데이터의 크기가 한정되어 있고 데이터가 많이 중복되어 있을 수록 유리하고 항상 사용할 수 없다.

계수 정렬은 앞의 정렬과 다르게 직접 데이터 값을 비교하는 비교 기반의 정렬 알고리즘이 아니다.

 

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

- count 리스트에 각 데이터가 몇 번 등장했는지 기록한다.'

- count 리스트 첫 번째 데이터부터 차례때로 그 값만큼 인덱스를 출력한다.

 

• 계수 정렬의 소스코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(arr) + 1)

for i in range(len(arr)):
    count[arr[i]] += 1  # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ')

 

• 계수 정렬의 시간복잡도

데이터의 개수가 n, 데이터 중 최댓값이 k일 때, O(n + k)

 

• 계수 정렬의 공간복잡도

데이터의 개수가 n, 데이터 중 최댓값이 k일 때, O(n + k)

 

 

* 이것이 코딩테스트다 with 파이썬 - 나동빈