선택/삽입/거품/병합/힙/카운팅/기수정렬 알고리즘

백준 알고리즘 문제를 풀며 다뤄지는 다양한 방법의 정렬 알고리즘들에 대해 알아보려 한다.

선택 정렬 (Selection Sort)

이름처럼 현재 위치에 들어갈 값을 찾아 정렬하는 배열
현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬, 최대 선택 정렬로 구분됨
- 최소 선택 정렬은 오름차순, 최대 선택 정렬은 내림차순
알고리즘
- 정렬 되지 않은 인덱스의 맨 앞부터 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아감
  - 정렬되지 않은 인덱스의 맨 앞은 초기 입력에서는 배열의 시작위치가 됨
- 가장 작은 값을 찾으면 그 값을 현재 인덱스의 값과 바꿔줌
- 다음 인덱스에서 위 과정을 반복함

알고리즘은 n-1개, n-2개, …, 1개를 각각 비교함.
- 따라서 배역 어떻게 되었던 전체 비교를 진행하므로 시간 복잡도는 $O(n^{2})$
- 공간 복잡도는 단 하나의 배열에서만 진행하므로 $O(n)$
코드

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

삽입 정렬 (Insertion Sort)

현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아 그 위치에 삽입하는 배열 알고리즘
알고리즘
- 두 번째 인덱스부터 비교하며, 현재 인덱스는 별도의 변수에 저장하고 비교 인덱스를 현재 인덱스-1로 잡음
- 별도 저장해둔 삽읍을 위한 변수와 비교 인덱스의 배열 값 비교
- 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장하고, 비교 인덱스를 01 하여 비교 반복
- 만약 삽입 변수가 더 크면 비교 인덱스+1에 삽입 변수를 저장

최악의 경우(역정렬) n-1, n-2, .., 1개씩 비교하여 시간복잡도는 $O(n^{2})$ 이나, 이미 정렬되어 있는 경우엔 한 번씩밖에 비교를 하지 않아 복잡도는 $O(n)$이 됨
공간 복잡도는 단 하나의 배열에서만 진행하므로 $O(n)$
코드

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1]  = x[j]
			j = j - 1
		x[j+1] = key
	return x

거품 정렬 (Bubble Sort)

매번 연속된 두 개 인덱스를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 방법
오름차순으로 정렬하고자 할 경우 비교시마다 큰 값이 뒤로 이동하며, 1 바퀴 돌 시 가장 큰 값이 맨 뒤에 저장
맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기에 (전체 배열 크기 - 현재까지 순환한 바퀴 수)만큼만 반복하면 됨
알고리즘
- 두 번째 인덱스부터 시작하며, 현재 인덱스 값과 이전 인덱스 값을 비교
- 이전 인덱스가 크면 현재 인덱스와 바꿔줌
- 현재 인덱스가 더 크면 다음으로 두 연속된 배열값 비교
- 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수) 만큼 반복

시간 복잡도는 $O(n^{2})$
공간 복잡도는 $O(n)$
코드

def bubbleSort(x):
	length = len(x)-1
	for i in range(length):
		for j in range(length-i):
			if x[j] > x[j+1]:
				x[j], x[j+1] = x[j+1], x[j]
	return x

병합 정렬 (Merge sort)

분할 정복(Divide and conquer) 방식으로 설계된 알고리즘
- 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결하나가는 방식
- 분할은 배열의 크기가 1보다 작거나 같을때까지 반복함
입력으로 받은 배열을 연산 중 두개의 배열로 계속 쪼개 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력
합병은 두개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나감
오름차순의 경우 배열 A, B를 비교하여 A에 있는 값이 더 작다면 새 배열에 저장하고, A 인덱스를 증가시킨 후 A, B의 반복을 진행
이는 A나 B중 하나가 모든 배열값들을 새 배열에 저장할 때 까지 반복하며, 전부 다 저장하지 못한 배열의 값들을 모두 새 배열의 값에 저장함
분할 알고리즘
- 현재 배열을 반으로 쪼갠다.
- 배열의 시작 위치와 종료 위치를 입력받아 둘을 더한 후 2로 나눠 그 위치를 기준으로 나눔
- 이를 쪼갠 배열의 크기가 0이거나 1일때까지 반복
합병 알고리즘
- 두 배열 A, B의 크기를 비교, 각각의 배열의 현재 인덱스를 i, j로 가정
- i에는 A 배열의 시작 인덱스를, j 에는 B 배열의 시작 주소를 저장
- A[i]와 B[j]를 비교, 오름차순의 경우 이중 작은 값을 새 배열 C에 저장
- A[i]가 더 컷다면 A[i]의 값을 배열 C에 저장하고, i의 값을 하나 증가
- 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달할 때 까지 반복
- 끝까지 저장을 못한 배열의 값을 순서대로 전부 다 C에 저장
- C 배열을 원래의 배열에 저장

