[Algorithm] 정렬

* Python을 기준으로 합니다

---

정렬 (Sorting)

- 개념

• 정렬 : 데이터를 순서대로 나열하는 것
• 정렬의 종류
  • Time Complexity $O(n^{2})$
    1. 선택 정렬 (Selection Sort) :  가장 단순한 정렬 방식으로, 배열에서 가장 작은 수를 찾아 하나씩 순서대로 정렬하는 방법
    2. 삽입 정렬 (Insertion Sort) : 현재 위치의 수를 정렬된 영역의 적절한 위치로 이동시켜 정렬하는 방법
       - 거의 정렬되어 있는 경우 $O(n)$을 소모하지만 대부분의 경우, $O(n^{2})$이 소모됨
    3. 버블 정렬 (Bubble Sort) : 현재 값과 다음 값을 비교하여 다음 값이 더 작다면 위치를 교환하는 방식으로 정렬
  • Time Complexity $O(n \log n)$
    1. 퀵 정렬 (Quick Sort) : pivot를 활용하여 분할-정복 방식으로 정렬하는 방법
       - Pivot 보다 작으면 왼쪽, 크면 오른쪽으로 나누어 가면서 재귀적으로 정렬
    2. 병합 정렬 (Merge Sort) : 정렬되지 않은 영역이 1칸이 될 때까지 절반씩 분할한 다음, 하나씩 병합하면서 정렬하는 방식
       - 병합 정렬은 안정 정렬
    3. 트리 정렬 / 힙 정렬 (Tree Sort / Heap Sort) : 이진 트리 / 힙을 사용하여 정렬하는 방식
  • 기타 정렬 방식
    1. 계수 정렬 (Counting Sort) : 주어진 배열에서 각 수들이 등장한 빈도를 활용하여 정렬하는 방식
    2. 기수 정렬 (Radix Sort) : 각 숫자의 자릿수 별로 계수 정렬을 수행하는 방식
    3. 위상 정렬 (Topology Sort) : 방향 비순환 그래프 (Directed Acyclic Graph)에서 작업의 순서에 따라 정렬하는 방식

- 구현

1. sort(), sorted()를 활용하는 방법

• Python은 기본적으로 `sort()`, `sorted()`를 통해 정렬을 지원하고, Tim Sort로 구현되어 $O(n \log n)$을 보장함
  • 이때 아래의 argument를 활용하여 특정 기준으로 정렬할 수 있음 
  • `key` : 특정 기준을 정하는 함수를 활용해 정렬
    - 주로 lambda 표현식을 활용해서 기준에 대한 함수를 설정함
  • `reverse` : `reverse=False` 시 오름차순(default), `reverse=True` 시 내림차순

test = [[0,6], [1,1], [1,3], [2,2], [0,4], [1,5]]

print(sorted(test)) #[[0, 4], [0, 6], [1, 1], [1, 3], [1, 5], [2, 2]]
print(sorted(test, reverse=True)) #[[2, 2], [1, 5], [1, 3], [1, 1], [0, 6], [0, 4]]

#리스트의 두번째 값을 기준으로 정렬
print(sorted(test, key=lambda x: x[1])) #[[1, 1], [2, 2], [1, 3], [0, 4], [1, 5], [0, 6]]

• `functools` 라이브러리의 `cmp_to_key()`를 사용하여 복잡한 정렬 기준을 사용할 수도 있음

from functools import cmp_to_key

def sort_criteria(a, b):
  if a[1]>b[1]: # 배열의 두번째 값이 더 크면
    return 1 #a 다음에 b가 오도록 정렬
  elif a[1] == b[1]: #배열의 두번째 값이 같으면
    return 0 #a,b 순서를 변경하지 않음
  else:
    return -1 #b 다음에 a가 오도록 정렬

#리스트의 두번째 값을 기준으로 정렬
test = [[0,6], [1,1], [1,3], [2,2], [0,4], [1,5]]
print(sorted(test, key=cmp_to_key(sort_criteria))) #[[1, 1], [2, 2], [1, 3], [0, 4], [1, 5], [0, 6]]

2. 선택 정렬

• 정렬되지 않은 부분에서 최소값을 찾아 위치를 교환하는 방식

def selection_sort(arr):
  for i in range(len(arr)-1):
    idx = i
    for j in range(i+1, len(arr)):
      if arr[j] < arr[idx]:
        idx = j #정렬되지 않은 부분에서 최소값의 index
    
    arr[i], arr[idx] = arr[idx], arr[i] #swap 

  return arr

