hackoctober/sorting.py at master · TabishAjaz/hackoctober · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import sys
import random

def quicksort(arr, l, r):
    if l >= r:
        return
    pivot = arr[r]
    i = l
    for j in range(l, r):
        if arr[j] < pivot:
            arr[j], arr[i] = arr[i], arr[j]
            i += 1
    arr[i], arr[r] = arr[r], arr[i]
    quicksort(arr, l, i - 1)
    quicksort(arr, i + 1, r)

def heapify(arr, n, i):
    left = 2 * i + 1
    right = 2 * i + 2
    largest = i
    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 heapsort(arr):
    n = len(arr)
    i = n // 2 - 1
    while i >= 0:
        heapify(arr, n, i)
        i -= 1
    i = n - 1
    while i >= 0:
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
        i -= 1

arr = [3, 8, 2, 103, 282, 182, 6, 4, 29, 19]
quicksort(arr, 0, len(arr) - 1)
for i in arr:
    sys.stdout.write(str(i) + " ")
print("")

random.shuffle(arr)
heapsort(arr)
for i in arr:
    sys.stdout.write(str(i) + " ")
print("")