초보몽키의 개발공부로그
강의노트 16.[정렬] - bubble sort(버블정렬), insertion sort(삽입정렬), selection sort(선택정렬)
16 Apr 2017 |패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
O(n^2)의 성능을 가진 버블정렬, 삽입정렬, 선택정렬에 대해서 알아본다.
bubble sort (버블정렬)
- 인접한 두 원소를 검사하여 정렬하는 방법
- 시간복잡도가 (Big O) O(n^2)로 상당히 느리다. 하지만 코드가 단순하기 때문에 자주 사용된다.
- 최악의 경우 100개의 데이터가 있을 때 연산을 10,000번 할 수 있다.
- 참고글 - 정렬(Sorting) 알고리즘 O(n^2)
- 참고글 - 정렬알고리즘
- 참고글 - 버블정렬 쉽게 정리하기
구현 1 (버블정렬)
def BubbleSort(li):
list_length = len(li)
#length가 4라면
#바깥 루프는 3번 돌아야 하므로
#range()는 0, 1, 2까지 즉 range(3)이 되야 하므로
#range(list_length-1)이 되어야 한다.
for i in range(list_length-1):
#안쪽 루프는 1번당 3-> 2-> 1
#즉 range(4 - 0 - 1) ->
#range(4 - 1 - 1) ->
#range(4 - 2 - 1)
#range(list_leng - i - 1)
for j in range(list_length-i-1):
#만약 앞에 있는 값이 크다면 두 개를 교환
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
if __name__ == "__main__":
li = [2, 3, 1, 4]
BubbleSort(li)
print(li)
def bubble_sort(li):
length = len(li) - 1
for i in range(length):
for j in range(length-i):
if li[j] > li[j+1]:
li[j], li[j+1] = li[j+1], li[j]
if __name__ == "__main__":
li = [10,2,3,4,1,7,0]
bubble_sort(li)
print(li)
구현 2 (버블정렬)
- 구현 1 보다 불필요한 반복이 추가된다. (이미 정렬된 부분에 대한 비교)
import unittest
def bubblesort(alist):
for i in range(len(alist)-1):
for j in range(len(alist)-1):
if alist[j] > alist[j+1]:
alist[j], alist[j+1] = alist[j+1], alist[j]
return alist
class unit_test(unittest.TestCase):
def test(self):
self.assertEqual([1,2,3,4,5,6], bubblesort([4,6,1,3,5,2]))
if __name__=='__main__':
unittest.main()
selection sort(선택정렬)
- 최소값을 선택하는 과정을 반복해서 선택 정렬이라 부른다고 한다.
- 위키백과
- 주어진 리스트 중에 최솟값을 찾는다
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass))
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
구현 1 (선택정렬)
#맨 왼쪽부터 하나씩 최소값을 선택(selection)해 채운다
def selection_sort(li):
for i in range(len(li)-1):
min_idx = i
for j in range(i+1, len(li)):
if li[min_idx] > li[j]:
min_idx = j
if min_idx != i:
li[i], li[min_idx] = li[min_idx], li[i]
return li
if __name__ == "__main__":
li = [4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]
SelectionSort(li)
print(li)
구현 2 (선택정렬)
- 구현 1의 방식이 더 일반적이다.
def selection_sort(li):
for i in range(len(li)-1):
for j in range(i+1, len(li)):
if li[i] > li[j]:
li[i], li[j] = li[j], li[i]
return li
if __name__ == "__main__":
li = [4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]
selection_sort(li)
print(li)
구현 3 (선택정렬)
- unittest 를 활용한다.
# 풀이 3
import unittest
def selection_sort(li):
for i in range(len(li)-1):
min_idx = i
for j in range(i+1, len(li)):
if li[min_idx] > li[j]:
min_idx = j
li[i], li[min_idx] = li[min_idx], li[i]
return li
class unit_test(unittest.TestCase):
def test(self):
self.assertEqual([1, 2, 3, 4, 5, 6], selection_sort([4, 6, 1, 3, 5, 2]))
self.assertEqual([1, 2, 3, 4, 5, 6], selection_sort([6, 4, 3, 1, 2, 5]))
self.assertEqual([1, 2, 3, 4, 5, 6], selection_sort([6, 5, 4, 3, 2, 1]))
if __name__ == '__main__':
unittest.main()
#----------------------------------------------------------------------
# Ran 1 test in 0.000s
# OK
insertion sort(삽입정렬)
- 작은 원소를 골라 앞쪽부터 정렬
- 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
- 최악의 경우 O(n^2)의 시간복잡도를 가진다.
- 하지만 안쪽 루프에 군더더기가 없기 때문에 삽입 정렬을 입력 크기가 작을 때는 빠른 내부 정렬 알고리즘이다.
31 25 12 22 11 처음 상태
31 [25] 12 22 11 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25> 31 [12] 22 11 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12> 25 31 [22] 11 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12 <22> 25 31 [11] 마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11> 12 22 25 31 종료.
구현 1(삽입정렬)
def insertion_sort(li):
for i in range(1, len(li)):
j = i - 1
key = li[i]
while li[j] > key and j >= 0:
li[j+1] = li[j]
j = j -1
li[j+1] = key
return li
if __name__ == "__main__":
li = [4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]
insertion_sort(li)
구현 2(삽입정렬)
#이미 정렬되어 있는 배열에 데이터를 삽입(insertion)한다고 하여 InsertionSort
def InsertionSort(li):
list_length = len(li)
for i in range(1, list_length):
unsortedData = li[i]
properIdx = 0
for j in range(i-1, -1, -1):
if li[j] > unsortedData:
li[j+1] = li[j]
else:
properIdx = j+1
break
li[properIdx] = unsortedData
if __name__ == "__main__":
li = [2, 5, 7, 3, 6, 1, 4, 8]
InsertionSort(li)
print(li)