[알고리즘] 정렬 알고리즘 (Sorting Algorithm) (버블정렬, 선택정렬, 삽입정렬)

정렬 알고리즘

n개의 원소를 기준에 맞게 열거하는 알고리즘

 

구현이 간단한 경우는 시간복잡도가 비효율적

시간 복잡도가 효율적인 경우는 구현이 복잡함

 

1. 버블/거품 정렬 (Bubble Sort)

서로 인접한 두 원소의 대소를 비교 및 교환

 

 

구현이 쉽고 간단하지만 효율이 좋지 않다.

 

시간 복잡도

평균 시간 복잡도는 $O(n^2)$

 

비교

한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어든다.

전체 원소의 개수가 n이라고 하면 n-1번 순회를 하면 정렬이 끝난다.

위 그림에서는 원소의 개수가 5개이므로 4+3+2=10번의 비교를 하게 된다.

일반화 수식은 아래와 같다. 
$$(n-1)+(n-2)+...+2+1 = {n*(n-1)\over2}$$

 

자리 교환

최선의 경우: 자리 교환이 한번도 이루어 지지 않기 때문에 영향을 미치지 않게 된다.

최악의 경우: 원소를 비교할 때마다 자리 교환이 이루어 지므로 비교 횟수와 같이 $n*(n-1)\over2$가 된다.

 

구현 코드- 파이썬

def bubbleSort(arr):
    for i in range(len(arr)):
        for idx in range(len(arr)-i-1):
            if arr[idx] > arr[idx+1]:
                arr[idx], arr[idx+1] = arr[idx+1], arr[idx]

 

 

2. 선택 정렬 (Selection Sort)

위치를 정해놓고 그 자리에 오는 원소를 찾는 방식

 

버블 정렬과 유사한 알고리즘으로, 구현은 단순하나 시간복잡도가 비효율적이다.

비교 연산 횟수가 교환 연산 횟수보다 많기 때문에 버블 정렬보단 효율적이다.

 

과정

1. 주어진 배열 중 최소값을 찾는다.

2. 그 값을 가장 앞에 위치한 값과 교체한다.

3. 가장 앞에 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

하나의 원소만 남을 때까지 과정을 반복한다.

 

시간복잡도

평균 시간 복잡도는 $O(n^2)$

 

비교

버블 정렬과 마찬가지로 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어든다.

 

교환 

상수 시간 작업이다. (0 ~ n = 교환 안하는 경우 ~ 매번 교환하는 경우)

 

구현 코드- 파이썬

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

 

 

3. 삽입 정렬 (Insertion Sort)

앞에서 차례대로 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 삽입

 

배열의 길이가 길어질수록 비효율적이다.

 

과정

1. 현재 원소와 이전 위치에 있는 원소들을 비교한다.

2. 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입한다.

반복

 

시간복잡도

평균 시간복잡도는 $O(n^2)$
최선의 경우 $O(n)$, 최악일 경우 $O(n^2)$

비교

최선의 경우: 순회 한 번에 한 번의 비교 ($n$)

최악의 경우: 원소의 개수가 n이라 고 하면 n-1번 비교, 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어든다. ($n*(n-1)\over2$)

 

교환

최선, 최악의 경우: 순회 한 번에 한 번 교환 

 

구현 코드- 파이썬

def insertionSort(arr):
    for i in range(1, len(arr)):
        insert_value = arr[i]
        j = i
        while j > 0 and arr[j-1] > insert_value:
            arr[j] = arr[j-1]
            j-=1
        arr[j] = insert_value
    return arr