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}")

 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}")

 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

"""Kommentera koden på de markerade platserna.

SKRIV KOMMENTARERNA SOM ATT DE VORE RIKTIGA KOMMENTARER I DIN KOD.

- Skriv docstrings som följer PEP257 för varje funktion: "The docstring for a
  function or method should summarize its behavior and document its arguments,
  return value(s), side effects, exceptions raised, and restrictions on when it
  can be called (all if applicable). Optional arguments should be indicated. It
  should be documented whether keyword arguments are part of the interface.".
  Se https://peps.python.org/pep-0257/ för mer information.
- Lämna kvar existerande block-kommentarerna och skriv din kommentar under dem
  (se exempel på kurshemsidan).
- Inlinekommentarerna ska vara formulerade som hjälp till andra programmerare
  som läser koden. Skriv INTE dina kommentarer formulerade som svar på
  frågorna. Dvs. skriv inte "Syftet med villkoret är att ..." utan skriv
  kommentaren som om frågan inte funnits där.


# Tips

- Det kan underlätta att börja med funktionen partition() följt av
  quick_sort_helper().
- Börja med block-kommentarerna i funktionen innan ni skriver funktionens
  docstring.
- Börja med block-kommentarerna i looparna innan ni skriver kommentaren för
  loopen.
"""


def quick_sort(a_list):
    """Skriv docstring för funktionen."""
    quick_sort_helper(a_list, 0, len(a_list)-1)


def quick_sort_helper(a_list, first, last):
    """Skriv docstring för funktionen."""
    # Kommentera villkorssatsen. Vad är syftet med villkoret? Beskriv vad det
    # innebär för algoritmen om first < last?
    if first < last:
        # Beskriv innebörden av värdet i split. Vad har hänt med a_list
        # efter att partition har körts?
        split = partition(a_list, first, last)
        # Beskriv syftet med anropet till quick_sort_helper. Vad kommer ha hänt
        # i a_list efter anropet?
        quick_sort_helper(a_list, first, split - 1)
        # Beskriv syftet med anropet till quick_sort_helper. Vad kommer ha hänt
        # i a_list efter anropet?
        quick_sort_helper(a_list, split + 1, last)


def partition(a_list, first, last):
    """Skriv docstring för funktionen."""
    # Vad är syftet med pivot_val? Till vad används det?
    pivot_val = a_list[first]

    # Vad är syftet med left_mark och right_mark? Till vad används de?
    left_mark = first + 1
    right_mark = last

    # Beskriv syftet med while-loopen. Vad har hänt efter loopen är klar? Vad
    # händer varje varv?
    done = False
    while not done:
        # Beskriv syftet med loopen. Vad har hänt efter att loopen är klar?
        while left_mark <= right_mark and a_list[left_mark] <= pivot_val:
            left_mark = left_mark + 1
        # Beskriv syftet med loopen. Vad som hänt efter att loopen är klar?
        while a_list[right_mark] >= pivot_val and right_mark >= left_mark:
            right_mark = right_mark - 1

        # Vad betyder det när done har satts True?
        if right_mark < left_mark:
            done = True
        # Berätta vad som görs om right_mark >= left_mark?
        else:
            a_list[left_mark], a_list[right_mark] = (
                a_list[right_mark],
                a_list[left_mark]
            )

    # Vad är resultatet efter denna tilldelning?
    a_list[first], a_list[right_mark] = a_list[right_mark], a_list[first]

    # Förklara vad som returneras; vad är innebörden av värdet i right_mark?
    return right_mark