정렬 알고리즘은 다음과 같이 나눠 볼 수 있음.
-
단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬
-
복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 병합 정렬
버블 정렬(Bubble Sort)
-
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘.
-
인접한 2개의 원소를 비교해 크기가 순서대로 되어 있지 않으면 서로 교환한다.
-
선택 정렬과 기본 개념이 유사하다.
def bubblesort(data):
for index in range(len(data)-1):
swap = False
for index2 in range(len(data)-1-index):
if data[index2] > data[index2+1]:
data[index2], data[index2+1] = data[index2+1], data[index2]
swap = True
if swap == False:
break
return data
로직
-
1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, .... 이런 식으로 마지막 -1 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.
-
1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
시간 복잡도
(n-1) + (n-2) + (n-3) + ... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다.
버블 정렬은 정렬이 되어있건, 안되어있건 2개의 원소를 비교하기 때문에 최악의 경우, 최선의 경우, 평균의 경우 모두 시간 복잡도가 O(N^2)으로 동일.
장점
- 구현이 간단하고 소스코드가 직관적이다.
- 이미 정렬된 데이터를 정렬할 때, 가장 빠르다.
- 정렬하고자 하는 배열 안에서 정렬하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
- 안정 정렬이다.
단점
- 시간 복잡도가 최악, 최선, 평균 모두 O(N^2)이므로 비효율적.
- 다른 정렬에 비해 정렬 속도가 느리다.
- 교환 횟수가 많다.
- 역순배열을 정렬할 때, 가장 느리다.
선택 정렬(Selection Sort)
-
해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘.
-
현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라서 최소 선택 정렬(오름차순 정렬)과 최대 선택 정렬(내림차순 정렬)로 나뉜다.
def selectionSort(data):
for stand in range(len(data)-1):
lowest = stand
for index in range(stand + 1, len(data)):
if data[lowest] > data[index]:
lowest = index
data[lowest], data[stand] = data[stand], data[lowest]
로직
-
주어진 배열에서 첫번째 인덱스를 기준으로 잡는다. 기준은 처음부터 시작한다.
-
주어진 배열에서 기준 이후의 값 중 최소값을 찾는다.
-
최소값과 기 기준의 값을 교체한다.
-
기준 이후의 나머지 배열을 같은 방법으로 교체한다.
시간 복잡도
쉽게 말해서 기준이 되는 수와 나머지 수를 비교해서 가장 작은 수를 앞으로 계속 보내는 정렬.
간단하지만, 매우 비효율적이다.
1단계 => n개의 원소를 비교
2단계 => n-1개의 원소 비교
3단계 => n-2개의 원소 비교
...
를 하여 비교 횟수는 n(n-1)/2가 된다. 즉 시간복잡도는 O(n^2)이 된다.
최악의 경우, 최선의 경우, 평균적인 경우 모두 시간 복잡도는 O(n^2)이 된다.
장점
-
알고리즘이 단순하다.
-
정렬을 위한 비교는 여러번 수행되지만, 실제로 교환 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적인 면이 있다.
-
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
단점
-
시간 복잡도가 O(n^2)이므로 비효율적이다.
-
불안정 정렬이다.
삽입 정렬(Insertion Sort)
-
손 안의 카드를 정렬하는 방법과 유사하다.
-
새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입한다.
-
2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
-
최선의 경우, O(n)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될만큼 좋은 정렬 알고리즘이다.
def insertionSort(data):
for index in range(len(data)-1):
for index2 in range(index+1,0, -1):
if data[index2] < data[index2-1] :
data[index2], data[index2-1] = data[index2-1], data[index2]
else:
break
return data
로직
-
정렬은 2번째 위치(index)의 값이 index2를 가리킨다.
-
index2와 이전에 있는 원소들과 비교하여 자리를 바꾸며 삽입해 나간다.
-
1번으로 돌아가서 다음 위치(index)의 값이 index2를 가리키면 반복한다.
시간 복잡도
-
최악의 경우(역으로 정렬되어 있을 경우), 선택 정렬과 마찬가지로 (n-1)+(n-2)+ ... +2+1 => n(n-1)/2 즉, O(N^2)이다.
-
하지만, 모두 정렬이 되어 있는 경우, 한번씩만 비교하므로 O(N)의 시간 복잡도를 가지게 된다. 또한, 이미 정렬되어 있는배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.
-
최선의 경우 : O(N)
-
평균과 최악의 경우 : O(N^2)
장점
- 알고리즘이 단순하다.
- 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.
- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
- 선택 정렬이나 버블 정렬에 비하여 상대적으로 빠르다.
단점
- 비교적 많은 수들의 이동을 포함한다.
- 비교할 수가 많고 크기가 클 경우에 적합하지 않다.(배열의 길이가 길어질수록 비효율적)
- 평균과 최악의 시간 복잡도가 O(N^2)이므로 비효율적이다.
퀵 정렬(QuickSort)
-
퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬한다.
- 분할 정복(Divide and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.
-
불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
-
또한, 병합 정렬과 달리 퀵 정렬은 배열을 비균등하게 분할한다.
-
pivot(기준점을 정해) pivot보다 작은수는 왼쪽 큰수는 오른쪽에 배치하여, 재귀 호출을 통하여 리스트의 길이가 1까지 반복해서 호출 한 후 합치는 정렬 방법.
def qsort(data):
if len(data) <= 1:
return data
pivot = data[0]
left, right = list(), list()
for index in range(1,len(data)):
if pivot > data[index]:
left.append(data[index])
else:
right.append(data[index])
return qsort(left) + [pivot] + qsort(right)
로직
-
배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소는 피봇(pivot)이라고 한다.
-
피봇 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피봇 뒤는 피봇보다 값이 큰 모든 원소들이 오도록 피봇을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나눈 것을 분할(Divide)이라고 한다.분할을 마친 뒤에 피봇은 더 이상 움직이지 않는다.
-
분학 된 두개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
-
분할(Divide) : 주어진 배열을 피봇을 기준으로 비균등하게 2개의 부분 배열로 분할한다. (피봇을 중심으로 왼쪽 : 피봇보다 작은 요소들, 오른쪽 : 피봇보다 큰 요소들)
-
정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
시간 복잡도
- 병합 정렬과 유사, 시간복잡도는 O(nlogn)
- 최악의 경우: 피봇이 가장 크거나, 가장 작으면 모드 데이터를 비교하는 상황이 나오기 때문에 O(n^2)의 복잡도를 가질 수 있음
장점
-
불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(N logN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
-
정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.
단점
-
불안정 정렬이다.
-
정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다.
병합 정렬(MergeSort)
-
빠른 정렬로 분류되며, 퀵 정렬과 함께 많이 언급되는 정렬 방식이다.
-
퀵 정렬과는 반대로 안정 정렬에 속한다.
-
병합 정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때, 사용하면 효율적이다. LinkedList를 퀵 정렬에 사용해 정렬하면 성능이 좋지 않다. 이유는 퀵 정렬은 순차 접근이 아닌 임의 접근이기 때문이다. LinkedList는 삽입과 삭제 연산에서는 유용하지만, 접근 연산에서는 비효율적이다.
def mergeSort(data):
if len(data) <= 1:
return data
medium = len(data) // 2
left = mergeSort(data[:medium])
right = mergeSort(data[medium:])
return merge(left, right)
def merge(left, right):
merged = list()
left_point, right_point = 0, 0
#case1 : left/right 아직 남아있을 때
while len(left) > left_point and len(right) > right_point:
if left[left_point] > right[right_point]:
merged.append(right[right_point])
right_point += 1
else:
merged.append(left[left_point])
left_point += 1
#case2 : left만 남아있을 때
while len(left) > left_point:
merged.append(left[left_point])
left_point += 1
#case3 : right만 남아있을 때
while len(right) > right_point:
merged.append(right[right_point])
right_point += 1
return merged
시간 복잡도
평균, 최선, 최악 모두 O(nlogn)의 복잡도를 가진다.
장점
-
데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무어싱든 간에 정렬되는 시간은 동일하다.
-
크기가 큰 레코드를 정렬한 경우, LinkedList를 사용한다면 병학 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.
-
안정 정렬에 속한다
단점
-
레코드를 배열로 구성한다면, 임시 배열이 필요하다. 메모리 낭비를 초래한다. 제자리 정렬이 아니다.
-
레코드의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
