늦은 프로그래밍 이야기
정렬 본문
정렬
버블정렬
특징
- 리스트의 두가지 자료를 비교하여 둘중 작은 것을 왼쪽에 둔다.
- 한 바퀴를 실행하면 가장 큰 데이터가 가장 오른쪽으로 가게 된다.
- 두 바퀴를 실행하면 두번째로 큰 데이터가 오른쪽에서 두번째로 가게 된다.
- 모든 바퀴 수를 실행하면 데이터가 순서에 맞게 정렬되게 된다.
- 따라서, 오른쪽부터 정렬이 된다.
구현
input = [4, 6, 2, 9, 1]
def bubble_sort(array):
n = len(array)
for i in range(n - 1): # 이중반복문을 통해 아래와 같이 배열의 인덱스를 반복한다.
for j in range(n - i - 1): # 맨마지막 인덱스를 제외하고 반복, 마지막 인덱스를 하나씩 줄여감.
if array[j] > array[j + 1]: # 인덱스 j와 오른쪽 인덱스인 j+1을 비교 왼쪽이 크다면,
array[j], array[j + 1] = array[j + 1], array[j] # 오른쪽으로 옮겨준다.
return
bubble_sort(input)
print(input)
- a, b = b, a 로 변수의 위치를 변경할 수 있다.
- 이중 반복문 구조 (n = 5)
| i | j |
| 0 | 5 - 0 - 1 = 4, 따라서 0, 1, 2, 3 |
| 1 | 5 - 1 - 1 = 3, 따라서 0, 1, 2 |
| 2 | 5 - 2 - 1 = 2, 따라서 0, 1 |
| 3 | 5 - 3 - 1 = 1, 따라서 0 |
- 이중 반복문을 사용하므로 O(N^2)의 시간복잡도를 가진다.
선택 정렬
특징
- 선택해서 정렬한다.
- 배열을 탐색한 후 가장 작은 데이터를 맨 왼쪽의 데이터와 자리를 바꾼다.
- 맞춘 데이터를 제외하고 다시 배열을 탐색 후 가장 작은 데이터를 왼쪽 두번째 데이터와 자리를 바꾼다.
- 따라서, 왼쪽부터 정렬이 된다.
구현
input = [4, 6, 2, 9, 1]
def selection_sort(array):
n = len(array)
for i in range(n - 1): # 배열의 모든 인덱스를 반복
min_index = i # 왼쪽의 인덱스가 변수에 담긴다.
for j in range(n - i): # 아래와 같이 반복
if array[i + j] < array[min_index]: # 반복된 배열의 원소를 하나하나 비교.
min_index = i + j # i 위치에 가장 작은 수가 온다.
array[i], array[min_index] = array[min_index], array[i]
return
selection_sort(input)
print(input)- 이중 반복문 구조 (n = 5)
| i | j | i + j |
| 0 | 5 - 0 = 5, 따라서 0, 1, 2, 3, 4 | 0, 1, 2, 3, 4 |
| 1 | 5 - 1 = 4, 따라서 0, 1, 2, 3 | 1, 2, 3, 4 |
| 2 | 5 - 2 = 3, 따라서 0, 1, 2 | 2, 3, 4 |
| 3 | 5 - 3 = 2, 따라서 0, 1 | 3, 4 |
| 4 | 5 - 4 = 1, 따라서 0 | 4 |
- 이중 반복문을 사용하므로 O(N^2)의 시간복잡도.
삽입 정렬
특징
- 올바른 위치에 삽입한다.
- 왼쪽부터 인덱스 하나씩 늘려가며 정렬한다.
- “기존 왼쪽에 있는 데이터”와 “오른쪽의 데이터”를 비교하여 왼쪽으로 정렬한다.
- 0번 인덱스의 데이터는 정렬되어 있다.
- 1번 인덱스를 0번 인덱스와 비교하여 0, 1번을 정렬한다.
- 2번 인덱스를 1, 0번 인덱스와 비교하여 0, 1, 2번을 정렬한다.
- 3번 인덱스를 2, 1, 0번 인덱스와 비교하여 0, 1, 2, 3번을 정렬한다.
- 끝까지 반복한다.
- 비교할때는 버블정렬의 방식을 사용한다. (왼쪽으로)
- 따라서, 왼쪽부터 정렬이 된다.
구현
input = [4, 6, 2, 9, 1]
def insertion_sort(array):
n = len(array)
for i in range(1, n): # 배열의 인덱스 1부터 n-1까지 반복
for j in range(i): # i가 1인 경우, j는 0
if array[i - j - 1] > array[i - j]: # i가 1인 경우, array[0]과 array[1] 중 왼쪽이 크면,
array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1] # 위치 변경
else:
break # 왼쪽 데이터가 오른쪽 데이터보다 크지 않을 경우 멈추고 첫번째 반복문으로 돌아간다.
return
insertion_sort(input)
print(input)- 이중 반복문 구조 (n = 5)
| i | j | i - j |
| 1 | 0 | 1 |
| 2 | 0, 1 | 2, 1 |
| 3 | 0, 1, 2 | 3, 2, 1 |
| 4 | 0, 1, 2, 3 | 4, 3, 2, 1 |
- 이중 반복문을 사용하지만, break문을 사용하므로 최선의 경우에는 N의 복잡도가 나올 수 있다.
병합 정렬
특징
- 병합 : 배열의 앞부분, 뒷부분 두그룹으로 나누어 각각 정렬 후 합치며 새로운 배열에 정렬.
- 분할 정복의 개념 적용
- 분할 정복 : 문제를 작은 두개의 문제로 분리, 각각을 해결, 결과를 모아서 문제를 해결.
- 배열을 두개로 끝까지 분리하면 길이가 1인 배열이 된다.
- 길이가 1인 배열을 2개씩 병합하며 새로운 배열에 정렬한다.
구현
- 합치기
array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]
def merge(array1, array2):
array_c = [] # 새로운 배열을 생성한다.
array1_index = 0 # 배열1의 인덱스 변수를 설정
array2_index = 0 # 배열2의 인덱스 변수를 설정
while array1_index < len(array1) and array2_index < len(array2): # 배열1과 배열2의 모든 인덱스의 데이터를 반복한다.
if array1[array1_index] < array2[array2_index]: # 배열1의 데이터가 작은 경우
array_c.append(array1[array1_index]) # 새로운 배열에 배열1의 데이터를 담는다.
array1_index += 1 # 배열1의 인덱스를 다음으로 넘긴다.
else: # 배열2의 데이터가 작은 경우
array_c.append(array2[array2_index]) # 새로운 배열에 배열2의 데이터를 담는다.
array2_index += 1 # 배열2의 인덱스를 다음으로 넘긴다.
if array1_index == len(array1): # 배열1의 인덱스가 끝까지 간 경우
while array2_index < len(array2): # 배열2의 남은 인덱스의 데이터를 반복한다.
array_c.append(array2[array2_index]) # 새로운 배열에 배열2의 데이터를 담는다.
array2_index += 1
if array2_index == len(array2): # 배열2의 인덱스가 끝까지 간 경우
while array1_index < len(array1): # 배열1의 남은 인덱스의 데이터를 반복한다.
array_c.append(array2[array1_index]) # 새로운 배열에 배열1의 데이터를 담는다.
array1_index += 1
return array_c
print(merge(array_a, array_b))
- 분할
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
if len(array) <= 1: # 탈출조건으로 배열의 길이가 1보다 작거나 같을때
return array # 멈춤.
mid = len(array) // 2 # 배열의 중간 인덱스를 변수에 담는다.
left_array = merge_sort(array[:mid]) # 배열의 처음부터 mid 인덱스까지 슬라이싱 하여 왼쪽 배열을 담는다.
right_array = merge_sort(array[mid:]) # 배열의 mid 인덱스부터 끝까지 슬라이싱 하여 오른쪽 배열을 담는다.
# 재귀함수를 사용하여 슬라이싱한 배열을 반복적으로 슬라이싱 한다.
return merge(left_array, right_array) # 합치기 함수를 실행하여 왼쪽과 오른쪽 배열을 순서에 맞게 정렬한다.
def merge(array1, array2):
print(merge_sort(array))- 병합 정렬의 시간복잡도는 O(NlogN)이다.
'내일배움캠프 > 자료구조 알고리즘' 카테고리의 다른 글
| 해쉬 (0) | 2022.11.14 |
|---|---|
| 스택, 큐 (0) | 2022.11.11 |
| Array, Linked List (0) | 2022.11.10 |
| 최대값 찾기, 최빈값 찾기 (0) | 2022.11.09 |
| 시간복잡도, 공간복잡도 (0) | 2022.11.09 |
