Skip to content
Snippets Groups Projects
Select Git revision
  • main default protected
1 result
Blame Permalink
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
Aufgabe02.py 2.52 KiB
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
86
87
88
89
90
91 






def HeapSort(array):
    '''Update the board according to the move and the player. If player 0 does
    the move, set the board cell to -1. If payer 1 makes the move, set the board cell
    to 1 (empty board cells have value zero).

    Parameters
    ----------
    array: list(*int)
        a list containing the integers to be sorted

    Returns
    -------
    sorted_array: a sorted copy of the array
    '''

    p = lambda i: (i-1)//2
    l = lambda i: 2*i + 1
    r = lambda i: 2*i + 2

    sorted_array = list(array)

    # Erzeuge einen max-Heap
    for i in range(1, len(sorted_array)):
        j = i
        while sorted_array[j] > sorted_array[p(j)] and j != 0:
            sorted_array[j], sorted_array[p(j)] = sorted_array[p(j)], sorted_array[j]
            j = p(j)

    # Entferne max aus dem max-Heap
    for i in range(len(sorted_array)-1, 1, -1):
        sorted_array[0], sorted_array[i] = sorted_array[i], sorted_array[0]
        j = 0
        while True:
            if l(j) >= i or r(j) >= i:
                break

            if r(j) >= i and sorted_array[l(j)] > sorted_array[j]:
                sorted_array[j], sorted_array[l(j)] = sorted_array[l(j)], sorted_array[j]
                j = l(j)

            if sorted_array[j] >= sorted_array[l(j)] and sorted_array[j] >= sorted_array[r(j)]:
                break

            if sorted_array[l(j)] > sorted_array[r(j)]:
                sorted_array[j], sorted_array[l(j)] = sorted_array[l(j)], sorted_array[j]
                j = l(j)
            else:
                sorted_array[j], sorted_array[r(j)] = sorted_array[r(j)], sorted_array[j]
                j = r(j)

    return sorted_array

def InsertionSort(array):
    '''Sort the array by inserting each element into an already sorted part of the array.

    Parameters
    ----------
    array: list(*int)
        a list containing the intergers to be sorted

    Returns
    -------
    sorted_array: a sorted copy of the array
    '''

    sorted_array = list(array)

    for i in range(1, len(array)):
        for j in range(i, 1, -1):
            if sorted_array[j] < sorted_array[j-1]:
                sorted_array[j], sorted_array[j-1] = sorted_array[j-1], sorted_array[j]
            else:
                continue

    return sorted_array

def CountingSort(array):
    '''Sort the array by counting the ocjence of each element in the array.

    Parameters
    ----------
    array: list(*int)
        a list containing the intergers to be sorted

    Returns
    -------
    sorted_array: a sorted copy of the array
    '''

    return