test = [2, 8, 9, 1, 3, 7, 6, 4, 5]
print(selection_sort(test)) #[1, 2, 3, 4, 5, 6, 7, 8, 9]

3. 삽입 정렬

• 배열의 각 값들을 하나씩 확인하면서, 적절한 위치로 삽입하는 방식

def insertion_sort(arr):
  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] #swap
      else: #정렬된 경우
        break

  return arr

test = [2, 8, 9, 1, 3, 7, 6, 4, 5]
print(insertion_sort(test)) #[1, 2, 3, 4, 5, 6, 7, 8, 9]

4. 버블 정렬

• 현재 값과 다음 값을 비교하여, 다음 값이 더 크면 swap 하는 방식

def bubble_sort(arr):
  for i in range(1, len(arr)):
    for j in range(0, len(arr)-1):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]

  return arr

test = [2, 8, 9, 1, 3, 7, 6, 4, 5]
print(bubble_sort(test)) #[1, 2, 3, 4, 5, 6, 7, 8, 9]

5. 퀵 정렬

• Pivot과 분할 정복을 활용하는 방법

def quick_sort(arr, start, end):
  if start >= end:
    return # 종료조건

  pivot = start #pivot을 배열의 첫번째 값으로 설정
  left = start+1
  right = end

  #partition
  while left <= right:
    while left <= end and arr[left]<= arr[pivot]: #pivot 보다 큰 값을 찾을 때까지
      left += 1
    while right > start and arr[right] >= arr[pivot]: #pivot 보다 작은 값을 찾을 때까지
      right -= 1
    
    if left > right: #교차하면 right와 pivot을 swap
      arr[right], arr[pivot] = arr[pivot], arr[right]
    else: #교차하지 않으면 작은 값과 큰 값을 swap
      arr[left], arr[right] = arr[right], arr[left]

  #recursion
  quick_sort(arr, start, right-1)
  quick_sort(arr, right+1, end)

test = [2, 8, 9, 1, 3, 7, 6, 4, 5]
quick_sort(test, 0, len(test)-1)
print(test) #[1, 2, 3, 4, 5, 6, 7, 8, 9]

퀵 정렬

6. 병합 정렬

• 정렬되지 않은 영역이 1칸이 될 때까지 절반씩 분할한 다음, 하나씩 병합하면서 정렬하는 방식
  1. 각 배열의 첫 번째 값을 나타내는 index를 만들고
     
     1. 각 index가 가리키는 값 중에서 작은 값을 새로운 배열 merged에 추가
     2. 선택된 index를 증가
     3. 한 배열 내의 데이터가 새로운 배열 merged에 저장될 때까지 위 과정을 반복
  2. 이후 남아 있는 배열의 값을 merged 배열에 저장
     - 결과적으로 merged 배열에는 데이터가 정렬된 상태로 저장됨
  3. 주어진 배열을 절반으로 나누어가며 위 과정을 재귀적으로 처리

def merge(left, right):
    merged = []
    i = j = 0 #첫번째 값을 가리키는 index
    while i < len(left) and j < len(right): #왼쪽,오른쪽 배열이 모두 존재하면
        if left[i] < right[j]: #왼쪽 값이 작으면 왼쪽 배열에 추가
            merged.append(left[i]) 
            i += 1
        else: #아니면 오른쪽에 추가
            merged.append(right[j])
            j += 1
    
    #배열에 남아있는 값 처리
    merged += left[i:]
    merged += right[j:]

    return merged

def merge_sort(arr):
    if len(arr) <= 1:
      return arr #종료조건
	
    #recursion
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

test = [2, 8, 9, 1, 3, 7, 6, 4, 5]
print(merge_sort(test)) #[1, 2, 3, 4, 5, 6, 7, 8, 9

병합 정렬

7. 힙 정렬

• 힙을 사용하여 정렬하는 방식

import heapq #heap 사용을 위함

def heap_sort(arr):
  heap = []
  for data in arr:
    heapq.heappush(heap, data) #push
  
  return [heapq.heappop(heap) for i in range(len(heap))] #pop으로 정렬
 
test = [2, 8, 9, 1, 3, 7, 6, 4, 5]
print(heap_sort(test)) #[1, 2, 3, 4, 5, 6, 7, 8, 9]