1def partition(lst):
 2    pivot_value = lst[-1]
 3    left_lst = []
 4    right_lst = []
 5    for value in lst[:-1]:
 6        if value < pivot_value:
 7            left_lst.append(value)
 8        else:
 9            right_lst.append(value)
10    return left_lst, [pivot_value], right_lst
11
12def quicksort(lst):
13    if len(lst) < 2:
14        return lst
15    else:
16        left_lst, pivot_list, right_lst = partition(lst)
17        return quicksort(left_lst) + pivot_list + quicksort(right_lst)
18
19if __name__ == "__main__":
20    print("Without repeated values:")
21    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
22    print(f"Before sorting:\n{values}")
23    last_index = len(values) - 1
24    values = quicksort(values)
25    print(f"After sorting:\n{values}")
26
27    print("\nWith repeated values:")
28    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
29    print(f"Before sorting:\n{values}")
30    last_index = len(values) - 1
31    values = quicksort(values)
32    print(f"After sorting:\n{values}")

 1def partition(seq, start_index, stop_index):
 2    pivot = seq[stop_index]
 3    i = start_index
 4    for j in range(start_index, stop_index):
 5        if seq[j] < pivot:
 6            swap(seq, i, j)
 7            i += 1
 8    swap(seq, i, stop_index)
 9    return i
10
11
12def swap(seq, i, j):
13    seq[i], seq[j] = seq[j], seq[i]
14
15
16def quicksort_in_place(seq, start_index, stop_index):
17    if start_index < stop_index:
18        pivot_index = partition(seq, start_index, stop_index)
19        quicksort_in_place(seq, start_index, pivot_index - 1)
20        quicksort_in_place(seq, pivot_index + 1, stop_index)
21
22if __name__ == "__main__":
23    print("Without repeated values:")
24    values = [9, 1, 10, 2, 8, 7, 3, 6, 4, 5]
25    print(f"Before sorting:\n{values}")
26    last_index = len(values) - 1
27    quicksort_in_place(values, 0, last_index)
28    print(f"After sorting:\n{values}")
29
30    print("\nWith repeated values:")
31    values = [7, 9, 10, 4, 8, 1, 10, 1, 8, 7]
32    print(f"Before sorting:\n{values}")
33    last_index = len(values) - 1
34    quicksort_in_place(values, 0, last_index)
35    print(f"After sorting:\n{values}")

 1"""Kommentera koden på de markerade platserna.
 2
 3SKRIV KOMMENTARERNA SOM ATT DE VORE RIKTIGA KOMMENTARER I DIN KOD.
 4
 5- Skriv docstrings som följer PEP257 för varje funktion: "The docstring for a
 6  function or method should summarize its behavior and document its arguments,
 7  return value(s), side effects, exceptions raised, and restrictions on when it
 8  can be called (all if applicable). Optional arguments should be indicated. It
 9  should be documented whether keyword arguments are part of the interface.".
10  Se https://peps.python.org/pep-0257/ för mer information.
11- Lämna kvar existerande block-kommentarerna och skriv din kommentar under dem
12  (se exempel på kurshemsidan).
13- Inlinekommentarerna ska vara formulerade som hjälp till andra programmerare
14  som läser koden. Skriv INTE dina kommentarer formulerade som svar på
15  frågorna. Dvs. skriv inte "Syftet med villkoret är att ..." utan skriv
16  kommentaren som om frågan inte funnits där.
17
18
19# Tips
20
21- Det kan underlätta att börja med funktionen partition() följt av
22  quick_sort_helper().
23- Börja med block-kommentarerna i funktionen innan ni skriver funktionens
24  docstring.
25- Börja med block-kommentarerna i looparna innan ni skriver kommentaren för
26  loopen.
27"""
28
29
30def quick_sort(a_list):
31    """Skriv docstring för funktionen."""
32    quick_sort_helper(a_list, 0, len(a_list)-1)
33
34
35def quick_sort_helper(a_list, first, last):
36    """Skriv docstring för funktionen."""
37    # Kommentera villkorssatsen. Vad är syftet med villkoret? Beskriv vad det
38    # innebär för algoritmen om first < last?
39    if first < last:
40        # Beskriv innebörden av värdet i split. Vad har hänt med a_list
41        # efter att partition har körts?
42        split = partition(a_list, first, last)
43        # Beskriv syftet med anropet till quick_sort_helper. Vad kommer ha hänt
44        # i a_list efter anropet?
45        quick_sort_helper(a_list, first, split - 1)
46        # Beskriv syftet med anropet till quick_sort_helper. Vad kommer ha hänt
47        # i a_list efter anropet?
48        quick_sort_helper(a_list, split + 1, last)
49
50
51def partition(a_list, first, last):
52    """Skriv docstring för funktionen."""
53    # Vad är syftet med pivot_val? Till vad används det?
54    pivot_val = a_list[first]
55
56    # Vad är syftet med left_mark och right_mark? Till vad används de?
57    left_mark = first + 1
58    right_mark = last
59
60    # Beskriv syftet med while-loopen. Vad har hänt efter loopen är klar? Vad
61    # händer varje varv?
62    done = False
63    while not done:
64        # Beskriv syftet med loopen. Vad har hänt efter att loopen är klar?
65        while left_mark <= right_mark and a_list[left_mark] <= pivot_val:
66            left_mark = left_mark + 1
67        # Beskriv syftet med loopen. Vad som hänt efter att loopen är klar?
68        while a_list[right_mark] >= pivot_val and right_mark >= left_mark:
69            right_mark = right_mark - 1
70
71        # Vad betyder det när done har satts True?
72        if right_mark < left_mark:
73            done = True
74        # Berätta vad som görs om right_mark >= left_mark?
75        else:
76            a_list[left_mark], a_list[right_mark] = (
77                a_list[right_mark],
78                a_list[left_mark]
79            )
80
81    # Vad är resultatet efter denna tilldelning?
82    a_list[first], a_list[right_mark] = a_list[right_mark], a_list[first]
83
84    # Förklara vad som returneras; vad är innebörden av värdet i right_mark?
85    return right_mark