🌈 정렬(Sort)
🔥 버블 정렬(bubble sort) 구현
🔥 선택 정렬 구현(select sort) 구현
🔥 삽입 정렬 구현(insert sort) 구현
🔥 퀵 정렬 구현(quick sort) 구현
🔥 병합 정렬 구현(merge sort) 구현
1. 정렬 알고리즘(Sort Algorithm)
- 앞에서부터 두 인접한 데이터를 비교해서, 앞에 있는 값이 뒤에 있는 값보다 크면 자리를 교체하는 정렬을 버블 정렬이라 함
- 즉, 앞에서부터 인접한 두 값을 비교해 앞의 수가 크면 swap하여, 배열 처음부터 끝까지 순회하면 배열의 마지막 요소에 가장 큰 값이 놓임(큰 값을 계속 뒤로 밀기 때문)
- 마지막 패턴에서 맨 앞의 놓여진 수는 이미 가장 작은 수 이기 때문 교차 비교할 필요 없어 전체 배열의 길이의 -1 만큼의 순회 패턴 필요
- 🔍 for i in range(len(data)-1)
- 또한 첫번째 패턴이 끝나면, 배열의 마지막 자리에 있는 수는 가장 큰 수가 될 수 밖에 없음
- 즉, 패턴이 1회씩 증가할 때마다 값의 크기를 비교해야하는 요소의 갯수가 1개씩 감소
- 따라서, 패턴이 0부터 배열의 요소수-1까지 증가하는 i일 때, 증가하는 i만큼 요소 비교 범위가 감소
- 🔍 for j in range(len(data) - i - 1):
- 단, 1회의 패턴이 반복될 동안 swap이 한번도 일어나지 않았다면 현재 배열의 상태는 이미 정렬된 상태기 때문에 더 이상 패턴을 비교할 필요 없음
- 🔍 if swap == False: break
# 버블 정렬 구현 def bubble_sort(data): for i in range(len(data)-1): # ⭐️ 순회하는 패턴의 횟수 swap = False for j in range(len(data) - i - 1): # ⭐️ 패턴 별 비교 횟수 if data[j] > data[j + 1]: data[j], data[j+1] = data[j+1], data[j] swap = True if swap == False: break return data # 버블 정렬 TEST import random data_list = random.sample(range(100), 50) print(bubble_sort(data_list))
- 버블 정렬의 시간 복잡도는 반복문이 2개이기 때문에 n의 제곱만큼 소요됨
- 🔍 O(N^2)
2. 선택 정렬 구현(select sort) 구현
- 주어진 배열의 요소 중 최소값을 찾은 후 맨 앞에 위치한 요소와 교체한 뒤, 맨 앞의 요소를 제외한 나머지 배열을 통해 위 작업을 반복하며 정렬
- 패턴을 1회 실행할 때 마다, 맨 앞의 요소부터 가장 작은 값을 순차적으로 배치
- 마지막에 남은 요소는 가장 큰 수로 비교할 필요가 없기 때문에 패턴의 총 횟수는 데이터의 길이-1 만큼 필요
- 🔍 for i in range(len(data) - 1)
- 맨 앞 요소, 두번째 요소, 세번째 요소, ..i-1번째 요소 값과 현재 탐색 대상의 값을 비교 후 현재 탐색 대상 요소가 더 작다면 swap하기 때문에 그 요소를 change_index에 임시로 담음
- 🔍 change_index = i
- change_index와 비교할 대상은 i+1번째 요소부터 데이터의 길이의 -1번째 요소까지가 됨
- 🔍 for j in range(i+1, len(data))
- lowest_index+1과 i+1은 초기에는 같지만, 패턴이 실행되면 lowest_index는 계속 가장 작은 값의 인덱스로 덮어씌어지기 때문에 i+1로해야 순차적으로 진행 가능
- 각 패턴 마다, 스왑할 차례가된 앞의 요소는 i에 담겨 있고, 값 비교를 통해 가장 작은 값의 위치가 lowest_index에 담겨 있기 때문에 이를 swap시킴
- 🔍 data[lowest_index], data[i] = data[i], data[lowest_index]
# 선택 정렬 구현 def selection_sort(data): for i in range(len(data) - 1): lowest_index = i # ⭐️ 횟차 별 가장 작은 값이 위치한 index 번호 for j in range(i+1, len(data)): if data[lowest_index] > data[j]: lowest_index = j # ⭐️ 가장 작은 요소의 인덱스 번호를 lowest_index로 교체 data[lowest_index], data[i] = data[i], data[lowest_index] return data # 버블 정렬 TEST import random data_list = random.sample(range(100), 10) print(selection_sort(data_list))
- 선택 정렬의 시간 복잡도는 반복문이 2개이기 때문에 n의 제곱만큼 소요됨
- 🔍 O(N^2)
3. 삽입 정렬 구현(insert sort) 구현
- 삽입 정렬은 배열의 [인덱스1]를 시작 기준으로 그 앞의 값인 [인덱스 0]과 비교하여 기준 값인 [인덱스1]이 더 작다면 서로 swap함
- 그 다음으로는 시작 기준을 [인덱스2]으로 잡아 [인덱스1]와 비교하여 [인덱스2]의 값이 더 작다면 다시 그 앞의 [인덱스0]과 비교하여 [인덱스2]가 더 작다면 swap함
- 단, 값이 작지않을 때는 값이 작았던 때까지만 swap하고 반복문을 탈출함
- 이에 삽입 정렬은 배열의 길이의 -1 만큼의 패턴을 가짐
- 🔍 for i in range(len(data) - 1)
- 한 패턴 내에서 기준점은 i + 1부터 시작하여, [index1] 까지만 역순으로 순회하며 그 이전 값과 비교
- 🔍 for j in range(i + 1, 0, -1)
- [index1]까지 역순으로 순회하는 이유는, 0번으로 하게될 경우 비교 [인덱스 : -1]이 발생하기 때문
- if문으로 작을 때 까지만 반복을 진행하고, 작지 않다면 그 패턴의 반복은 종료시키면됨
# 삽입 정렬 구현 def insert_sort(data): for i in range(len(data) - 1): for j in range(i + 1, 0, -1): # 👈 기준 index의 변화(i+1부터 1까지) if data[j] < data[j-1]: data[j], data[j-1] = data[j-1], data[j] else: break return data # 삽입 정렬 TEST import random data_list = random.sample(range(100), 10) print(insert_sort(data_list))
- 삽입 정렬의 시간 복잡도는 반복문이 2개이기 때문에 n의 제곱만큼 소요됨
- 🔍 O(N^2)
4. 퀵 정렬 구현(quick sort) 구현
- pivot(기준점)을 정해서 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)로 분리하여 재귀 호출하는 작업을 반복
- 재귀함수에 전달된 리스트의 원소가 1개 이하일 때는 더 이상 리스트를 분리하지 않고 반환
- 🔍 if len(data) <= 1: return data
- 일반적으로 맨 앞 요소를 pivot으로 정해 그 이후의 요소들과 비교해 작은 요소는 왼쪽 리스트와 큰 요소는 오른쪽 리스트에 나눠 보관하기 위해 빈 리스트를 2개 생성
- 🔍 left, right = list(), list()
- 🔍 pivot = data[0]
- 분리된 요소들의 갯수가 1개 일 때, 반환하기 때문에 이를 pivot을 중심으로 합쳐줌
- 🔍 return quick_sort(left) + [pivot] + quick_sort(right)
# 퀵 정렬 구현 def quick_sort(data): if len(data) <= 1: return data # 👈 종료 조건 left, right = list(), list() pivot = data[0] for i in range(1, len(data)): if pivot > data[i]: left.append(data[i]) else: right.append(data[i]) return quick_sort(left) + [pivot] + quick_sort(right) # 👈 [] + [] + [] = [] # 퀵 정렬 TEST import random data_list = random.sample(range(100), 10) print(quick_sort(data_list))
- 리스트 Comprehension을 활용하여 퀵 정렬 구현하면, 가독성이 높아짐
# 리스트 Comprehension을 활용하여 퀵 정렬 구현 def quick_sort(data): if len(data) <= 1: return data # 👈 종료 조건 left, right = list(), list() pivot = data[0] left = [i for i in data[1:] if pivot > i] right = [i for i in data[1:] if pivot <= i] return quick_sort(left) + [pivot] + quick_sort(right) import random data_list = random.sample(range(100), 10) print(quick_sort(data_list))
- 퀵 정렬의 시간 복잡도는 O(NlogN)
5. 병합 정렬 구현(merge sort) 구현
- 병합 정렬은 리스트를 나누는 merge_split 함수와 다시 이를 비교하고 합치는 merge 함수가 필요
- merge_split 함수는 리스트가 1개의 요소를 가질 때 까지 재귀 호출을 통해 리스트를 절반으로 자르는 함수임
- 분리된 리스트를 merge 함수의 파라미터로 전달해 값의 크기를 비교 후 병합
def merge_split(data): if len(data) <= 1: return data medium = int(len(data) / 2) left = merge_split(data[:medium]) right = merge_split(data[medium:]) return left, right data_list = [3,4,1,7,2] print(merge_split(data_list)) # (([3], [4]), ([1], ([7], [2])))
- 스플릿한 리스트를 전달해 주려면, left와 right를 병합하는 함수에 전달한 다음에 return함
- 🔍
return merge(left, right)def merge(left, right): merged = list() left_point, right_point = 0, 0 #case1 : left리스트와 right리스트에 모두 원소가 아직 남아있을 때, while len(left) > left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged.append(right[right_point]) right_point += 1 else: merged.append(left[left_point]) left_point += 1 #case2 : left 리스트의 원소만 남아 있을 때, while len(left) > left_point: merged.append(left[left_point]) left_point += 1 #case3 : right 리스트의 원소만 남아 있을 때, while len(right) > right_point: merged.append(right[right_point]) right_point += 1 return merged print(merge([6], [1])) # [1, 6]
- 두 함수를 합치면 아래와 같음
# 병합 정렬 구현 # 값 비교 및 병합 함수 def merge(left, right): merged = list() left_point, right_point = 0, 0 #case1 : left/right 가 모두 존재할 때, while len(left) > left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged.append(right[right_point]) right_point += 1 else: merged.append(left[left_point]) left_point += 1 #case2 : left만 남아 있을 때, while len(left) > left_point: merged.append(left[left_point]) left_point += 1 #case3 : right만 남아 있을 때, while len(right) > right_point: merged.append(right[right_point]) right_point += 1 return merged # 스플릿 & 재귀 호출 def merge_split(data): if len(data) <= 1: return data medium = int(len(data) / 2) left = merge_split(data[:medium]) right = merge_split(data[medium:]) return merge(left, right) # 병합 정렬 TEST import random data_list = random.sample(range(100), 10) print(merge_split(data_list))
- 병합 정렬의 시간 복잡도는 O(NlogN)
Keep Going, Keep Coding!