오늘 알고리즘 정렬 문제를 풀기 전에 부족했던 정렬에 대한 개념을 다시한번 다듬는 시간을 갖었다. 처음에 두루뭉술하게 알고만 있던 지식들을 직접 코드까지 짜보니깐 어느정도 머리에 자리잡아가는 것이 느껴졌다. 역시 코드는 직접 생각하고 짜야 나의 것이 된다는 것을 다시 한번 느낄 수 있었다.
정렬을 하는방법은 여러가지가 있는데 그 중 다음의 항목들에 대해 알아보자.
동작 방식
N개의 요소를 가진 배열이 존재한다고 가정했을 때, 버블 정렬의 동작 방식은 다음과 같다.
- 첫번째 자료와 두번째 자료를 비교한다.
- 비교한 값중 더 큰 값이 뒤로가게 서로 자리를 교체한다.
- 두번째 자료와 세번재 자료를 비교한다.
- 비교한 값중 더 큰 값이 뒤로가게 서로 자리를 교체한다.
...- N-1번째 자료와 N번째 자료를 비교한다.
- 비교한 값중 더 큰값이 뒤로가게 서로 자리를 교체한다.
- 6번까지의 동작으로 N번째 자료는 정렬이 완료된다.
- 6번까지의 과정을 N-1번 실행하여 배열을 정렬한다.
특징
버블 정렬의 특징은 다음과 같다.
코드
# 다음의 배열을 정렬하시오.
input = [4, 6, 2, 9, 1]
def buble_sort(array):
n = len(array)
for i in range(n - 1): # 마지막으로 주어지는 값은 정렬하지 않아도 이미 정렬되어 있다고 판단할 수 있기 때문에 -1을 한다.
for j in range(n-i-1): # 뒤에서부터 i만큼의 자료가 정렬이 완료되기 때문에 비교횟수에서 i를 뺀다.
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j] # a,b = b,a 를 사용하면 두 배열의 자료를 서로 바꿀 수 있다.
return
buble_sort(input)
print(input)
# [1, 2, 4, 6, 9]
동작 방식
N개의 요소를 가진 배열이 존재한다고 가정했을 때, 선택 정렬의 동작 방식은 다음과 같다.
- N개의 자료를 모두 확인해서 가장 작은 자료를 찾아낸다.
- 자료는 정렬되지 않은 자료들 중 맨 앞의 자료와 서로 바꾼다.
...- 마지막으로 남은 2개의 자료들 중 작은 자료를 찾아낸다.
- 자료는 정렬되지 않은 자료들 중 앞의 자료와 서로 바꾼다.
특징
선택 정렬의 특징은 다음과 같다.
코드
input = [4, 6, 2, 9, 1]
def selection_sort(array):
n = len(array)
for i in range(n-1):
min_index = i # 가장 작은 값이 들어있는 index값을 의미한다.
for j in range(n-i-1):
if array[min_index] > array[i+j+1]: # for문이 돌때마다 비교하는 맨 앞 요소를 하나씩 증가 시켜준다. i+j+1
min_index = i+j+1
array[i], array[min_index] = array[min_index], array[i]
return
selection_sort(input)
print(input)
# [1, 2, 4, 6, 9]
동작 방식
N개의 요소를 가진 배열이 존재한다고 가정했을 때, 선택 정렬의 동작 방식은 다음과 같다.
- 배열에서 자료를 하나 선택한다. 자료 하나는 정렬되어 있다고 할 수 있다.
- 배열에서 자료를 하나 더 선택한다.
- 선택한 자료를 정렬되어 있는 배열에 추가한다.
- 추가한 자료와 앞에 있는 자료를 서로 비교한다.
- 추가한 자료의 값이 정렬되어 있는 자료보다 더 커질때까지 자료를 바꾼다.
...- 배열에서 마지막으로 정렬되지 않은 자료 하나를 선택한다.
- 추가한 자료의 값이 정렬되어 있는 자료보다 더 커질때까지 자료를 바꾼다.
특징
삽입 정렬의 특징은 다음과 같다.
코드
input = [4, 6, 2, 9, 1]
def insertion_sort(array):
n = len(array)
for i in range(1, n): # 배열의 첫번째 자료를 정렬되어 있다 가정하기 때문에 1번부터 정렬한다.
for j in range(i):
if array[i-j-1] > array[i-j]: # 배열의 역으로 순차적으로 비교해가기 때문에 i-j를 사용한다.
array[i-j-1], array[i-j] = array[i-j], array[i-j-1]
else:
break # 추가한 자료가 정렬이 완료되면 새로운 자료를 정렬하기 위해 반복문을 끝낸다.
return
insertion_sort(input)
print(input)
# [1, 2, 4, 6, 9]
array = [5, 3, 2, 1, 6, 8, 7, 4]
# 병합정렬 : 정렬되어 있는 상태가 될때까지 쪼개서(배열내 요소가 한개 있을 때를 의미) 다시 합치면서 정렬하는 방식
# Big_O(NlogN)
# 재귀함수를 사용한다.
def merge_sort(array): # 재귀함수를 사용해서 array를 정렬되어 있는 상태가 될때까지 쪼갠다.
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = merge_sort(array[:mid])
right_array = merge_sort(array[mid:])
return merge(left_array, right_array)
def merge(array1, array2): # 정렬되어 있는 두개의 array에 들어있는 자료들을 비교하며 새로운 sorted_list라는 리스트에 넣어준다.
sorted_list = []
array1_pointer = 0
array2_pointer = 0
while array1_pointer < len(array1) and array2_pointer < len(array2):
if array1[array1_pointer] < array2[array2_pointer]:
sorted_list.append(array1[array1_pointer])
array1_pointer += 1
else:
sorted_list.append(array2[array2_pointer])
array2_pointer += 1
if array1_pointer >= len(array1):
while array2_pointer < len(array2):
sorted_list.append(array2[array2_pointer])
array2_pointer += 1
if array2_pointer >= len(array2):
while array1_pointer < len(array1):
sorted_list.append(array1[array1_pointer])
array1_pointer += 1
return sorted_list
print(merge_sort(array))
정렬 종류마다 특징과 코드까지...!! 덕분에 저도 한번 정리하고 갑니다 👍