오늘은 퀵정렬부터 시작해서 정렬파트 마무리 지었습니다.
전체적으로 코드 리뷰를 해보자면,
< 버블 정렬 구현 문제 >
[ bubble sort ]
버블 정렬은 인접한 두 요소를 비교하여 정렬하는 간단한 정렬 알고리즘입니다.
마치 거품이 위로 올라가는 것처럼 큰 값이 배열의 끝으로 이동하기 때문에 "버블 정렬"이라는 이름이 붙었습니다.
n = int(input())
arr = list(map(int, input().split()))
def bubble_sort(arr):
for i in range(n):
swap = False
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swap = True
if not swap:
break
return arr
sorted_arr = bubble_sort(arr)
print(" ".join(map(str, sorted_arr)))
[ 동작 ]
- 배열의 첫 번째 요소부터 인접한 요소와 비교하여 더 큰 값이 오른쪽으로 이동하도록 한다.
- 한 번의 순회가 끝나면 가장 큰 값이 배열의 끝에 위치하게 된다.
- 다음 순회에서는 마지막 요소를 제외하고 다시 비교를 반복한다.
- 위 과정을 반복하면 배열이 정렬된다.
- 만약 정렬이 완료된 상태라면 더 이상 교환이 일어나지 않으므로, 이를 감지하여 정렬을 조기에 종료할 수도 있다.
for i in range(n)
전체 배열을 순회
swap = False
교환 여부를 체크하는 변수로, 만약 교환이 발생하지 않으면 정렬을 멈춤
for j in range(0, n-i-1)
이미 정렬된 부분을 제외하고 인접한 요소들을 비교
if arr[j] > arr[j+1]
앞의 요소가 뒤의 요소보다 크다면 위치를 바꿈
swap = True
교환이 발생했음을 기록
if not swap: break
만약 교환이 발생하지 않았다면 조기 종료하여 불필요한 연산을 줄임
< 선택 정렬 구현 문제 >
[ selection sort ]
선택 정렬은 가장 작은 값을 찾아 앞쪽으로 정렬하는 간단한 정렬 알고리즘입니다.
배열에서 최솟값을 찾아 맨 앞 요소와 교환하는 방식으로 동작하며, 정렬이 완료될 때까지 반복됩니다.
n = int(input())
arr = list(map(int, input().split()))
def selection_sort(arr):
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
sorted_arr = selection_sort(arr)
print(" ".join(map(str, sorted_arr)))
[ 동작 ]
- 배열의 첫 번째 요소부터 마지막 전 요소까지 순회하면서 가장 작은 값을 찾는다.
- 찾은 최솟값을 현재 위치의 요소와 교환한다.
- 다음 순회에서는 첫 번째 요소를 제외하고 같은 과정을 반복한다.
- 이 과정을 배열이 정렬될 때까지 반복한다.
for i in range(n - 1)
전체 배열을 순회하면서 최솟값을 찾을 범위를 점점 줄임
min_index = i
최솟값의 인덱스를 저장하는 변수
for j in range(i + 1, n)
현재 위치 이후 요소들과 비교하며 최솟값을 찾음
if arr[j] < arr[min_index]
더 작은 값이 발견되면 최솟값의 인덱스를 업데이트
arr[i], arr[min_index] = arr[min_index], arr[i]
현재 위치의 요소와 최솟값을 교환하여 정렬을 진행
< 삽입 정렬 구현 문제 >
[ insertion sort ]
삽입 정렬은 필요할 때만 위치를 변경하는 효율적인 정렬 알고리즘입니다.
각 요소를 적절한 위치에 삽입하여 정렬하며, 정렬된 부분과 정렬되지 않은 부분을 나누어 동작합니다.
n = int(input())
arr = list(map(int, input().split()))
def insert_sort(arr):
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
sorted_arr = insert_sort(arr)
print(" ".join(map(str, sorted_arr)))
- 배열의 두 번째 요소부터 시작하여 앞쪽 정렬된 부분과 비교하면서 자신의 위치를 찾는다.
- 더 큰 값을 오른쪽으로 이동시키며 적절한 위치에 현재 요소를 삽입한다.
- 이 과정을 배열이 정렬될 때까지 반복한다.
for i in range(1, n)
두 번째 요소부터 시작하여 정렬을 진행
key = arr[i]
현재 삽입할 값을 저장
j = i - 1
정렬된 부분의 마지막 인덱스를 저장
while j >= 0 and arr[j] > key
현재 요소보다 큰 값이 있다면 한 칸씩 오른쪽으로 이동
arr[j + 1] = key
모든 요소를 이동한 후, 현재 요소를 적절한 위치에 삽입
< 기수 정렬 구현 문제 >
[ radix sort ]
기수 정렬은 숫자의 자릿수를 기준으로 정렬하는 알고리즘입니다.
자릿수를 비교해 정렬하는 방식입니다.
n = int(input())
numbers = list(map(int, input().split()))
def counting_sort(numbers, digit_place):
length = len(numbers)
sorted_numbers = [0] * length
count_array = [0] * 10
for i in range(length):
digit = (numbers[i] // digit_place) % 10
count_array[digit] += 1
for i in range(1, 10):
count_array[i] = count_array[i] + count_array[i - 1]
i = length - 1
while i >= 0:
digit = (numbers[i] // digit_place) % 10
sorted_numbers[count_array[digit] - 1] = numbers[i]
count_array[digit] -= 1
i -= 1
for i in range(length):
numbers[i] = sorted_numbers[i]
def radix_sort(numbers):
max_value = max(numbers)
digit_place = 1
while max_value // digit_place > 0:
counting_sort(numbers, digit_place)
digit_place *= 10
radix_sort(numbers)
print(" ".join(map(str, numbers)))
[ 동작 ]
- 가장 작은 자릿수(1의 자리)부터 시작해서 특정 자릿수를 기준으로 정렬한다.
- 정렬이 끝나면, 그다음 자릿수(10의 자리, 100의 자리, …) 를 기준으로 다시 정렬한다.
- 가장 큰 자릿수까지 정렬이 끝나면, 전체 배열이 정렬된 상태가 된다.
max_value = max(numbers)
배열에서 가장 큰 값을 찾아 최대 자릿수를 결정
digit_place = 1
자릿수를 1의 자리부터 시작
while max_value // digit_place > 0
최대 자릿수까지 반복하며 자릿수별로 정렬을 수행
counting_sort(numbers, digit_place)
현재 자릿수를 기준으로 계수 정렬을 수행하여 정렬을 진행
sorted_numbers[count_array[digit] - 1] = numbers[i]
누적합을 이용하여 안정적인 정렬을 수행
numbers[i] = sorted_numbers[i]
정렬된 결과를 원래 배열로 복사
< 병합 정렬 구현 문제 >
[ merge sort ]
기수 정렬은 숫자의 자릿수를 기준으로 정렬하는 알고리즘입니다.
자릿수를 비교해 정렬하는 방식입니다.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
sorted_arr = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr
n = int(input())
arr = list(map(int, input().split()))
sorted_arr = merge_sort(arr)
print(" ".join(map(str, sorted_arr)))
[ 동작 ]
- 배열을 두 부분으로 나눈다.
- 그 후, 각각의 부분을 정렬한다.
- 두 개의 정렬된 배열을 합쳐서 하나의 정렬된 배열로 만든다.
max_value = max(numbers)
배열의 최댓값을 찾아 최대 자릿수를 결정합니다.
이는 정렬이 몇 번 반복되어야 하는지 결정하는 기준이 됩니다.
digit_place = 1
정렬을 1의 자리부터 시작합니다.
각 자릿수를 기준으로 순차적으로 정렬을 진행합니다.
while max_value // digit_place > 0
최대 자릿수까지 반복합니다.
나눗셈의 결과가 0이 되면 모든 자릿수에 대한 정렬이 완료된 것입니다.
counting_sort(numbers, digit_place)
현재 자릿수를 기준으로 계수 정렬을 수행합니다.
각 반복에서 특정 자릿수를 기준으로 안정적 정렬이 이루어집니다.
sorted_numbers[count_array[digit] - 1] = numbers[i]
누적 빈도수를 이용해 각 원소의 올바른 위치를 결정합니다.
계수 정렬의 핵심 부분으로, 안정적 정렬을 보장합니다.
numbers[i] = sorted_numbers[i]
정렬된 배열의 결과를 원래 배열에 복사하여 다음 자릿수 정렬을 준비합니다.
< 퀵 정렬 구현 문제 >
[ radix sort ]
퀵 정렬은 분할 방식의 정렬 알고리즘입니다.
주어진 배열을 기준으로 배열을 두 부분으로 나누고, 각 부분에 대해 재귀적으로 정렬을 수행합니다.
n = int(input())
arr = list(map(int, input().split()))
def quick_sort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
quick_sort(arr, 0, n - 1)
print(*arr)
[ 동작 ]
- 기준 원소(pivot) 를 선택 일반적으로 마지막 원소를 pivot으로 선택
- 배열을 두 부분으로 분할한다.
- 재귀적으로 분할하고 분할된 두 부분에 대해 동일한 방식으로 정렬
quick_sort
주어진 배열을 퀵 정렬 알고리즘을 이용해 정렬
partition
배열을 두 부분으로 나누는 역할을 하며, 주어진 기준 값(피벗)을 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 배치
quick_sort(arr, low, high)
pivot 오른쪽 부분을 정렬
arr[i + 1], arr[high] = arr[high], arr[i + 1]
주어진 배열 arr를 low와 high 범위로 나누어 퀵 정렬을 재귀적으로 적용
arr[i], arr[j] = arr[j], arr[i]
조건에 맞는 원소들을 위치를 교환하여, 정렬
arr[i + 1], arr[high] = arr[high], arr[i + 1]
피벗 값을 올바른 자리에 배치하여 분할
< 힙 정렬 구현 문제 >
[ heap sort ]
힙 정렬은 트리 구조를 이용한 정렬 알고리즘입니다
배열을 최대 힙 또는 최소 힙 구조로 만들고, 최댓값 또는 최솟값를 배열의 끝으로 옮겨가며 정렬하는 방식입니다.
n = int(input())
arr = [0] + list(map(int, input().split()))
def heapify(arr, n, i):
largest = i
left = 2 * i
right = 2 * i + 1
if left <= n and arr[left] > arr[largest]:
largest = left
if right <= n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr) - 1
for i in range(n // 2, 0, -1):
heapify(arr, n, i)
for i in range(n, 1, -1):
arr[1], arr[i] = arr[i], arr[1]
heapify(arr, i - 1, 1)
heap_sort(arr)
print(*arr[1:])
[ 동작 ]
- 힙 정렬은 배열을 최대 힙 구조로 변환하여, 루트를 배열의 끝으로 옮긴다.
- 그 후, 배열의 크기를 줄이는것을 반복하여 다음 자리를 기준으로 정렬을 계속한다.
- 각 단계에서 루트와 마지막 원소를 교환한다.
- 힙 구조를 유지하며 배열을 정렬한다.
heapify(arr, n, i)
주어진 인덱스 i에서 자식 노드들과 비교하여 힙 구조를 유지하도록 재정렬
heap_sort(arr)
배열을 최대 힙으로 변환한 후, 루트(최댓값)를 끝으로 보내며 정렬을 반복
arr[i], arr[largest] = arr[largest], arr[i]
부모 노드와 자식 노드의 값을 교환하여 힙 유지
heapify(arr, n, largest)
자식 노드를 기준으로 힙을 재정렬하기 위해 재귀적으로 호출