[알고리즘/정렬] 선택, 버블, 삽입, 병합, 퀵, 힙

프로그래밍 중에 배열이나 리스트 등을 정렬해야 할 때가 있다.

그런 때 사용하는 정렬 알고리즘을 몇 가지 알아보도록 하자.

 

선택 정렬

배열의 가장 큰(또는 가장 작은)원소를 배열의 끝으로 옮기는 작업을 반복해서 배열을 정렬한다.

동작 과정

1. 최대 원소(또는 최소 원소)를 찾는다.
2. 최대 원소(또는 최소 원소)와 배열의 끝에 있는 원소를 교환한다.
3. 배열 끝의 원소를 다음 반복에서 제외한다.
4. 1~3번을 원소가 하나 남을 때까지 반복한다.

 

코드

def selectionSort(list):
    max = 0
    if len(list) <= 1:
        return list
    for i in range(len(list)-1, 0, -1):
        for j in range(i+1):
            if max <= list[j]:
                max = list[j]
        list[i], list[list.index(max)] = list[list.index(max)], list[i]
        max = 0
    return list

 

성능

중첩for문을 사용하기 때문에 수행시간은 O(n^2)이다.

---

버블 정렬

이웃한 두 원소를 비교해서 가장 큰(또는 작은)원소를 끝자리로 옮기는 작업을 반복한다.

동작 과정

1. 왼쪽부터 차례로 이웃한 수와 값을 비교한다.
2. 오른쪽 원소가 왼쪽 원소보다 크면(또는 작으면) 두 원소를 교환한다.
3. 가장 오른쪽 원소를 다음 반복에서 제외한다.
4. 1~3의 작업을 하나의 원소만 남을 때까지 반복한다.

 

코드

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

 

성능

중첩for문을 사용하기 때문에 수행 시간은 O(n^2)가 소요된다.

---

삽입 정렬

배열에 원소를 추가하는 시점에 정렬한다.

동작 과정

1. 가장 왼쪽 원소부터 차례대로 하나씩 subset에 추가한다.
2. subset에 추가되는 원소의 위치를 크기에 따라 적절히 선택한다.
   2-1. subset의 가장 오른쪽 원소부터 차례대로 크기를 비교한다.
   2-2. 새롭게 추가되는 원소보다 작은 원소가 나올 때까지 비교를 반복한다.
3. 해당 위치의 바로 오른쪽에 원소를 새로 추가한다.
4. 1~3의 작업을 배열의 끝까지 반복한다.

 

코드

def insertionSort(list):
    if len(list) <= 1:
        return list

    resList = []
    for i in range(0, len(list)):
        if not resList:
            resList.append(list[i])
        else:
            for j in range(i-1, -1, -1):
                if resList[j] <= list[i]:			부호 < : 오름차순, > : 내림차순
                    resList.insert(j+1, list[i])
                    break
                elif j == 0:
                    resList.insert(0, list[i])
    return resList

print(insertionSort(list))

 

성능

for루프가 n-1회 반복, 원소 삽입 시 비교를 최악의 경우 i-1회 비교하기 떄문에 수행 시간은 O(n^2)가 된다.

---

병합 정렬

동작 과정

1. 배열을 중앙 원소를 기준으로 둘로 나눈다.
2. 각각의 배열을 순서에 맞춰서 정렬한다.
3. 순서에 맞도록 각 배열에서 원소를 하나씩 뽑아내 다시 하나의 배열로 재조합한다.
4. 1~3의 작업을 재귀적으로 반복한다.

 

코드

def mergeSort(list):
    if len(list) <= 1:
        return list

    mid = len(list) // 2
    left = mergeSort(list[:mid])
    right = mergeSort(list[mid:])
    return merge(left, right)

def merge(left, right):
    res = []

    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] >= right[0]:				부호 > : 내림차순, < : 오름차순
                res.append(left[0])
                left = left[1:]
            else:
                res.append(right[0])
                right = right[1:]
        elif len(left) > 0:
            res.append(left[0])
            left = left[1:]
        else:
            res.append(right[0])
            right = right[1:]

    return res

print(mergeSort(list))

 

성능

수행 시간은 O(nlogn)이 소요된다.

---

퀵 정렬

배열을 기준원소 중심으로 해당 원소보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 재배치한다.

각 부분마다 따로 정렬하여 이 과정을 재귀적으로 반복한다.

동작 과정

1. 배열을 기준원소를 중심으로 기준원소보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 재배치한다.
2. 나뉘어진 배열들을 각각 정렬한다.
3. 1~2를 재귀적으로 반복한다.

 

코드

def quickSort(list, start, end):
    if start < end:
        pivot = partition(list, start, end)
        quickSort(list, start, pivot-1)
        quickSort(list, pivot+1, end)
    return list

def partition(list, start, end):
    pivot = list[end]
    i = start-1

    for j in range(start, end):
        if list[j] <= pivot:					부호 < : 내림차순, > : 오름차순
            i += 1
            list[i], list[j] = list[j], list[i]
    list[i+1], list[end] = list[end], list[i+1]
    return i+1

print(quickSort(list, 0, len(list)-1))

 

성능

수행 시간은 평균적으로 O(nlogn)이 수행된다. 하지만 최악의 경우 O(n^2)가 수행된다.

---

힙 정렬

최대 힙 또는 최소 힙 트리를 구성해 정렬을 수행한다.

동작 과정

1. 배열의 원소 수 n개의 힙을 만든다.
2. 해당 힙을 완전 이진 트리 형태로 만든다.
3. 트리의 가장 끝 원소를 꺼내어 배열에 저장하고, 해당 원소는 트리에서 제외한다.
4. 1~3의 작업을 재귀적으로 반복한다.

 

코드

def select(list, start, end, i):
    if start == end:
        return list[start]
    pivot = partition(list, start, end)
    k = pivot-start+1
    if i < k:
        return select(list, start, pivot-1, i)
    elif i == k:
        return list[pivot]
    else:
        return select(list, pivot+1, end, i-k)

def partition(list, start, end):
    x = list[end]
    i = start-1
    for k in range(start, end):
        if list[k] >= x:				부호 > : i번쨰로 큰 수, < : i번째로 작은 수
            i += 1
            list[i], list[k] = list[k], list[i]
    list[i+1], list[end] = list[end], list[i+1]
    return i+1

sel = select(list, 0, len(list)-1, 1)
print(sel)

 

성능

수행 시간은 최악의 경우에도 O(nlogn)이 소요된다.