- 정렬 알고리즘 : 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘
- 대표적인 정렬의 종류
1. 버블 정렬 (Bubble Sort) : 두 인접한 원소의 대소를 비교하고, 조건에 따라 자리를 교환하며 정렬하는 방식
- 시간 복잡도
- 평균 : O(n^2)
- 최악 : O(n^2)
- 장점
1) 구현이 매우 간단하고, 소스 코드가 직관적이다.
2) 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬)
3) 중복된 값을 입력 순서와 동일하게 정렬하는 안정 정렬이다.
- 단점
1) 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 굉장히 비효율적이다.
2) 정렬되어 있지 않은 원소가 정렬 되었을 때의 자리로 가기 위해서 교환 연산이 많이 일어난다.
3) 배열의 길이가 길어질수록 비효율적이다.
- 코드
list = [2,1,23,43,53,3,5,4,6]
for i in range(len(list)):
for j in range(i, len(list) - 1):
if list[j] > list[j + 1]:
list[j], list[j + 1] = list[j + 1], list[j]
print(list) # [1, 2, 3, 4, 5, 6, 23, 43, 53]
2. 선택 정렬 (Selection Sort) : 맨 앞부터 끝까지의 위치에 해당 위치보다 다음 인덱스를 검색하여 최솟값을 해당 위치에 넣는 방식
- 시간 복잡도
- 평균 : O(n^2)
- 최악 : O(n^2)
- 장점
1) 구현이 간단하고, 알고리즘이 단순하다.
2) 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. (제자리 정렬)
3) 정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야하는 자료 상태에서 비교적 효율적이다. (예를들어 내림차순으로 정렬되어 있는 자료를 오름차순으로 재정렬할 때 적합)
- 단점
1) 시간복잡도가 O(n^2)으로 비효율적이다.
2) 불안정 정렬이다.
3) 배열의 길이가 길어질수록 비효율적이다.
- 코드
list = [2,1,23,43,53,3,5,4,6]
for i in range(len(list)):
min_index = i
for j in range(i + 1, len(list)):
if list[min_index] > list[j]:
min_index = j
list[i], list[min_index] = list[min_index], list[i]
print(list) # [1, 2, 3, 4, 5, 6, 23, 43, 53]
3. 삽입 정렬 (Insertion Sort) : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬하는 방식
- 시간 복잡도
- 평균 : O(n^2)
- 최악 : O(n^2)
- 장점
1) 알고리즘이 단순하다.
2) 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다 (제자리 정렬)
3) 중복된 값을 입력 순서와 동일하게 정렬하는 안정 정렬이다.
4) 대부분의 원소가 이미 정렬되어 있는 경우, 시간 복잡도 O(n)으로 효율적일 수 있다.
- 단점
1) 시간복잡도가 최악, 평균 모두 O(n^2)으로 비효율적이다.
2) 배열의 길이가 길어질수록 비효율적이다.
- 코드
list = [2,1,23,43,53,3,5,4,6]
for i in range(1, len(list)):
key = list[i]
j = i - 1
while key < list[j] and j >= 0:
list[j + 1] = list[j]
j -= 1
list[j + 1] = key
print(list) # [1, 2, 3, 4, 5, 6, 23, 43, 53]
4. 퀵 정렬 (Quick Sort) : 분할 정복 알고리즘을 통해 구현하였으며, 피벗(기준 값)을 설정하여 피벗 기준으로 양쪽으로 나눠서 정렬하는 방식
- 작동 방식 :
1) 피벗을 설정한다.
2) 배열의 시작 인덱스를 left, 마지막 인덱스를 right라고 할 때,
- pl은 left부터 시작하여 피벗보다 크거나 같은 값이 있을 때까지 오른쪽으로 이동한다.
(단, pl이 right보다 작거나 같을때 까지만 이동)
- pr은 마지막부터 시작하여 피벗보다 작거나 같은 값이 있을 때까지 왼쪽으로 이동한다.
(단, pr이 left보다 크거나 같을때 까지만 이동)
3) pl과 pr이 둘 다 이동을 멈추고 pl<=pr 이면 arr[pl] 과 arr[pr]을 서로 교환(swap)한다.
4) pl과 pr이 교차할 때까지, 즉 pl > pr일 때까지 2, 3번을 반복한다.
5) pl과 pr이 교차하면 시작 인덱스를 left, 끝 인덱스를 pr로 하는 그룹과
시작 인덱스 pl, 끝 인덱스를 right로 하는 그룹으로 나눠서 위 과정을 반복한다.
6) 더 이상 작은 그룹으로 나눌 수 없으면 종료한다.
- 시간 복잡도
- 평균 : O(nlogn)
- 최악 : O(n^2) (피벗 값이 계속 한쪽으로 치우치게 되어 파티션을 나누지 못했을 경우)
- 장점
1) 최악의 경우를 제외하면 다른 알고리즘과 비교했을 때 속도가 가장 빠르다.
2) 추가 메모리 공간이 필요 없다.
- 단점
1) 정렬된 리스트에 대해서는 비효율적인 수행시간이 걸린다.
2) 불안정 정렬이다.
- 코드
list = [2,1,23,43,53,3,5,4,6]
def quick_sort(temp_list):
if len(temp_list) < 2:
return temp_list
pivot = len(temp_list) // 2
front_list, pivot_list, back_list = [], [], []
for elem in temp_list:
if elem < temp_list[pivot]:
front_list.append(elem)
elif elem > temp_list[pivot]:
back_list.append(elem)
else:
pivot_list.append(elem)
return quick_sort(front_list) + quick_sort(pivot_list) + quick_sort(back_list)
print(quick_sort(list)) # [1, 2, 3, 4, 5, 6, 23, 43, 53]
5. 병합 정렬 (Merge Sort) : 합병 정렬이라고도 부름. 분할 정복 알고리즘을 통해 구현하였으며, 요소를 쪼갠 후 다시 합병시키면서 정렬해나가는 방식
- 시간 복잡도
- 평균 : O(nlogn)
- 최악 : O(nlogn)
- 장점
1) 순차적인 비교로 정렬을 하므로 LinkedList의 정렬이 필요할 때 사용하면 효율적이다.
2) 데이터 분포에 영향을 덜 받는다.
3) 중복된 값을 입력 순서와 동일하게 정렬하는 안정 정렬이다.
- 단점
1) 추가적인 메모리(임시 배열)를 사용해야 한다.
2) 크기가 큰 경우 이동 횟수가 많아지므로 시간 낭비 발생
- 코드
list = [2,1,23,43,53,3,5,4,6]
def merge(left, right):
len_left, len_right = len(left), len(right)
i_left, i_right = 0, 0
l = []
while i_left < len_left and i_right < len_right:
if left[i_left] < right[i_right]:
l.append(left[i_left])
i_left += 1
else:
l.append(right[i_right])
i_right += 1
while i_left < len_left:
l.append(left[i_left])
i_left += 1
while i_right < len_right:
l.append(right[i_right])
i_right += 1
return l
def merge_sort(temp_list):
if len(temp_list) < 2:
return temp_list
mid = len(temp_list) // 2
left = merge_sort(temp_list[0:mid])
right = merge_sort(temp_list[mid:])
r = merge(left, right)
return r
print(merge_sort(list)) # [1, 2, 3, 4, 5, 6, 23, 43, 53]
6. 힙 정렬 (Heap Sort) : 최대 힙 또는 최소 힙을 구성하여 정렬한 방식
최대 힙을 만들어주고 Extract(Heap의 최대 요소를 추출하는 작업, 추출 후 Heap 마지막 요소를 루트 노드에 배치 그 다음에 max_heapify 수행)를 반복하면 오름차순으로 정리가 가능하다. (반대로 최소 힙으로 하면 내림차순)
- 시간 복잡도
- 평균 : O(nlogn)
- 최악 : O(nlogn)
- 장점
1) 가장 큰 값을 구하거나 가장 작은 값을 구할 때 좋다.
- 단점
1) 다른 O(nlogn) 방식보다 오래 걸린다.
2) 불안정 정렬이다.
- 코드
list = [2,1,23,43,53,3,5,4,6]
def heap(temp_list):
def heapify(i, l):
largest = i
left, right = i * 2 + 1, i * 2 + 2
if left < l and temp_list[largest] < temp_list[left]:
largest = left
if right < l and temp_list[largest] < temp_list[right]:
largest = right
if largest != i:
temp_list[i], temp_list[largest] = temp_list[largest], temp_list[i]
heapify(largest, l)
n = len(temp_list)
for idx in range(n // 2 - 1, -1, -1):
heapify(idx, n)
for i in range(n - 1, 0, -1):
temp_list[0], temp_list[i] = temp_list[i], temp_list[0]
heapify(0, i)
return temp_list
print(heap(list)) # [1, 2, 3, 4, 5, 6, 23, 43, 53]'개발에 도움이 되는 > 자료구조 & 알고리즘' 카테고리의 다른 글
| Float(부동 소수점 자료형)의 숫자 표현법 (0) | 2022.01.08 |
|---|---|
| 힙(Heap) (0) | 2022.01.02 |
| 이진 탐색 트리(Binary Search Tree, BST) (0) | 2022.01.02 |
| 이진 트리(Binary Tree) (0) | 2022.01.02 |
| 트리(Tree) (0) | 2022.01.01 |
