카테고리 없음
병합 정렬, 퀵 정렬 (Python) 코드
oilater
2024. 5. 2. 23:25
병합정렬
n = int(input())
arr = list(map(int, input().split()))
merged_arr = [0] * n
def merge_sort(low, high):
if low < high:
mid = (low + high) // 2
merge_sort(low, mid)
merge_sort(mid+1, high)
merge(low, mid, high)
def merge(low, mid, high):
i, j = low, mid + 1
k = low
while i <= mid and j <= high:
if arr[i] <= arr[j]:
merged_arr[k] = arr[i]
i += 1
k += 1
else:
merged_arr[k] = arr[j]
j += 1
k += 1
while i <= mid:
merged_arr[k] = arr[i]
k += 1
i += 1
while j <= high:
merged_arr[k] = arr[j]
k += 1
j += 1
for k in range(low, high+1):
arr[k] = merged_arr[k]
merge_sort(0, n - 1)
for elem in arr:
print(elem, end=" ")
퀵 정렬
n = int(input())
arr = list(map(int, input().split()))
def partition(arr, low, high):
i = low - 1
for j in range(low, high):
if arr[j] < arr[high]:
i += 1
swap(i, j)
swap(i+1, high)
return i+1
def quick_sort(arr, low, high):
if low < high:
pos = partition(arr, low, high)
quick_sort(arr, low, pos - 1)
quick_sort(arr, pos + 1, high)
def swap(a, b):
arr[a], arr[b] = arr[b], arr[a]
quick_sort(arr, 0, len(arr) - 1)
for i in range(len(arr)):
print(arr[i], end=" ")
728x90
반응형
LIST