정렬 알고리즘 정리
1. 버블 정렬(Bubble sort)
가장 쉬운 정렬 알고리즘이지만 시간복잡도가 별로 좋지 않아서 많이 사용되지 않는다.
- 시간복잡도 : O(n^2)
- 공간복잡도 : 하나의 배열만 사용하여 정렬하기 때문에 O(n)
def bubbleSort(list):
# 총 배열 원소의 개수 n 개면 n-1->n-2->0 만큼 반복한다.
for loop_count in range(len(list)-1, 0, -1):
for index in range(loop_count):
if list[index] > list[index+1]:
tmp = list[index]
list[index] = list[index+1]
list[index+1] = tmp
return list
버블 정렬은 정렬할때마다 큰 값들이 점점 뒤로(수면 위로 올라오는 것처럼) 정렬 되기 때문에 버블정렬이라고 한다.
테스트 결과, Execution Time 이 7.72012 정도 나왔다.
2. 선택 정렬(Selection sort)
버블 정렬과 유사하다. 버블 정렬은 순회마다 한 인덱스의 값과 다음 인덱스의 값을 계속 비교하면서 값을 바꾸지만, 선택 정렬은 순회마다 가장 작은 수를 찾아서 배열의 마지막 위치와 교환한다.
- 시간복잡도 : O(n^2)
- 공간 복잡도 : 하나의 배열만 사용하기 때문에 O(n)
그림을 보면 알겠지만, 버블 정렬과는 달리 선택 정렬은 작은 값부터 정렬된다. 선택 정렬은 가장 작은 애를 선택한다고 기억하면 좋을 것 같다.
def SelectionSort(list):
#offset은 0 -> 1 -> 2 -> ... -> n-1 까지 증가합니다. 비교할 기준을 offset이라 생각하면 된다.
for offset in range(0, len(list)-1):
# 현재 기준
offset_minValue = offset
# 기준 다음부터 비교하면 된다.
for num in range(offset+1, len(list)):
# 만약 기준보다 작은 값이 나타났다 -> 기준점을 바꾼다
if list[num] < list[offset_minValue]:
offset_minValue = num
# 비교가 끝나면 값을 바꿔준다.
tmp = list[offset_minValue]
list[offset_minValue] = list[offset]
list[offset] = tmp
return list
테스트 결과, Execution time이 약 3.1412 로 버블 정렬의 반 이상 줄어든 것이 확인되었다.
3. 삽입 정렬(Insertion Sort)
삽입 정렬은 index가 1부터 n까지 증가하며, 이 인덱스를 기준으로 현재 위치보다 아래쪽을 순회하며 현재 위치의 값을(index에 있던 값을) 알맞은 위치에 넣어주는 정렬 알고리즘이다. 마치 값을 들어서 올바른 위치에 삽입하는 모양과 같다.
- 시간 복잡도 : 이미 정렬이 되어 있다면 O(n)의 시간 복잡도를 가진다. 정렬이 되어 있는 경우라면 한 번 순회하며 체크만 하기 때문이다. Big-O 시간복잡도는 O(n^2)이다.
def InsertionSort(list):
#1부터 시작하는 이유는 0이면 이전에 비교할 값이 없기 때문
for index in range(1, len(list)):
currentValue = list[index]
position = index
# 이전 값이 더 크면 큰 값을 위로 올려보내 준다
while position > 0 and list[position-1] > currentValue:
list[position] = list[position-1]
position -= 1
list[position] = currentValue
return list
테스트 결과 약 4.19의 execution time을 가지낟.
4. 병합 정렬(Merge sort)
병합 정렬은 정렬할 리스트를 반으로 쪼개 나가며 우측 리스트를 계속 분할해 나간 후 각 리스트 내에서 정렬 후 병합하는 과정을 통해 정렬하는 알고리즘이다. 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
- 시간 복잡도 : 최소 O(nlogn)을 보장한다. 즉 최악의 경우에도 O(nlogn)을 보장한다는 소리이다.
def MergeSort(list):
# 리스트의 원소의 개수가 하나이면 더 이상 나눌 수 없다.
if len(list) <= 1:
return list
# 리스트의 가운데 인덱스 값이 될 것이다.
mid = len(list) // 2
left_list = list[:mid]
right_list = list[mid:]
# 왼쪽 리스트와 오른쪽 리스트를 계속해서 병합 정렬 할 것이다.
L = MergeSort(left_list)
R = MergeSort(right_list)
# i, j는 각각 L, R 리스트의 인덱스입니다.
i = j = 0
result = []
# 왼쪽 리스트와 오른쪽 리스트에 있는 값들을 비교하며 작은 것부터 result에 넣습니다.
while i < len(L) and j < len(R):
if L[i] < R[j]:
result.append(R[j])
i += 1
else:
result.append(R[j])
j += 1
# L, R 리스트에 남아있는 것이 있으면 리스트에 추가해 줄겁니다.
# 이때 L, R 중 한 리스트에는 무조건 남아있는 원소가 없을 것입니다.
result += L[i:]
result += R[j:]
return result
Execution time은 약 0.065 정도로 굉장히 빠르다.
5. 퀵 정렬(Quick sort)
퀵 정렬은 real-world 데이터를 대상으로 빠르다고 알려져 있어서 가장 많이 사용되는 알고리즘이다. 퀵 정렬은 pivot을 설정하여 pivot을 기준으로 좌측과 우측으로 pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 재배치를 하고 계속해서 분할하여 정렬하는 알고리즘이다.
- 시간복잡도 : 최악의 경우 O(n^2)의 비교를 수행하지만 일반적으로 O(nlogn)의 시간복잡도를 가진다. pivot을 기준으로 분할했을 때 값들이 한 편으로 크게 치우치게 되면 퀵 정렬의 성능은 떨어집니다.
def partition(list, start, end):
pivot = list[start]
left = start + 1
right = end
done = False
while not done:
# left > right이 될 때 멈추고 left에 있는 값이 pivot보다 큰 값이 있으면 멈춥니다.
while left <= right and list[left] <= pivot:
left += 1
# right < left이 될 때 멈추고 right에 있는 값이 pivot보다 작은 값이 있으면 멈춥니다.
while right >= left and list[right] >= pivot:
right -= 1
# 모든 값이 pivot 기준으로 잘 분리 된 것이므로 종료합니다.
if right < left:
done = True
else:
# pivot 기준으로 pivot 보다 큰 left, 작은 right를 서로 바꿔줍니다.
tmp = list[left]
list[left] = list[right]
list[right] = tmp
# left > right 일 때 right에 있는 값을 pivot과 바꿉니다.
tmp = list[start]
list[start] = list[right]
list[right] = tmp
# 새로운 pivot 장소를 리턴한다.
return right
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
6. 힙 정렬(Heap sort)
힙 정렬은 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성한다.
- 시간복잡도 : 최악, 최선, 평균 모두 O(nlogn)의 시간복잡도를 가진다.
- 공간복잡도 : O(n)
