섞여 있는 데이터를 순서대로 나열하는 것
정렬 알고리즘은 시간 복잡도에 따라 성능을 좌우되며 성능이 좋을수록 구현 방법이 어려워집니다.
대표적인 정렬의 종류
O(n²)의 시간 복잡도 (정렬할 자료의 수가 늘어나면 제곱에 비례해서 증가)
- 버블 정렬(Bubble Sort)
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)
O(n log n)의 시간 복잡도
- 병합 정렬(Merge Sort)
- 퀵 정렬(Quick Sort)
버블 정렬(Bubble Sort)
- 인접한 두 수를 비교하며 정렬해나가는 방법으로 O(n²)의 느린 성능을 가지고 있습니다.
- 앞에서부터 시작하여 큰 수를 뒤로 보내 뒤가 가장 큰 값을 가지도록 완성해나가는 방법 또는 뒤에서부터 반복하여 앞의 작은 값부터 정렬을 완성해나가는 방법이 있습니다.
파이썬 예제 코드
버블 정렬# array = [8,4,6,2,9,1,3,7,5]
array = [9,8,7,6,5,4,3,2,1]
def bubble_sort(array):
n = len(array)
for i in range(n - 1):
for j in range(n - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
print(array)
print("before: ",array)
bubble_sort(array)
print("after:", array)결과:
선택 정렬(Selection Sort)
- 한 바퀴 돌 때 가장 작은 값을 찾아 맨 앞과 교환하는 방식의 정렬.
- 앞에서부터 정렬해나가는 특성을 가지고 있고 버블 정렬과 마찬가지로 최악의 성능을 가진 알고리즘입니다.
파이썬 예제 코드
선택 정렬array = [8,4,6,2,9,1,3,7,5]
def selection_sort(array):
n = len(array)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if array[j] < array[min_index]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
print(array[:i+1])
print("before: ",array)
selection_sort(array)
print("after:", array)
결과:
삽입 정렬(Insertion Sort)
- 정렬된 데이터 그룹을 늘려가며 추가되는 데이터는 알맞은 자리에 삽입하는 방식
- 버블 정렬과 선택 정렬과 마찬가지로 최악의 성능인 정렬 알고리즘입니다.
파이썬 예제 코드
삽입 정렬array = [8,4,6,2,9,1,3,7,5]
def insertion_sort(array):
n = len(array)
for i in range(1, n):
for j in range(i, 0, - 1):
if array[j - 1] > array[j]:
array[j - 1], array[j] = array[j], array[j - 1]
print(array[:i+1])
print("before: ",array)
insertion_sort(array)
print("after:", array)
결과:
병합 정렬(Merge Sort)
- 분할 정복과 재귀를 이용한 알고리즘으로 O(n log n)의 시간 복잡도를 가지고 있어 괜찮은 성능을 보여 줍니다.
- 반으로 쪼개고 다시 합치는 과정에서 그룹을 만들어 정렬하게 되며 이 과정에서 2n 개의 공간이 필요합니다.
- 합쳐지는 과정은 다음과 같습니다.
[1,4][2,3] (1과 2 비교) -> 1 선택, 완성된 배열은 [1]
[4][2,3] (4와 2 비교) -> 2 선택, 완성된 배열은 [1,2]
[4][3] (4와 3 비교) -> 3 선택, 완성된 배열은 [1,2,3]
[4][] -> 남는 4 선택, 완성된 배열은 [1,2,3,4] 파이썬 예제 코드
병합 정렬array = [8,4,6,2,9,1,3,7,5]
def merge_sort(array):
if len(array) < 2:
return array
mid = len(array) // 2
low_arr = merge_sort(array[:mid])
high_arr = merge_sort(array[mid:])
merged_arr = []
l = h = 0
while l < len(low_arr) and h < len(high_arr):
if low_arr[l] < high_arr[h]:
merged_arr.append(low_arr[l])
l += 1
else:
merged_arr.append(high_arr[h])
h += 1
merged_arr += low_arr[l:]
merged_arr += high_arr[h:]
print(merged_arr)
return merged_arr
print("before: ",array)
array = merge_sort(array)
print("after:", array)
분할 후 병합 과정:
퀵 정렬(Quick Sort)
- 병합 정렬과 마찬가지로 분할 정복 알고리즘으로 평균적으로 빠른 속도를 수행합니다.
- 추가적인 메모리가 공간이 필요 없다는 장점을 가졌습니다.
- 병합 정렬은 균등하게 분할하였다면 퀵 정렬은 Pivot을 설정하고 그 기준으로 정렬을 합니다.
- 다른 정렬 알고리즘보다 빠르며 많은 언어의 정렬 내장 함수로 퀵 정렬을 수행합니다.
파이썬 예제 코드
퀵 정렬array = [8,4,6,2,5,1,3,7,9]
def quick_sort(array):
if len(array) <= 1:
return array
pivot = len(array) // 2
front_arr, pivot_arr, back_arr = [], [], []
for value in array:
if value < array[pivot]:
front_arr.append(value)
elif value > array[pivot]:
back_arr.append(value)
else:
pivot_arr.append(value)
print(front_arr, pivot_arr, back_arr)
return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)
print("before: ",array)
array = quick_sort(array)
print("after:", array)
피봇 기준 분할 과정:
백엔드 개발을 공부하고 있습니다.
감사합니다 감사합니다.. 큰 도움을 얻었습니다....버블정렬이 뭔지 이거 보구나니까 좀 알거같습니다..