Selection Sort(선택 정렬)
- 선택 정렬은 리스트 중에서 가장 작은 값(또는 가장 큰 값)을 선택하여 리스트의 앞(또는 뒤)쪽으로 Swap하는 방식이다.
# -*- coding: utf-8 -*-
import unittest
class Exam08(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_selection_sort(self):
"""선택 정렬을 이용한 정렬 방법"""
data = [2, 11, 3, 91, 7, 50, 33]
length = len(data)
for i in range(length):
min_idx = i
for j in range(i+1, length):
# 더 작은 최솟값이 있다면, 교환(swap)한다.
if data[min_idx] > data[j]:
tmp = data[min_idx]
data[min_idx] = data[j]
data[j] = tmp
print("{} 회차: {}".format(i+1, data))
self.assertEqual([2, 3, 7, 11, 33, 50, 91], data)
if __name__ == "__main__":
unittest.main()import unittest
def selectionSort(input):
for i in range(len(input) - 1):
# assume the min is the first element
idx_min = i
j = i + 1
# test against elements after i to find the smallest
while j < len(input):
if(input[j] < input[idx_min]):
# found new minimum; remember its index
idx_min = j
j = j + 1
if idx_min is not i:
# swap
input[idx_min], input[i] = input[i], input[idx_min]
return input
class unit_test(unittest.TestCase):
def test(self):
self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([4, 6, 1, 3, 5, 2]))
self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([6, 4, 3, 1, 2, 5]))
self.assertEqual([1, 2, 3, 4, 5, 6], selectionSort([6, 5, 4, 3, 2, 1]))Insertion Sort(삽입 정렬)
-
삽입 정렬(Insertion Sort)은 첫번째 원소부터 하나하나 차례대로 비교해가면서, 자신보다 큰 값이 나타나면 그 큰 값 앞에 놓는 방식이다.
-
일반적인 삽입정렬
# -*- coding: utf-8 -*-
import unittest
class Exam09(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_insertion_sort(self):
data = [2, 4, 5, 1, 3]
n = len(data)
for i in range(1, n):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j] # 오른쪽으로 밀어준다. (공간 확보)
j -= 1
data[j + 1] = key
# print(key, data)
self.assertEqual([1, 2, 3, 4, 5], data)
if __name__ == "__main__":
unittest.main()
출처: https://memostack.tistory.com/26 [MemoStack:티스토리]- 파이썬을 활용한 삽입 정렬
# -*- coding: utf-8 -*-
import unittest
class Exam09(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_insertion_sort_with_python(self):
data = [2, 4, 5, 1, 3]
sorted_data = list()
while data:
value = data.pop(0)
n = len(sorted_data) # value 보다 큰 원소가 없는 경우 맨 뒤로 배치 (default)
insert_idx = n
# value 보다 큰 원소를 찾는다.
for i in range(n):
if value < sorted_data[i]:
insert_idx = i
break
sorted_data.insert(insert_idx, value)
# print(value, sorted_data)
self.assertEqual([1, 2, 3, 4, 5], sorted_data)
if __name__ == "__main__":
unittest.main()삽입정렬의 시간복잡도는 O(N^2)로 상당히 오래 걸리는 편이다.
Bubble Sort(거품 정렬)
- 버블 정렬은 바로 옆의 원소와 크기 비교를 하여 위치를 바꾸는 방법이다. 바로 옆의 원소와 크기 비교를 하고 Swap을 하면 되기 때문에 구현하기 쉬운 알고리즘이다.
# -*- coding: utf-8 -*-
import unittest
class Exam12(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_bubble_sort(self):
data = [2, 6, 3, 4, 8, 9, 1, 10]
n = len(data)
for _ in range(n-1):
for i in range(n-1):
if data[i] > data[i+1]:
data[i], data[i+1] = data[i+1], data[i]
self.assertEqual([1, 2, 3, 4, 6, 8, 9, 10], data)
if __name__ == "__main__":
unittest.main()시간복잡도는 O(N^2)로 상당히 오래 걸리는 편이다.
Merge Sort(병합 정렬)
-
병합 정렬은 그룹을 반으로 나눈다음 합칠때 크기에 맞게 고친다. 이 과정을 재귀적으로 수행한다.
-
일반적인 병합 정렬
# -*- coding: utf-8 -*-
import unittest
class Exam10(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_merge_sort(self):
"""일반적인 병합 정렬"""
def _merge_sort(group):
# 재귀 종료 조건: 그룹이 없을때
n = len(group)
if n <= 1:
return
# 반으로 그룹을 나눈다.
mid_idx = n // 2
group1 = group[:mid_idx]
group2 = group[mid_idx:]
# print(group, group1, group2)
# 재귀적으로 병합 정렬을 수행한다.
_merge_sort(group1)
_merge_sort(group2)
# 정렬한다.
idx, idx1, idx2 = 0, 0, 0 # 전체 그룹 인덱스, 그룹1 인덱, 그룹2 인덱스
while idx1 < len(group1) and idx2 < len(group2):
if group1[idx1] < group2[idx2]:
group[idx] = group1[idx1]
idx1 += 1
else:
group[idx] = group2[idx2]
idx2 += 1
idx += 1
# 그룹에 남아있는 원소를 넣는다.
while idx1 < len(group1):
group[idx] = group1[idx1]
idx1 += 1
idx += 1
while idx2 < len(group2):
group[idx] = group2[idx2]
idx2 += 1
idx += 1
data = [38, 27, 43, 3, 9, 82, 10]
_merge_sort(data)
self.assertEqual([3, 9, 10, 27, 38, 43, 82], data)
if __name__ == "__main__":
unittest.main()- 파이썬을 이용한 병합 정렬
# -*- coding: utf-8 -*-
import unittest
class Exam10(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_merge_sort_with_python(self):
"""파이썬을 이용한 병합 정렬"""
def _merge_sort(group):
# 종료 조건 설정
n = len(group)
if n <= 1:
return group
# 그룹 나누기
mid_idx = n // 2
group1 = _merge_sort(group[:mid_idx])
group2 = _merge_sort(group[mid_idx:])
# 정렬
result = list()
while group1 and group2:
result.append(group1.pop(0) if group1[0] < group2[0] else group2.pop(0))
result.extend(group1)
result.extend(group2)
# print(result)
return result
data = [38, 27, 43, 3, 9, 82, 10]
sorted_data = _merge_sort(data)
self.assertEqual([3, 9, 10, 27, 38, 43, 82], sorted_data)
if __name__ == "__main__":
unittest.main()반으로 나누어서 문제를 푸는 방식을 분할 정복(Divide and Conquer)이라고 한다.
분할 정복은 시간복잡도가 O(N logN)이다. 선택 정렬이나 삽입 정렬의 시간복잡도(ON^2)보다 낮아, 비교적 빠르다.
즉, 개수가 많아질수록 병합정렬(Merge Sort)을 이용하는것이 효율적이다.
Quick Sort(퀵 정렬)
-
퀵 정렬(Quick Sort)은 병합 정렬(Merge Sort)과 비슷하게 재귀 호출을 하여 정렬을 한다. 다만 퀵 정렬은 기준점과 미리 비교를 한다는 차이점이 있다.
-
일반적인 퀵 정렬
# -*- coding: utf-8 -*-
import unittest
class Exam11(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_quick_sort(self):
"""일반적인 퀵 정렬"""
def _quick_sort(data, start, end):
# 종료 조건: 정렬을 할 원소가 1개 이하인 경우
if start >= end:
return
# 피봇 설정 (편의상 맨 마지막 원소를 피봇으로 지정)
pivot = data[end]
left = start
# 왼쪽은 피봇보다 작은 수가 위치한다.
# 오른쪽은 피봇보다 큰 수가 위치한다.
for right in range(start, end):
if data[right] <= pivot:
# data[right], data[left] = data[left], data[right] 와 동일
tmp = data[right]
data[right] = data[left]
data[left] = tmp
left += 1
# 맨 마지막에 위치한 피봇과 위치를 바꿔준다.
# [피봇보다 작은 수들] + [피봇] + [피봇보다 큰 수]
data[end], data[left] = data[left], data[end]
_quick_sort(data, start, left - 1)
_quick_sort(data, left + 1, end)
data = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
_quick_sort(data, 0, len(data) - 1)
self.assertEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], data)
if __name__ == "__main__":
unittest.main()- 파이썬을 이용한 퀵 정렬
# -*- coding: utf-8 -*-
import unittest
class Exam11(unittest.TestCase):
@classmethod
def setUp(cls):
pass
def test_quick_sort_with_python(self):
def _quick_sort(data):
# 종료 조건
n = len(data)
if n <= 1:
return data
# 피봇 값은 어떤값으로 하든 상관없음. 편의상 맨 마지막을 피봇으로 지정
pivot = data[-1]
group1 = list() # 피봇보다 작은 값
group2 = list() # 피봇보다 큰 값
for num in data[:-1]:
if num < pivot:
group1.append(num)
else:
group2.append(num)
return _quick_sort(group1) + [pivot] + _quick_sort(group2)
data = [4, 2, 6, 5, 3, 9]
self.assertEqual([2, 3, 4, 5, 6, 9], _quick_sort(data))
if __name__ == "__main__":
unittest.main()시간 복잡도는 병합 정렬과 똑같이 분할 정복을 수행하려 들기 때문에 O(N * logN)이다.
다만, 대부분은 O(NlogN)이지만 최악의 경우 O(N^2)까지 갈 수 있다.
- 출처: https://memostack.tistory.com/25 [MemoStack:티스토리]
- 출처 : https://github.com/minsuk-heo/problemsolving/tree/master/sort
개발자 지망생