시간의 복잡도는 $O(n log n)$
공간의 복잡도는 $O(n)$

def merge_sort(list):
    if len(list) <= 1:
        return list
    mid = len(list) // 2
    leftList = list[:mid]
    rightList = list[mid:]
    leftList = merge_sort(leftList)
    rightList = merge_sort(rightList)
    return merge(leftList, rightList)

퀵 정렬 (Quick sort)

분할 정복을 이용하여 정렬을 수행하는 알고리즘
Pivot point라고 기준이 되는 값 하나를 설정해 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬
이를 반복해 분할된 배열 크기가 1이 되면 배열이 모두 정렬된 것
알고리즘
- Pivot point로 잡을 배열의 값 하나를 정함. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열 값 중 중간값이나 랜덤값으로 정함
- 분할 전에 비교 진행을 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장하는 right 변수 생성
- right부터 비교를 진행. 비교는 right가 left보다 클 때만 반복하며, 비교한 배열값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복
- pivot point보다 작은 배열 값을 찾으면 반복을 중지
- 그 다음 left부터 비교를 진행, 비교는 right가 left보다 클 때만 반복하며 비교한 배열값이 pivot point보다 작으면 left를 하나 증가시키고 비교를 반복
- pivot point보다 큰 배열 값을 찾으면 반복을 중지
- left 인덱스의 값과 right 인덱스의 값을 바꿔줌
- 위 3, 4, 5, 6, 7번째 과정을 left<right 관계가 만족할 때 까지 반복
- 위 과정이 끝나면 left의 갑소가 pivot point를 바꿔줌
- 맨 왼쪽부터 left - 1까지, left + 1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복

시간의 복잡도는 $O(n log n)$
코드

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)

힙 정렬 (Heap sort)

자료구조 힙은 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조
최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조
힙은 한 노드가 최대 두 개의 자식 노드를 가지면서, 마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 완전이진트리를 기본으로 함

힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 됨.
알고리즘
- n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.
- 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
- 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
- 2번째와 3번째를 반복한다.

시간 복잡도는 $O(n log n)$
공간 복잡도는 $O(1)$

코드

