Sorting (1) - 정렬 알고리즘 구현하기 (Bubble, Selection, Insertion) (with.Python)

Bubble Sort (버블정렬)

• 인접한 두 원소를 검사하여 큰 값이 오른쪽으로 이동하는 과정을 반복하여, 비교했던 모든 값들의 최댓값을 맨 오른쪽으로 옮긴다.
• 시간복잡도가 최악의 경우 (Big O) O(n^2)로 (n-1) + (n-2) + ··· + 1번 비교가 이루어진다. 그러나, 데이터가 잘 정렬되어 있다면 O(n)으로 데이터 정렬 여부를 파악하기 위한 알고리즘으로 사용될 수 있다.

< 버블정렬 >

 

def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def bubbleSort(x):
    for size in reversed(range(len(x))):
        for i in range(size):
            if x[i] > x[i+1]:
                swap(x, i, i+1)
    return x
if __name__ == '__main__':
	x = [4,2,5,1]
    print(bubbleSort(x))

---

Selection Sort (선택정렬)

• 주어진 배열에서 최댓(최솟)값을 찾아 맨 오른쪽(왼쪽) 값과 교체한다. 
• 시간복잡도는 최댓값을 찾아야 하므로 정렬 상태에 관계없이 O(n^2)이다.

< 선택정렬 >

 

def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def selectionSort(x):
    for size in reversed(range(len(x))):
        max_i = 0
        for i in range(1, 1+size):
            if x[i] > x[max_i]:
                max_i = i
    return x
    
if __name__ == '__main__':
    x = [4,2,5,1]
    print(selectionSort(x))

---

Insertion Sort (삽입정렬)

• 작은 원소를 골라 앞쪽부터 정렬한다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위를 찾아 삽입한다.
• 시간복잡도는 버블정렬과 마찬가지로 데이터가 이미 정렬되어 있다면 O(n)이나, 데이터가 역순으로 정렬된 상태라면 삽입을 위해 값을 하나씩 뒤로 밀어내는 과정을 반복하므로 느리다.
• 최악의 경우에는 O(n^2)의 시간복잡도를 가지고 있다.

< 삽입정렬 >

< 삽입 정렬 >

def insertionSort(x):
    for size in range(1, len(x)):
        val = x[size]
        i = size
        while i > 0 and x[i-1] > val:
            x[i] = x[i-1]
            i -= 1
        x[i] = val
    return x

if __name__ == '__main__':
    x = [4,2,5,1]
    print(insertionSort(x))

---

참조

• https://namu.wiki/w/정렬%20알고리즘
• https://en.wikipedia.org/wiki/Sorting_algorithm
• http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html
• https://interactivepython.org/runestone/static/pythonds/index.html#
• http://www.b3ta.com/board/10454738
• https://wayhome25.github.io/cs/2017/04/16/cs-17/