정렬 알고리즘

이코테 강의를 통해 공부했습니다!!

• 정렬(Sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것
• 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.
  • 예) 데이터가 많을 때, 데이터가 많지만 범위가 한정되어 있을 때, 데이터가 어느정도 정렬되어 있을 때 등

선택 정렬

• 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 과정을 반복하는 정렬 방식
• 단순하게 전체 리스트를 훌어보면서 가장 작은 숫자부터 정렬하는 방식이다.

선택 정렬 파이썬 구현

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

for i in range(len(array)): # i는 0부터 마지막 인덱스까지, 정렬이 될 원소를 가리킴
    min_index = i
    for j in range(i + 1, len(array)): # 0 ~ i-1 까지는 정렬이 됐으므로 그 뒷 부분을 확인 
        if array[min_index] > array[j]: # j 인덱스로 끝까지 돌면서 최소값을 선택
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # i의 위치에 선택한 최소값으로 swap

print(array)

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

선택 정렬의 시간 복잡도

• N개의 데이터가 있을 때, 선택 정렬은 N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내는 연산을 수행함
• 전체 연산 횟수는 다음과 같다.
  $N +(N-1)+(N-2)+...+2 = {N^2+N-2 \over 2}$
• 대략적으로 봐도 2중 for문 안에서 연산이 실행되기 때문에 입력되는 데이터의 개수에 제곱에 비례하여 수행 시간이 늘어나기 때문에 시간 복잡도는 $`O(N^2)`$으로 표시된다.

삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬 방식
• 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작
• 정확히는 ‘데이터가 거의 정렬되어 있을 때’ 선택 정렬보다 훨씬 효율적이다.

삽입 정렬의 파이썬 구현

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

for i in range(1, len(array)):  # i : 앞 부분에 삽입할 원소의 인덱스
    for j in range(i, 0, -1):   # j를 이용해서 삽입할 원소의 위치를 앞으로 한칸 씩 이동시킨다.
        if array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
        else:
            # 이미 i의 앞 쪽은 오름차순 정렬이 되어있으므로
            # 자기보다 작은 숫자가 앞에 위치할 때까지 이동한 다음에 이동을 종료한다.
            break

print(array)

삽입 정렬의 시간 복잡도

• 빅 오 표기법으로 삽입 정렬의 시간 복잡도는 $`O(N^2)`$이다. 이중 for문의 사용에서 쉽게 유추가 가능하다.
• 삽입 정렬과 선택 정렬의 차이점은, 삽입 정렬의 경우 현재 리스트 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 점이다. 최선의 경우 $`O(N)`$의 시간 복잡도를 가진다.

퀵 정렬

• 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
  • 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작
• 가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
• 이름 그대로 빠른게 특징인 알고리즘.
• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘

퀵정렬의 파이썬 구현

일반적인 방식

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

def quick_sort(array, start, end):
    if start >= end:
        # 종료 조건
        # start == end -> 파티션에 존재하는 원소의 개수가 1개임을 의미
        # start > end  -> 파티션에 원소가 존재하지 않음을 의미
        return

    pivot = start       # 피벗을 기준으로 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 분할
    left = start + 1    # 왼쪽에서 피벗보다 큰 원소를 찾아서 오른쪽으로 보낸다
    right = end         # 오른쪽에서 피벗보다 작은 원소를 찾아서 왼쪽으로 보낸다

    while (left <= right):  # left와 right가 교차되면 반복문 종료
        while (left <= end and array[left] <= array[pivot]):
            # left는 왼쪽부터 피벗보다 큰 원소를 찾을 때까지 오른쪽으로 한 칸씩 이동한다.
            left += 1
        while (right > start and array[right] >= array[pivot]):
            # right는 오른쪽부터 피벗보다 작은 원소를 찾을 때까지 왼쪽으로 한 칸씩 이동한다.
            right -= 1

        if (left > right):
            # left와 right가 교차되면 피벗위치의 원소와 right위치의 원소를 swap한다
            # 즉, 분할을 시행하고 반복문이 종료된다
            array[right], array[pivot] = array[pivot], array[right]
        else:
            # left와 right가 교차되지 않았다면 두 원소를 swap한 후 반복한다
            array[left], array[right] = array[right], array[left]

    # right의 위치로 피벗 원소가 이동하고 분할이 완료되었기 때문에
    # 나뉜 두 부분에 대해 다시 sort를 진행한다.
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

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

