기본정렬 알고리즘 (Sorting 기법 정리(Bubble,Selection,Quick,Heap,Insertion,Merge))

학교를 다니면서 알고리즘은 많이 배웠는데 제대로 써먹어본적이 없고 머리에 정리가 제대로 정립이 안된거 같아서 한번 정리해보려구요!!! 총 6가지 sorting 기법만 우선 정리해볼께용~~

1. Bubble Sort

버블 정렬은 매번 연속된 두개의 인덱스 값을 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법입니다.

오름차순으로 정렬하려고 하면, 비교할때 마다 큰 값이 뒤로 이동하면서 한바퀴 돌면 가장 큰 값이 맨 뒤에 저장됩니다.

맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에,(전체 배열의 크기- 현재까지 순환한 바퀴수)만큼만 반복하는 알고리즘입니다!! 백문이 불여일견이라 그림으로 보고 가실께용

출처https://sylagape1231.tistory.com/17

이 알고리즘은 1부터 비교를 시작하면서 n-1,n-2,....1개씩 비교를 반복하면서 배열이 어떻게 되어있던 전체 비교를 진행하므로 시간복잡도는 O(N^2)입니다. 공간복잡도도 이 또한 단 하나의 배열에서만 진행하고 추가로 메모리를 할당하지 않으므로 O(N)입니다.

버블정렬 python 소스 코드

def bubble_sort(arr):
    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[j]

 

2.Selection sort

선택 정렬은 현재 위치에 들어갈 값을 찾아 정렬하는 배열입니다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 오름차순으로 정렬할껀지, 내림차순으로 정렬될건지 구할 수 있습니다.

1. 정렬 되지 않은 인덱스의 맨 앞에서부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.
2. 가장 작은 값을 찾으면, 그값을 현재 인덱스의 값과 바꿔준다
3. 다음 인덱스에서 위 과정을 반복해준다

출처:https://s-satsangi.medium.com/insertion-sort-selection-sort-and-bubble-sort-5eb16d55a4de

이 알고리즘은 1부터 비교를 시작하면서 n-1,n-2,....1개씩 비교를 반복하면서 배열이 어떻게 되어있던 전체 비교를 진행하므로 시간복잡도는 O(N^2)입니다. 공간복잡도도 이 또한 단 하나의 배열에서만 진행하고 추가로 메모리를 할당하지 않으므로 O(N)입니다.

장점으로 비교횟수는 많아도 실제로 교환하는 횟수는 적어서 자주 사용하는 알고리즘입니다.

선택정렬 python 수도코드

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

3.QuickSort

얘는 이름만 봐도 약간 떨리는..(시험시간때 공부하다 머리를 다 뽑아버릴뻔 했다는...) 

퀵 정렬은 Divide&Conquer을 이용하여 정렬을 수행하는 알고리즘입니다. pivot point라고 기준이 되는값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값을 오른쪽으로 옮기는 방식으로 정렬을 진행합니다. 이를 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된 것입니다.

1. pivot point로 잡을 배열의 값 하나를 정합니다.(이게 사실 젤 중요 이유는 나중에!)
2. pivot point을 설정한 후,pivot을 기준으로 왼쪽에서는 pivot보다 큰 데이터를 찾고, 오른쪽에서는 pivot보다 작은 데이터를 찾아서 서로 위치를 교환합니다.
3. 1,2 번의 과정을 반복합니다.

출처:https://en.m.wikipedia.org/wiki/File:Quicksort-example.gif

퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘르고, 각 정렬은 배열의 크기 N만큼 비교하면, logN만큼 깊이가 생기므로 총 비교횟수는 NlogN, 평균 시간복잡도는 O(NlogN)입니다.

퀵 정렬은 최악의 경우가 존재하는데, 이는 배열이 이미 정렬되어있는 경우입니다! 이 경우 분할이 N만큼 일어나므로 시간복잡도는 O(N^2)입니다. 이를 방지하기 위해 언급했던 전체 배열 값 중 중간값이나 랜덤값으로 pivot point를 정하는 방법을 쓰기도 합니다.

 

