[이코테 알고리즘] - 정렬 (1) (선택, 삽입, 퀵, 계수)

zsunny·2022년 8월 3일

[Python] 이코테 문제

목록 보기

5/6

📍 정렬 알고리즘

정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
일반적으로 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다.

1️⃣ 선택 정렬

선택 정렬은 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸는 것을 반복하는 것이다.

첫번째 데이터를 두번째 ~ 마지막 데이터들과 비교해 첫번째 데이터 보다 작은 수가 있으면 첫번째 자리에 둔다. (두 수의 자리를 바꾼다.)

두번째 데이터를 세번째 ~ 마지막 데이터들과 비교해 두번째 데이터 보다 작은 수가 있으면 두번째 자리에 둔다. (두 수의 자리를 바꾼다.)

이 과정을 끝까지 반복하면 오름차순으로 정렬된다.

🔎 시간 복잡도 분석

N번 만큼 가장 작은 수를 찾아 맨 앞으로 보낸다.
구현 방식에 따라 사소한 오차는 있을 수 있으나 전체 연산 횟수는 다음과 같다.
N + ( N - 1 ) + ( N - 2 ) + ••• + 2
이는 ( N2 + N + 2 ) / 2 로 표현할 수 있는데, 빅오표기법으로 O(N2) 라고 작성한다.

선택 정렬 예제 )

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

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

print(arr)

2️⃣ 삽입 정렬

삽입 정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

첫번째 데이터는 이미 정렬되어있다고 가정하고 두번째 데이터의 위치를 판단한다. (첫번째 데이터 앞에 들어가거나 움직이지 않는 2가지의 경우만 존재)

즉, 매번 왼쪽의 데이터와 비교해 자리를 찾는다.

이 과정을 끝까지 반복하면 오름차순으로 정렬된다.

🔎 시간 복잡도 분석

삽입 정렬의 시간 복잡도는 빅오표기법으로 O(N2) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.
삽입 정렬은 현재 리스트의 데이터가 거의 정렬된어 있는 상태라면 매우 빠르게 동작한다.
- 최선의 경우 O(N)의 시간 복잡도를 가진다.
- 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떨까?
  - Break 만 하는 거의 상수 시간의 시간 복잡도를 가질 수도 있다.

삽입 정렬 예제 )

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):   # 인덱스 i부터 1까지 1씩 감소하며 반복
        if arr[j] < arr[j-1]:   # 현재 데이터가 왼쪽 데이터보다 작으면
            arr[j], arr[j-1] = arr[j-1], arr[j] # 자리를 바꿔 왼쪽으로 이동
        else:                   # 현재 데이터가 왼쪽 데이터보다 크면
            break               # 이동하지 않음

print(arr)

3️⃣ 퀵 정렬

굉장히 빠른 정렬 알고리즘 중 하나
기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘이다.
가장 기본적인 퀵 정렬은 첫번째 데이터를 기준 데이터(Pivot)로 설정하는 것이다.

첫번째 데이터를 기준 데이터(피벗 값) 으로 설정한다.

이 데이터를 기준으로 왼쪽에서는 큰 값 오른쪽에서는 작은 값을 선택해 두 수의 위치를 바꾼다.

이 과정을 반복하는데 단, 두 수의 위치가 엇갈리는 경우 피벗 값과 작은 데이터의 위치를 바꾼다.

이 경우, 피벗 값을 기준으로 그 왼쪽에 있는 데이터들은 모두 작은 값들이고 오른쪽에 있는 데이터들은 모두 큰 값들이다.
-> 이러한 작업을 분할 (Divide) 또는 파티션 (Partition) 이라고 한다.

왼쪽 오른쪽 데이터들을 각각의 배열로 판단해 왼쪽에 대해 퀵 정렬 수행 오른쪽에 대해 퀵 정렬 수행한다. (재귀적으로 수행 / 정렬 범위 작아짐)

🔎 시간 복잡도 분석

퀵 정렬이 빠른 이유 : 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있다. (너비 N X 높이 logN)