def heapify(unsorted, index, heap_size):
  largest = index
  left_index = 2 * index + 1
  right_index = 2 * index + 2
  if left_index < heap_size and unsorted[left_index] > unsorted[largest]:
      largest = left_index
  if right_index < heap_size and unsorted[right_index] > unsorted[largest]:
      largest = right_index
  if largest != index:
      unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
      heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):
  n = len(unsorted)
  # BUILD-MAX-HEAP (A) : 위의 1단계
  # 인덱스 : (n을 2로 나눈 몫-1)~0
  # 최초 힙 구성시 배열의 중간부터 시작하면 
  # 이진트리 성질에 의해 모든 요소값을 
  # 서로 한번씩 비교할 수 있게 됨 : O(n)
  for i in range(n // 2 - 1, -1, -1):
      heapify(unsorted, i, n)
  # Recurrent (B) : 2~4단계
  # 한번 힙이 구성되면 개별 노드는
  # 최악의 경우에도 트리의 높이(logn)
  # 만큼의 자리 이동을 하게 됨
  # 이런 노드들이 n개 있으므로 : O(nlogn)
  for i in range(n - 1, 0, -1):
      unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
      heapify(unsorted, 0, i)
  return unsorted

카운팅 정렬 (Counting sort)

각 숫자가 몇번 등장했는지 세어서 정렬
모든 숫자의 개수를 센 후, 누적 합을 구하고, 다시 숫자를 넣어주면 됨
예시
- [3,4,0,1,2,4,2,4], [개수를 저장할 공간], [결과]
- 개수를 저장할 공간을 정렬할 제일 큰 수의 갯수만큼 0으로 만들어줌
- [3,4,0,1,2,4,2,4], [0,0,0,0,0], [결과]
- 처음부터 개수를 세어 저장
  - 0은 1개, 1은 1개, 2는 2개, 3은 1개, 4는 3개
- [3,4,0,1,2,4,2,4], [1,1,2,1,3], [결과]
- 개수를 저장한 것을 누적합으로 바꿔줌
  - 순서대로 1, 2, 4, 5, 8
- [3,4,0,1,2,4,2,4], [1,2,4,5,8], [결과]
- 누적합을 바탕으로 숫자를 결과에 넣어줌
  - 0은 1에, 1은 2에, 2는 3~4에 3은 5에, 4는 6~8에 넣어줌
- [3,4,0,1,2,4,2,4], [1,2,4,5,8], [0,1,2,2,3,4,4,4]
누적합이 바로 숫자들의 인덱스 역할을 하며, 1,3,4,7이 있으면 1은 0~1 사이에, 2는 1~3 사이에, 3은 3~4 사이에, 4는 4~7 사이에 넣으라는 의미
코드

# A: input array
# k: maximum value of A
def counting_sort(A, k):
    
    # B: output array
    # init with -1
    B = [-1] * len(A)
    
    # C: counting array
    # init with zeros
    C = [0] * (k + 1)
    
    # count occurences
    for a in A:
        C[a] += 1
    
    # update C
    for i in range(k):
        C[i+1] += C[i]
    
    # update B
    for j in reversed(range(len(A))):
    	B[C[A[j]] - 1] = A[j]
    	C[A[j]] -= 1

    return B

시간의 복잡도는 $O(n+k)$이나, k가 크면 그만큼 쓸데없는 연산이 많아져 굉장히 비효율적

기수 정렬 (Radix sort)

낮은 자리 수부터 비교하여 정렬해 간다는 것을 기본으로 하는 정렬 알고리즘
자릿수가 고저오디어 있어 안정성이 있음
비교 연산을 하지 않으며, 전체 시간 복잡도가 낮아($O(dn)$) 정수와 같은 자료의 정렬 속도가 매우 빠름
하지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요
정렬 방법의 특성상 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없음
예시
- 입력한 수열은 몇 개의 키로 분류됨. 예를 들어 3자리 이하 수라면 1의자리, 10의자리, 100의자리로 나누어 분류됨. 각각의 키에 대해 하위 키부터 정렬
- [170, 45, 75, 90, 2, 24, 802, 66]이 주어진 경우, 수열의 1의 자리만 보고 정렬을 수행하면
- [170, 90, 2, 802, 24, 45, 75, 66]이 됨. 이를 갖고 다시 10의 자리에 대해 정렬하면
- [2, 802, 24, 45, 66, 170, 75, 90]이 됨. 마지막으로 100의 자리에 대해 정렬을 하면
- [2, 24, 45, 66, 75, 90, 170, 802]이 되어 정렬이 완료됨
시간 복잡도는 $O(dn)$

코드

def radix_sort(a, base=10):
  size = len(a)
  maxval = max(a)
  exp = 1
  while exp <= maxval:
      output = [0]*size
      count = [0]*base
      for i in range(size): count[(a[i]//exp)%base] += 1
      for i in range(1,base): count[i]+=count[i-1]
      for i in range(size-1,-1,-1):
      	j = (a[i]//exp)%base
      	output[count[j]-1] = a[i]
      	count[j] -= 1
      for i in range(size): a[i]=output[i]
      exp *= base
arr = [9,1,22,4,0,1,22,100,10]
radix_sort( arr )
print( arr )
# [0, 1, 1, 4, 9, 10, 22, 22, 100]

Things to do…

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/ 에서 heap에 대해 자세히 공부하기

[참고글]

위키피디아

https://hsp1116.tistory.com/33

https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/

https://www.zerocho.com/category/Algorithm/post/58006da88475ed00152d6c4b

Seongkyun Han's blog

선택/삽입/거품/병합/힙/카운팅/기수정렬 알고리즘

선택/삽입/거품/병합/힙/카운팅/기수정렬 알고리즘

선택 정렬 (Selection Sort)

삽입 정렬 (Insertion Sort)

거품 정렬 (Bubble Sort)

병합 정렬 (Merge sort)

퀵 정렬 (Quick sort)

힙 정렬 (Heap sort)

카운팅 정렬 (Counting sort)

기수 정렬 (Radix sort)

Things to do…

Related Posts

알고리즘 포스팅 글 관련 사항 16 Jun 2020

2D convolution methods 30 Jan 2020

Semantic Segmentation (FCN, Fully Convolutional Network) 08 Dec 2019