참조
버블정렬
선택정렬
삽입정렬
연습
버블 정렬
버블정렬 wiki
- 왼쪽에서 출발
- 1-2 비교, 2가 더 작으면 교환, 아님 패스
- 2-3 비교, 3이 더 작으면 교환, 아님 패스
- 맨 오른쪽 부터 정렬됨
def sort_bubble_start(arr):
var result = sort_bubble(arr, len(arr))
return
def sort_bubble(arr, arr_size):
if arr_size < 2:
return arr
for i in range(arr_size-1):
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
print arr
return sort_bubble(arr, arr_size-1)
선택 정렬
선택정렬 wiki
- 왼쪽부터 출발
- 1번인 내가 제일 작은 숫자로 min 지정
- 내 오른쪽부터 min이랑 비교, 더 작으면 min으로 지정
- 그렇게 리스트에서 제일 작은 애 찾아서
- 나랑 자리 바꿈
def sort_select(arr):
arr_size = len(arr)
for i in range(arr_size):
min_index = i
for j in range(arr_size - i):
tar_index = j + i
if arr[tar_index] < arr[min_index]:
min_index = tar_index
if i != min_index:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
삽입 정렬
삽입정렬 wiki
- 왼쪽부터 출발
- 내 왼쪽 리스트 중에 나보다 작은수, 나보다 큰수 사이로 삽입
-> (내 왼쪽은 정렬이 되어있으므로 나보다 작은수 처음 발견했을 때 바로 뒤에 꽂으면 됌)
def sort_insert(arr):
arr_size = len(arr) - 1
for i in range(arr_size):
start_index = i + 1
tar_val = arr[start_index]
j = start_index
while j > 0 and tar_val < arr[j-1]:
arr[j] = arr[j-1]
j -= 1
arr[j] = tar_val
return arr
테스트 코드
import unittest
import sort
class TestSort(unittest.TestCase):
def setUp(self):
self.test_array = [
[10, 7, 17, 3, 4, 21, 6, 20, 1],
[10, 7, 17, 3, 4, 21, 6, 20, 1, 9],
[7, 6, 5, 4, 3, 2, 1],
[1, 2, 3, 4, 5, 6, 7],
[3, 3, 4, 3, 6, 5, 6, 4, 3, 4, 6, 3],
[1],
[2, 10],
[10, 2],
[],
]
def tearDown(self):
del self.test_array
def test_bubble(self):
for array in self.test_array:
self.assertEqual(sort.sort_bubble_start(array), sorted(array))
def test_insertion(self):
for array in self.test_array:
self.assertEqual(sort.sort_insert(array), sorted(array))
def test_selection(self):
for array in self.test_array:
self.assertEqual(sort.sort_select(array), sorted(array))
unittest.main()
선택정렬을 이용하여 문제풀이
삽입정렬을 이용하여 문제풀이