퀵 정렬은 평균의 경우 O(NlogN) 의 시간 복잡도를 가진다.
하지만 최악의 경우 O(N2) 의 시간 복잡도를 가질 수도 있다.
- 피벗 값 설정에 따라 분할이 절반에 가깝게 이루어지지 않고 한쪽 방향으로 편향된 분할이 발생할 수 도 있다.

퀵 정렬 예제 1 )

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

def quick_sort(arr, start, end):
    if start >= end:        # 원소가 1개면 종료
        return
    # 정렬하고자하는 데이터가 여러개면 퀵정렬 시작
    pivot = start           # 피벗 값 = 첫번째 원소
    left = start + 1
    right = end
    while(left <= right):   # 분할이 될때까지 (엇갈릴 때까지)
        # 피벗보다 큰 데이터 찾을 때까지 반복
        while(left <= end and arr[left] <= arr[pivot]):
            left += 1
        # 피벗보다 작은 데이터 찾을 때까지 반복
        while(right > start and arr[right] >= arr[pivot]):
            right -= 1
        # left는 항상 오른쪽으로 가고 right은 항상 왼쪽으로 가기 때문에
        # 이 과정 자체를 '선형탐색'이라고 볼 수 있음
        if(left > right):       # min, max값의 자리가 엇갈리면 min과 pivot 자리를 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else:                   # 아니라면 min값과 max값의 자리를 교체
            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)

퀵 정렬 예제 2 ) 파이썬의 장점을 살린 짧은 로직

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 = arr[1:]      # 피벗을 제외한 리스트
    # pivot과 pivot을 제외한 나머지 원소 리스트 비교하며 왼쪽 오른쪽 부분으로 분할
    left_side = [x for x in tail if x <= pivot]     # pivot 보다 작으면 왼쪽에
    right_side = [x for x in tail if x > pivot]     # pivot 보다 크면 오른쪽에
    # 분할 후 왼쪽 부분과 오른쪽 부분 각각 정렬 수행하고 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(arr))

4️⃣ 계수 정렬

특정한 조건이 부합할 때만 사용할 수 있으나 매우 빠르게 동작하는 정렬 알고리즘이다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다.

min, max 데이터의 범위가 담길 수 있는 리스트를 생성한다.

각 데이터 값(=인덱스)이 몇번 등장 했는지 카운트한다. ( 상수 시간 O(1) )

리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복해 인덱스(데이터) 출력한다.
ex. 759031629148052 -> 001122345567899

데이터의 범위가 담길 수 있는 리스트를 생성해야하므로 상대적으로 공간 복잡도가 높지만 퀵 정렬과 비교시 조건만 만족한다면 더 빠르게 동작한다.

🔎 시간 복잡도 분석

계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N + K)이다.
- 공간 복잡도: 정렬을 수행하는 개수 N + 데이터 중 가장 큰 값 K 만큼의 크기 가진 공간
계수 정렬은 때에 따라 심각한 비효율성을 초래할 수도 있다.
- 데이터가 0과 999,999로 단 2개만 존재할 때
  -> 데이터는 2개지만 총 1000만개 만큼의 배열 만들어야 함..
계수 정렬은 동일한 값을 가지는 데이터가 여러개 등장 할 때 효과적으로 사용된다.
- 성적의 경우 100점 맞은 학생이 여러명일 수 있기에 계수 정렬이 효과적

계수 정렬 예제 )

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

cnt = [0] * (max(arr) + 1)  # 모든 범위 포함하는 리스트 선언

# O(N) : 데이터 개수만큼 데이터 확인하며 카운트
for i in range(len(arr)):   # 각 데이터에 해당하는 인덱스 값 증가
    cnt[arr[i]] += 1

# O(N+K) : 원소 중 가장 큰 값을 의미하는 K만큼 각 인덱스 확인하며
#		   그 인덱스에 기록되어 있는 값만큼 출력 수행
for i in range(len(cnt)):   # 리스트에 기록된 정렬 정보 확인
    for j in range(cnt[i]):
        print(i, end=' ')   # 띄어쓰기 구분으로 카운트된 횟수만큼 인덱스 출력