[알고리즘] 정렬 알고리즘

정렬 알고리즘

Selection sort

n개의 원소를 가진 배열 중에 가장 작은 값을 찾아서 처리되지 않은 데이터 중 맨 앞과 바꾼다. 이 과정을 N-1번 반복해 정렬이 완료된다.

for i in range(len(array)):
  min_index = i
  for j in range(i + 1, len(array)):
    if array[min_index] > array[j]:
      min_index = j
  array[i], array[min_index] = array[min_index], array[i]

Space ComplexityTime Complexity

O(1)

O(n^2)

Bubble sort

인접한 두 개의 데이터를 비교해가면서 정렬을 진행한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 끝에 위치하므로 2회전에서는 제외한다. 회전을 반복할 수록 정렬에서 제외되는 데이터가 늘어난다.

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

Space ComplexityTime Complexity

O(1)

O(n^2)

Insertion sort

특정 데이터가 적절한 위치에 들어가기 전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. i번째 원소와 i-1부터 0번째까지 원소를 비교하면서 i번째 원소가 비교하는 원소보다 클 경우를 찾아 위치를 바꾼다.

for i in range(1, len(arr)):
  for j in rnage(i, 0, -1):
    if arr[j] < arr[j - 1]:
      arr[j], arr[j - 1] = arr[j - 1], arr[j]
    else: # 자기보다 작을 경우 멈춤
      break

Space ComplexityTime Complexity

O(1)

O(n^2)

Quick sort

피벗을 정하고 왼쪽에서부터 피벗보다 큰 데이터를 찾고 오른쪽에서부터 피벗보다 작은 데이터를 찾아서 서로 위치를 바꾼다.

만약 왼쪽과 오른쪽의 위치가 엇갈린다면 작은 데이터와 피벗을 바꾼다.

피벗이 이동한 상태에서 배열은 분할 완료(partition)된 상태이다. 피벗의 왼쪽은 피벗보다 작은 데이터가 위치하고 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치한다.

이렇게 나눠진 왼쪽, 오른쪽 배열을 다시 재귀적으로 quick sort 시킨다. 현재 리스트의 데이터 개수가 1개일 때 재귀는 종료된다.

worst case

피벗이 가장 작은 값이거나 가장 큰 값으로 partitioning이 unbalanced 할 경우가 worst case이다. 이 경우 비교 횟수는 n, n-1, n-2 번 ,... 이 되므로 시간복잡도는 O(n^2)이 된다.

Balanced-partitioning

피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할한다면 시간복잡도는 O(NlogN)이 되게 된다.

def quick_sort(arr, start, end):
  if start >= end:
    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
    if left > right:
      arr[right], arr[pivot] = arr[pivot], arr[right]
    else:
      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)

Space ComplexityTime Complexity

O(log(n))

O(nlogn)

Heap sort

• 힙에 넣었다 꺼내기
• 기존 배열 힙으로 만들기

Space ComplexityTime Complexity

O(1)

O(nlogn)

Merge sort

정렬하고자 하는 배열의 크기를 작은 단윙로 나누어 정렬한 후 결합한다.

Merge Sort는 더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우(원소가 하나인 배열일 때)에는 자기 자신, 즉 원소 하나를 반환한다. 원소가 하나인 경우에는 정렬할 필요가 없기 때문이다. 이 때 반환한 값끼리 combine될 때, 비교가 이뤄지며, 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다. 실제 정렬은 나눈 것을 병합하는 과정에서 이뤄지는 것이다.

Space ComplexityTime Complexity

O(n)

O(nlogn)

Count sort

정렬하고자는 값 중 최대 값에 해당 하는 값을 size로 하는 임시 배열을 만든다. 각 원소가 몇개인지 세서 정렬한다. 가장 큰 데이터와 가장 작은 데이터의 차이가 너무 크다면 계수 정렬은 사용할 수 없다.

Space ComplexityTime Complexity

O(n)

O(n)

Radix sort

자릿수 별로 버킷에 분배하였다가 버킷의 순서대로 데이터를 꺼내 정렬한다.

Space ComplexityTime Complexity

O(n)

O(n)