Skip to content

Instantly share code, notes, and snippets.

@dongwooklee96
Created August 24, 2021 07:26
Show Gist options
  • Save dongwooklee96/ec66a918d400d27743b60f5b0effce8f to your computer and use it in GitHub Desktop.
Save dongwooklee96/ec66a918d400d27743b60f5b0effce8f to your computer and use it in GitHub Desktop.
정렬
from random import randint
def bubble_sort(arr):
n = len(arr)
for i in range(n):
done_sort = True
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
done_sort = False
if done_sort:
break
return arr
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
key_item = arr[i]
j = i - 1
while j >= 0 and arr[j] > key_item:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key_item
return arr
def merge_sort(arr):
def merge(left, right):
left_len = len(left)
right_len = len(right)
result = []
left_index = right_index = 0
while len(result) < left_len + right_len:
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
if right_index == right_len:
result.extend(left[left_index:])
break
if left_index == left_len:
result.extend(right[right_index:])
break
return result
n = len(arr)
if n < 2:
return arr
mid_index = n // 2
left = merge_sort(arr[:mid_index])
right = merge_sort(arr[mid_index:])
return merge(left, right)
def quicksort(arr):
arr_len = len(arr)
if arr_len < 2:
return arr
low, same, high = [], [], []
pivot = arr[randint(0, arr_len - 1)]
for item in arr:
if item < pivot:
low.append(item)
elif item == pivot:
same.append(item)
elif item > pivot:
high.append(item)
return quicksort(low) + same + quicksort(high)
def binary_search(arr, key, start, end):
if end - start <= 1:
if arr[start] > key:
return start - 1
else:
return start
mid = (start + end) // 2
if arr[mid] < key:
return binary_search(arr, key, mid, end)
elif arr[mid] > key:
return binary_search(arr, key, start, mid)
else:
return mid
def insertion_sort(arr, run_s=0, run_e=None):
if run_e is None:
run_e = len(arr) - 1
for i in range(run_s + 1, run_e + 1):
v = arr[i]
pos = binary_search(arr, v, run_s, i) + 1
for k in range(i, pos, -1):
arr[k] = arr[k - 1]
arr[pos] = v
def timsort(arr):
def merge(left, right):
left_len = len(left)
right_len = len(right)
result = []
left_index = right_index = 0
while len(result) < left_len + right_len:
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
if right_index == right_len:
result.extend(left[left_index:])
break
if left_index == left_len:
result.extend(right[right_index:])
break
return result
min_run = 32
n = len(arr)
for i in range(0, n, min_run):
insertion_sort(arr, i, min((i + min_run - 1), n - 1))
size = min_run
while size < n:
for start in range(0, n, size * 2):
mid = start + size - 1
end = min((start + size * 2 - 1), (n - 1))
merged = merge(arr[start:mid + 1], arr[mid + 1:end + 1])
arr[start:start + len(merged)] = merged
size *= 2
return arr
if __name__ == "__main__":
input_array = [randint(0, 100) for i in range(100)]
res = timsort(input_array)
print(f'{sorted(res)}')
print(f'{sorted(input_array) == res}')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment