정렬 알고리즘(sorting algorithm) 정리 -1

수많은 정렬 알고리즘 중 대표적인 5가지 정렬 알고리즘에 대해서 정리해보려고 한다.

• 버블 정렬(bubble sorting)
• 선택 정렬(Selection sorting)
• 삽입 정렬(insertion sorting)
• 병합 정렬(Merge sorting)
• 퀵 정렬(Quick sorting)
• 셸 정렬(shell sorting)
• 힙 정렬(heap sorting)

---

우선 시간복잡도 기준으로 나눠보자

• O(N²)
  • 버블 정렬
  • 선택 정렬
  • 삽입 정렬
• O(N log₂ N)
  • 병합 정렬
  • 퀵 정렬
  • 셸 정렬
  • 힙 정렬

아래에 있는 정렬들이 일단 시간복잡도가 더 빠르니 성능이 좋은 정렬 알고리즘이라 생각해도 될 것 같다.

그러나 언제나 그렇듯 모든 상황에서 아래의 알고리즘이 더 좋다고 단정지을 수는 없다.

---

1. 버블 정렬(Bubble sorting)

서로 이웃한 두 원소의 크기를 비교한 결과에 따라 교환을 반복하는 알고리즘이다.

가장 간단한 정렬 알고리즘 중 하나이며 동시에 비효율적인 정렬 알고리즘이다

단순 교환 정렬이라고도 한다.

참고로 양방향으로 번갈아서 수행하면 칵테일정렬이 된다

 

버블소트가 작동하는 과정.

내가 쉽게 이해한 방법은

그냥 앞에서부터 순서대로 하나하나씩 크기 비교하면서 자리를 바꿔주다보면

결국 오름차순으로 정렬이 된다는 아이디어다.

 

- 시간복잡도

최선의 경우 O(N)

최악의 경우 O(N²)

 

하지만 시간복잡도는 최악의 경우를 따지므로 거품정렬의 시간복잡도는 O(N²)이다.

 

<의사코드>
bubbleSort(list):
    length = length of list         -- 리스트의 길이를 변수에 저장
    for i = 1 to length -1 :        -- 첫번째 반복문 =>한번 돌면 제일 큰 수가 리스트의 마지막에 위치하게 된다
        for j = 1 to length - i - 1 -- 두번째 반복문 => 인접한 숫자들끼리 비교
            if li[j] > li[j+1]:           -- 앞의 수가 뒤의 숫자보다 크면
                li[j] swap li[j+1]      -- 서로 위치를 바꿔준다(swap)

기본적으로 반복문이 두번 돌아가므로 시간복잡도는 O(N²)이다.

# python 
# bubble sort

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

원소들이 정렬되는 모습이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 bubble sort라고 불린다고 한다. (출처: 위키백과)

2. 선택정렬(Selection sorting)

가장 작은 숫자를 고른뒤 맨 앞의 숫자와 차례차례 바꿔주는 알고리즘이다.

버블정렬과 같이 구현은 간단하지만 비효율적인 알고리즘이다.

선택정렬 에니메이션

다음과 같은 순서로 정렬이 이루어진다

 1. 주어진 리스트 중 최소값을 찾고

 2. 그 최소값과 맨 앞의 숫자와 자리를 바꿔준다.

 3. 맨 처음 숫자 이후부터 위의 과정을 반복한다.

 

큰 배열보다 작은 배열에서는 합병정렬(merge sort)보다 더 빠르다고 한다.

큰 배열에선 비효율적이지만 작은 배열에서는 쓸모가 있다고 한다.

 

- 시간복잡도 

최선의 경우 O(N²)

최악의 경우 O(N²)

선택정렬은 언제나 시간복잡도가 O(N²)이다. 

https://www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

위의 사이트에서 selection sorting을 다른 알고리즘과 비교해보면 굉장히 하나하나 느긋느긋하게 정렬하는 모습을 볼 수 있다. (답답함이 느껴지는...)

 

<의사코드>
selectionSort(list):
    for i = 0 to n:
        a[i]부터 a[n - 1]까지 차례로 비교하여 가장 작은 값이 a[j]에 있다고 하자.
        a[i]와 a[j]의 값을 서로 맞바꾼다.

# python
# selection sorting

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

 

3. 삽입정렬(insert sorting)

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘이다.

 

처음에 이 설명을 들었을때 무슨말인가 잘 모르겠어서 가만히 생각해보다가 아래의 예제를 보면서 이해할 수 있었다.

 

출처 위키피디아

그냥 정렬하고자 하는 리스트에서 두번째 인덱스부터 자기 자리를 찾아 앞으로 삽입하면서 오름차순 정렬하는 아이디어이다.

숫자를 리스트에서 하나씩 빼서 알맞은 자리에 꽂아준다는 의미에서 삽입정렬이라고 부르는듯 하다.

 

다음과 같은 순서로 정렬이 이루어진다.

(두번째 인덱스 숫자부터 차례차례 정렬이 이루어진다)

 1. 정렬하고자 하는 숫자의 앞쪽에 정렬되지 않은 배열과 비교한다.

 2. 정렬되지 않은 앞쪽 배열에서 정렬하고자 하는 숫자보다 큰 숫자가 나타나면 비교를 멈춘다

 3. 정렬하고자 하는 숫자를 그 자리에 삽입한다.

 4. 마지막 숫자까지 위의 과정을 반복한다.

- 시간복잡도

최선의 경우 O(N)

최악의 경우 O(N²)

 

최선의 경우는 이미 오름차순으로 정렬되어 있는 경우이다.

각 자리에 올바르게 정렬되어있는지 확인하기만 하면 되니깐 시간복잡도는 O(N)이다

 

최악의 경우는 내림차순으로 정렬되어 있는 경우이다.

내림차순을 오름차순으로 바꾸려면 높은 숫자들을 모두 오른쪽으로 이동하면서 최대 반복을 해야하므로 시간복잡도는 O(N²)이다

 

이 정렬방법도 단순하지만 비효율적이라는 특징이 있다.

소량의 데이터를 정렬할 때 유용하게 쓰인다.

 

<의사코드>

insertSort(list):
    length = length of list
    for i = 1 to length:
        target_num = i번째 숫자 (비교하려는 숫자)
        unsorted_arr = i번째 숫자 바로전까지 정렬되지 않은 배열
        while target_num < unsorted_arr(i-1):
            n -= 1 (unsorted_arr에서 n을 1씩 감소시키며 비교)
        unsorted_arr(n) swap target_num

(왜지.. 의사코드를 쓰고보니 더 어려워진거 같다..;;)

# python
# insertion sorting

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1                    # unsorted_arr를 구하기 위한 인덱스
		key = x[i]                   # 비교하려는 수
		while x[j] > key and j >= 0: # unsorted_arr에서 key보다 큰 수가 나올때까지 반복
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x

나머지 병합정렬, 퀵정렬, 힙정렬, 셸정렬은 다음 블로그때 정리해볼께요~

읽어주셔서 감사합니다