Göm meny
Gäller för: HT24

Quicksort

Nedan följer två exempelimplementationer av Quicksort i Python.

Du kan läsa mer om Quicksort på Wikipedia och (enbart i in-place-versionen) i boken av Miller & Ranum. Ni bör också söka ytterligare källor via t.ex. Google.

En bra visualisering av hur Quicksort fungerar kan ni se på Youtube.

Out-of-place list-baserad version

Den här varianten är enklare att sätta sig in i och gör det lättare att förstå den mer avancerade in-place-varianten.

 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

def partition(lst):
    pivot_value = lst[-1]
    left_lst = []
    right_lst = []
    for value in lst[:-1]:
        if value < pivot_value:
            left_lst.append(value)
        else:
            right_lst.append(value)
    return left_lst, [pivot_value], right_lst

def quicksort(lst):
    if len(lst) < 2:
        return lst
    else:
        left_lst, pivot_list, right_lst = partition(lst)
        return quicksort(left_lst) + pivot_list + quicksort(right_lst)

if __name__ == "__main__":
    print("Without repeated values:")
    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
    print(f"Before sorting:\n{values}")
    last_index = len(values) - 1
    values = quicksort(values)
    print(f"After sorting:\n{values}")

    print("\nWith repeated values:")
    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
    print(f"Before sorting:\n{values}")
    last_index = len(values) - 1
    values = quicksort(values)
    print(f"After sorting:\n{values}")

In-place index-baserad version

 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

def partition(seq, start_index, stop_index):
    pivot = seq[stop_index]
    i = start_index
    for j in range(start_index, stop_index):
        if seq[j] < pivot:
            swap(seq, i, j)
            i += 1
    swap(seq, i, stop_index)
    return i


def swap(seq, i, j):
    seq[i], seq[j] = seq[j], seq[i]


def quicksort_in_place(seq, start_index, stop_index):
    if start_index < stop_index:
        pivot_index = partition(seq, start_index, stop_index)
        quicksort_in_place(seq, start_index, pivot_index - 1)
        quicksort_in_place(seq, pivot_index + 1, stop_index)

if __name__ == "__main__":
    print("Without repeated values:")
    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
    print(f"Before sorting:\n{values}")
    last_index = len(values) - 1
    quicksort_in_place(values, 0, last_index)
    print(f"After sorting:\n{values}")

    print("\nWith repeated values:")
    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
    print(f"Before sorting:\n{values}")
    last_index = len(values) - 1
    quicksort_in_place(values, 0, last_index)
    print(f"After sorting:\n{values}")

Sidansvarig: Johan Falkenjack
Senast uppdaterad: 2024-10-16