[Algorithm] Python으로 구현한 sort
Python은 list 자료형에 대해 sort 메소드를 기본적으로 제공하지만 필요에 따라 직접 구현할 필요도 있고, 또 Python 언어와 알고리즘 이해를 위해 작성한다.
- 오름차순 정렬
list_data.sort()
- 내림차순 정렬
list_data.sort(reverse=True)
Sort Basic
- 선택 정렬 (Selection Sort)
- 삽입 정렬 (Insertion Sort)
- 거품 정렬 (Bubble Sort)
- 퀵 정렬 (Quick Sort)
선택 정렬 (Selection Sort)
selection sort는 정렬하고자 하는 array 원소들 중 가장 작은 값을 찾아 맨 앞의 값과 교체하고, 이어서 맨 앞의 값을 제외한 나머지 array 원소들에 앞 과정을 반복하여 정렬하는 알고리즘이다.
아래와 같은 순서로 정렬이 진행된다.
| – | 7 3 4 2 5 6 1 |
|---|---|
| – | 1 3 4 2 5 6 7 |
|---|---|
| – | 1 2 4 3 5 6 7 |
|---|---|
| – | 1 2 3 4 5 6 7 |
|---|---|
전체 원소에 대해 그 뒤 원소들과 비교를 수행하므로 시간복잡도는 $O(n^2)$이다.
알고리즘이 단순하여 메모리가 제한적인 경우 사용했을 때 이점이 있다.
selection_sort
def selection_sort(arr):
for i in range(len(arr)):
sel = i
for j in range(i+1,len(arr)):
if arr[sel]>arr[j]: sel = j
temp = arr[sel]
arr[sel] = arr[i]
arr[i] = temp
return arr
삽입 정렬 (Insertion Sort)
insertion sort는 주어진 array의 데이터를 index 순서대로 가져오면서, 해당 원소를 가져다 놓을 때에 크기 비교를 하여 적절한 위치에 배치시키는 알고리즘이다.
$n$개의 데이터가 있을 때 최악의 경우 아래와 같은 횟수의 비교를 수행하게 되므로
$$\sum_{n=1}^{n-1} 1+2+3+4+…+(n-1) = \frac{n(n-1)}{2}$$
시간 복잡도는 $O(n^2)$이다.
insertion_sort
def insertion_sort(arr):
for i in range(len(arr)):
temp, j = arr[i], i - 1
for j in range(j,-1,-1):
if arr[j]<temp: break
arr[j+1] = arr[j]
arr[j+1] = temp
return arr
거품 정렬 (Bubble Sort)
거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 이렇게 이름 지어진 거품 정렬은 인접한 두 원소를 검사하여 정렬한다.
시간 복잡도는 $O(n^2)$이다.
bubble_sort
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j]>arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
return arr
퀵 정렬 (Quick Sort)
시간 복잡도는 최악의 경우 $O(n^2)$일 수도 있지만 대부분 $O(n {\log n})$이다.
quick_sort
def quick_sort(arr,left=-1,right=-1):
left_temp = left if left!=-1 else 0
right_temp = right if right!=-1 else len(arr) - 1
pivot = arr[left]
while left<right:
while arr[right]>=pivot and left<right: right -= 1
if left!=right: arr[left] = arr[right]
while arr[left]<=pivot and left<right: left += 1
if left!=right:
arr[right] = arr[left]
right -= 1
arr[left] = pivot
pivot = left
left = left_temp
right = right_temp
if (left<pivot): quick_sort(arr,left,pivot-1)
if (right>pivot): quick_sort(arr,pivot+1,right)
return arr
Python Sample
위에서 설명한 sort 함수들을 모두 테스트 해보는 프로그램. python의 function은 list 자료형 인수에 대해 무조건 call by reference 방식으로 데이터를 변형하므로 main에서 data_original 을 이용해 계속해서 초기화해 줄 필요가 있다.
def selection_sort(arr):
for i in range(len(arr)):
sel = i
for j in range(i+1,len(arr)):
if arr[sel]>arr[j]: sel = j
temp = arr[sel]
arr[sel] = arr[i]
arr[i] = temp
return arr
def insertion_sort(arr):
for i in range(len(arr)):
temp, j = arr[i], i - 1
for j in range(j,-1,-1):
if arr[j]<temp: break
arr[j+1] = arr[j]
arr[j+1] = temp
return arr
def bubble_sort(arr):
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j]>arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
return arr
def quick_sort(arr,left=-1,right=-1):
left_temp = left if left!=-1 else 0
right_temp = right if right!=-1 else len(arr) - 1
pivot = arr[left]
while left<right:
while arr[right]>=pivot and left<right: right -= 1
if left!=right: arr[left] = arr[right]
while arr[left]<=pivot and left<right: left += 1
if left!=right:
arr[right] = arr[left]
right -= 1
arr[left] = pivot
pivot = left
left = left_temp
right = right_temp
if (left<pivot): quick_sort(arr,left,pivot-1)
if (right>pivot): quick_sort(arr,pivot+1,right)
return arr
def main():
import random
data_original = [random.randint(1,100) for _ in range(random.randint(4,10))]
print("original data")
print(data_original)
print("\nselection sort test")
data = data_original
print(selection_sort(data))
print("\ninsertion sort test")
data = data_original
print(insertion_sort(data))
print("\nbubble sort test")
data = data_original
print(bubble_sort(data))
print("\nquick sort test")
data = data_original
print(quick_sort(data))
if __name__ == '__main__':
main()
