정렬
버블 정렬
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
2단계 : [4, 6, 2, 9, 1]
6과 2를 비교합니다!
6 > 2 이므로 둘을 변경합니다!
[4, 2, 6, 9, 1] 이렇게요!
3단계 : [4, 2, 6, 9, 1]
6과 9를 비교합니다!
6 < 9 이면 그대로 둡니다.
4단계 : [4, 2, 6, 9, 1]
9와 1를 비교합니다!
9 > 1 이므로 둘을 변경합니다!
[4, 2, 6, 1, 9] 이렇게요!
자, 그러면 이제 한 바퀴를 돌렸죠?
이 과정에서 가장 큰 숫자인 9가 맨 뒤로 왔습니다.
큰 게 나오면 둘의 자리를 변경했으니 가장 맨 뒤에 갔다는 소리입니다!
그러면, 맨 뒷자리를 제외하고 다시 한 번 돌리면 됩니다!
5단계 : [4, 2, 6, 1, 9]
4와 2을 비교합니다!
4 > 2 이므로 둘을 변경합니다.
[2, 4, 6, 1, 9] 이렇게요!
6단계 : [2, 4, 6, 1, 9]
4와 6을 비교합니다!
4 < 6 이면 그대로 둡니다.
7단계 : [2, 4, 6, 1, 9]
6와 1을 비교합니다!
6 > 1 이므로 둘을 변경합니다!
[2, 4, 1, 6, 9] 이렇게요!
그러면 이제 두 번째로 큰 숫자인 6이 맨 뒤에서 두번쨰로 왔습니다!
여기까지만 비교하시면 됩니다. 6과 9을 비교할 필요는 없습니다.
다시 한 번 가볼게요!
8단계 : [2, 4, 1, 6, 9]
2와 4을 비교합니다!
2 < 4 이면 그대로 둡니다.
9단계 : [2, 4, 1, 6, 9]
4와 1을 비교합니다!
4 > 1 이므로 둘을 변경합니다!
[2, 1, 4, 6, 9] 이렇게요!
자, 이제 세 번쨰로 큰 숫자인 4가 맨 뒤에서 세번째로 왔습니다!
마지막 비교만 하면 됩니다!
10단계 : [2, 1, 4, 6, 9]
2와 1을 비교합니다!
2 > 1 이므로 둘을 변경합니다!
[1, 2, 4, 6, 9] 이렇게요!
input = [4, 6, 2, 9, 1]
def bubble_sort(array):
# 이 부분을 채워보세요!
n = len(array) #O(N^2)
for i in range(n - 1): #N의 길이만큼
for j in range(n - i - 1): #N의 길이만큼
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
return
bubble_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!선택 정렬
삽입 정렬
병합 정렬 - merge
[1, 2, 3, 5] # 정렬된 배열 A
[4, 6, 7, 8] # 정렬된 배열 B
[] # 두 집합을 합칠 빈 배열 C
↓
1단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
1과 4를 비교합니다!
1 < 4 이므로 1을 C 에 넣습니다.
C:[1]
↓
2단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
2와 4를 비교합니다!
2 < 4 이므로 2를 C 에 넣습니다.
C:[1, 2]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
3과 4를 비교합니다!
3 < 4 이므로 3을 C 에 넣습니다.
C:[1, 2, 3]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
5와 4를 비교합니다!
5 > 4 이므로 4을 C 에 넣습니다.
C:[1, 2, 3, 4]
↓
3단계 : [1, 2, 3, 5]
↓
[4, 6, 7, 8]
5와 6을 비교합니다!
5 < 6 이므로 5을 C 에 넣습니다.
C:[1, 2, 3, 4, 5]
엇, 이렇게 되면 A 의 모든 원소는 끝났습니다!
그러면 B에서 안 들어간 원소인
[6, 7, 8] 은 어떡할까요?
하나씩 C 에 추가해주면 됩니다.
C:[1, 2, 3, 4, 5, 6, 7, 8] 이렇게요!
그러면 A 와 B를 합치면서 정렬할 수 있었습니다.
array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]
def merge(array1, array2):
# 이 부분을 채워보세요!
array_c = []
array1_index = 0
array2_index = 0
while array1_index < len(array1) and array2_index < len(array2):
if array1[array1_index] < array2[array2_index]:
array_c.append(array1[array1_index])
array1_index += 1
else:
array_c.append(array2[array2_index])
array2_index += 1
if array1_index == len(array1):
while array2_index < len(array2):
array_c.append(array2[array2_index])
array2_index += 1
if array2_index == len(array2):
while array1_index < len(array1):
array_c.append(array2[array1_index])
array1_index += 1
return array_c
print(merge(array_a, array_b)) # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!병합 정렬 -mergeSort
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = array[:mid]
right_array = array[mid:]
print(array)
print('left_arary', left_array)
print('right_arary', right_array)
return merge(merge_sort(left_array), merge_sort(right_array))
# 출력된 값을 보면 다음과 같습니다!
# [5, 3, 2, 1, 6, 8, 7, 4] 맨 처음 array 이고,
# left_arary [5, 3, 2, 1] 이를 반으로 자른 left_array
# right_arary [6, 8, 7, 4] 반으로 자른 나머지가 right_array 입니다!
# [5, 3, 2, 1] 그 다음 merge_sort 함수에는 left_array 가 array 가 되었습니다!
# left_arary [5, 3] 그리고 그 array를 반으로 자르고,
# right_arary [2, 1] 나머지를 또 right_array 에 넣은 뒤 반복합니다.
# [5, 3]
# left_arary [5]
# right_arary [3]
# [2, 1]
# left_arary [2]
# right_arary [1]
# [6, 8, 7, 4]
# left_arary [6, 8]
# right_arary [7, 4]
# [6, 8]
# left_arary [6]
# right_arary [8]
# [7, 4]
# left_arary [7]
# right_arary [4]