[ Python | 파이썬 ] 정렬 알고리즘 정리 및 코드

🌏 Sorting 정렬

정렬이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미한다.

정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘이며 코딩테스트에서도 자주 출제되는 알고리즘 중 하나이기 때문에 확실하게 정리하고 넘어가보자!

---

👽 Bubble Sort 거품 정렬

정렬의 과정에서 데이터의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 정렬이라 한다고 함!

서로 인접한 두 데이터의 크기를 비교하여 데이터의 위치를 바꾸는 과정을 반복하는 알고리즘

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

 

👽 Selection Sort 선택 정렬

 

데이터가 무작위로 여러개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는 것 ➡️ 다시말해, 매번 가장 작은 데이터값을 선택한다!

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

 

👽 Insertion Sort 삽입 정렬

 

특정한 데이터를 적절한 위치에 삽입하는 알고리즘 ➡️ 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정하며. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤 그 위치에 데이터를 삽입한다!

def insertionSort():
	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

 

 

👽 Quick Sort 퀵 정렬

퀵 정렬은 가장 많이 사용되는 정렬 알고리즘으로, 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

def quick_sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]
    
    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

 

👽 Merge Sort 병합 정렬 / 합병 정렬

병합 정렬은 데이터를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식 ➡️ 쪼개는 방식은 퀵정렬과 유사하다!

1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. 
2. 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 마지막 남은 부분리스트가 정렬된 리스트이다.

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    L = [0] * (n1)
    R = [0] * (n2)

    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

    i, j, k = 0, 0, l

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1


def mergeSort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2

        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)


mergeSort(arr, 0, len(arr) - 1)

👽 Heap Sort 힙 정렬

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.
2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.
4. 2와 3을 반복한다.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        (arr[i], arr[largest]) = (arr[largest], arr[i])
        heapify(arr, n, largest)


def heapSort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

heapSort(arr)

👽 Radix Sort 기수정렬

기수 정렬은 자릿수 별로 비교 없이 수행하는 정렬 알고리즘

➡️ 비교 연산을 하지 않기 때문에 정렬 속도가 빠르지만 기수 테이블의 크기만한 메모리가 더 필요하다는 단점이 있다! ➡️ 또한 각 자릿수를 이용하여 정렬을 수행하기 때문에 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능하다!

def countingSort(arr, exp1):
	n = len(arr)
	output = [0] * (n)

	count = [0] * (10)

	for i in range(0, n):
		index = arr[i] // exp1
		count[index % 10] += 1

	for i in range(1, 10):
		count[i] += count[i - 1]

	i = n - 1
	while i >= 0:
		index = arr[i] // exp1
		output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1

	i = 0
	for i in range(0, len(arr)):
		arr[i] = output[i]

def radixSort(arr):
	max1 = max(arr)
	exp = 1
	while max1 / exp >= 1:
		countingSort(arr, exp)
		exp *= 10

radixSort(arr)

👽 Counting Sort 계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘. ➡️ 배열의 데이터 개수가 배열 내의 최대 값의 길이보다 작을때 매우 유용한 알고리즘!

def countSort(arr):
	output = [0 for i in range(len(arr))]
	count = [0 for i in range(256)]

	for i in arr:
		count[ord(i)] += 1

	for i in range(256):
		count[i] += count[i-1]

	for i in range(len(arr)):
		output[count[ord(arr[i])]-1] = arr[i]
		count[ord(arr[i])] -= 1

	return output

 

 

💫 알고리즘 별 시간복잡도 및 공간복잡도

정렬 알고리즘	시간복잡도	공간복잡도
Bubble Sort	O(n^2)	O(1)
Selection Sort	O(n^2)	O(1)
Insertion Sort	O(n^2)	O(1)
Quick Sort	O(nlogn)	O(logn)
Merge Sort	O(nlogn)	O(n)
Heap Sort	O(nlogn)	O(1)
Radix Sort	O(nk)	O(n+k)	k는 최대 자릿수
Counting Sort	O(n+k)	O(k)	k는 배열 내 최댓값의 길이

 

 

이제 정렬은 안심하고 두들겨팰 수 있다 아자!