파이썬의 장점을 살린 방식 (리스트 슬라이싱, 리스트 컴프리헨션)

• 피벗을 기준으로 분할을 할 때 left right 인덱스를 사용하지 않고 파이썬의 리스트 기능들을 이용해 간단하게 구현함

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:]

    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(NlogN)`$의 시간복잡도를 갖는다.
• 참고) 퀵 정렬의 시간 복잡도에 대한 증명은 초보자가 다루기에 간단하지 않다. 더불어 코딩 테스트를 목적으로 하는 경우, 퀵 정렬의 시간 복잡도 증명에 대하여 자세히 알지 못해도 큰 무리가 없다. 따라서 책에서는 구체적인 증명보다는 직관적인 이해를 돕기 위한 설명에 초점을 맞춰 전개하고자 한다.
• N개의 데이터가 존재하는 경우 가장 이상적인 상황에서 quick_sort는 $log_2N$ 번 발생하기 때문에 퀵 정렬의 시간 복잡도는 $`O(NlogN)`$이다.
• 하지만 최악의 경우 시간복잡도는 $`O(N^2)`$까지 늘어난다. 이미 정렬된 배열에 대해서 퀵 정렬을 수행할 경우 N번의 분할이 일어나야 하기 때문이다.

계수 정렬

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

계수 정렬의 파이썬 구현

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

# 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.
count = [0] * (max(array) + 1)

# 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시킨다.
for i in range(len(array)):
    count[array[i]] += 1

계수 정렬의 시간 복잡도

• 계수 정렬의 시간 복잡도와 공간 복잡도는 모두 $`O(N+K)`$
• 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있음
  • N이 작고 K가 큰 경우 비효율적 → 데이터가 0과 999,999로 단 2개만 존재하는 경우
• 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적

정렬 문제 풀이

문제1 : 두 배열의 원소 교체

# 두 배열의 원소 교체

# 입력
n, k = map(int, input().split())
array_a = list(map(int, input().split()))
array_b = list(map(int, input().split()))

# 정렬
array_a.sort()
array_b.sort(reverse=True)

# 바꿔치기
for i in range(k):
    if array_a[i] < array_b[i]:
        array_a[i] = array_b[i]
    else:
        break
# 출력
print(sum(array_a))

백준 문제 풀이

11650번 : 좌표 정렬하기

11650번: 좌표 정렬하기

# 좌표 정렬하기

import sys
input = sys.stdin.readline

# 입력
n = int(input())
array = []
for _ in range(n):
    array.append(list(map(int, input().split())))

# 정렬
array.sort()

# 출력
for i in range(n):
    print(f'{array[i][0]} {array[i][1]}')

11651번 : 좌표 정렬하기 2

11651번: 좌표 정렬하기 2

# 좌표 정렬하기 2

# 좌표 정렬하기 1에서 y와 x의 위치만 바꿔서 정렬
import sys
input = sys.stdin.readline

# 입력
n = int(input())
array = []
for i in range(n):
    x, y = map(int, input().split())
    array.append([y, x])

array.sort()

# 출력
for i in range(n):
    print(f'{array[i][1]} {array[i][0]}')

1181번 : 단어 정렬

1181번: 단어 정렬

# 단어 정렬
import sys
input = sys.stdin.readline

# 집합 51개를 가지는 리스트 생성
word_set_list = [set() for _ in range(51)]

# 입력
n = int(input())
for _ in range(n):
    word = input().rstrip()
    word_set_list[len(word)].add(word)

# 정렬 & 출력
for word_set in word_set_list:
    if len(word_set) == 0:
        continue
    word_set = sorted(word_set)
    print('\n'.join(word_set))

18870번 : 좌표 압축

18870번: 좌표 압축

# 좌표 압축

import sys
input = sys.stdin.readline

n = int(input())
number_list = list(map(int, input().split()))

number_set = set(number_list)
number_set = sorted(number_set)
number_dict = {}
for i in range(len(number_set)):
    number_dict[number_set[i]] = i

for x in number_list:
    print(number_dict[x])

# for x in number_list:
#     print(number_set.index(x), end=' ')
# O(n^2)으로 시간 초과 발생