퀵 정렬 python 수도코드

def quick_sort(arr, first, last):
	if first >= last:
		return

	mid = partition(arr, first, last)

	quick_sort(arr, first, mid-1)
	quick_sort(arr, mid, last)

	return arr

def partition(arr, first, last):
	pivot = arr[(first + last) // 2]

	while first <= last:
		while arr[first] < pivot:
			first += 1
		
		while arr[last] > pivot:
			last -= 1
		
		if first <= last:
			arr[first], arr[last] = arr[last], arr[first]
			first, last = first + 1, last - 1
		
	return first

 

4.Heapsort

힙 정렬을 말하기 전에 힙에 대해서 알아야합니다. 힙은 크기를 중심으로 정렬된 시퀀스를 활용할 떄 유용한 자료구조입니다. 힙은 한 노드가 최대 두개의 자식노드를 가지면서 마지막 레벨을 제외한 모든 레벨에서 완전 이진 트리(complete binary tree)를 기본으로 구조를 가지고 있습니다. 각 노드의 값은 자신의 자식노드보다 크거나 같습니다. 이진 탐색 트리에서는 자식의 노드가 부모의 노드보다 값이 클 수도 있습니다. 

출처:https://en.m.wikipedia.org/wiki/File:Heapsort-example.gif

heapsort은 n개의 정렬을 logN만큼의 깊이가 생기므로 항상 O(NlogN)입니다.

heapsort python 수도코드

def heapify(unsorted, index, heap_size):
  largest = index
  left = 2 * index + 1
  right = 2 * index + 2
  
  if left < heap_size and unsorted[right] > unsorted[largest]:
    largest = left
    
  if right < heap_size and unsorted[right] > unsorted[largest]:
    largest = right
    
  if largest != index:
    unsorted[largest], unsorted[index] = unsorted[index], unsorted[largest]
    heapify(unsorted, largest, heap_size)

def heap_sort(unsorted):
  n = len(unsorted)
  
  for i in range(n // 2 - 1, -1, -1):
    heapify(unsorted, i, n)
    
  for i in range(n - 1, 0, -1):
    unsorted[0], unsorted[i] = unsorted[i], unsorted[0]
    heapify(unsorted, 0, i)

  return unsorted

 

5.Insertion sort

삽입 정렬은 데이터를 하나씩 확인하면서, 각 데이터를 적절한 위치에 삽입하는 방법입니다. 적절한 위치에 삽입한다는 의미에서 삽입정렬이라 부르는데, 선택 정렬처럼 동작을 직관적으로 이해하기 쉽지만, 선택 정렬보다는 구현 난이도가 높고 실행시간 면에서 더 효율적입니다.

 

출처:https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

삽입정렬은 최선은 O(N), worst case에서는 O(N^2)입니다.

삽입정렬 수도코드

for i in range(1, len(array)):
    for j in range(i, 0, -1): 
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

6.Merge sort

합병 정렬은 Heapsort와 같은 의미로 분할정복(Divide and Conquer)방식으로 설계된 알고리즘입니다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을때까지 반복합니다 입력으로 하나의 배열을 받고, 연산 중에 두개의 배열로 계속 쪼개 나간뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력합니다.

출처:https://levelup.gitconnected.com/sorting-algorithms-selection-sort-bubble-sort-merge-sort-and-quicksort-75479f8f80b1

MergeSort도 O(NlogN)이라는 시간복잡도를 가지지만, 추가 메모리를 할당하면서 공간복잡도는 2N만큼 생깁니다.

 

mergesort 수도코드

def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

 

 

 

지금까지 제가 배운 sort 알고리즘에 대해서 한번 정리했습니다!! 다행히 머릿속에 남아있을떄 해서 다행인거같네요 ㅎㅎ 다음번 개인공부는 Search기법으로 찾아오겠습니다~~