7 examples of 'python sort array of integers' in Python

145
def counting_sort_ints(arr):
146
    """
147
    for array [7,1,5,2,2] len = 5, range of values from 0 = 0 to 7
148
    the algorithm is
149
    O(len) to count (assuming that finding max and min is O(1))
150
    O(range) for cumulative sum
151
    O(len) to copy back
152
153
    so O(2n + k) = O(n) where k is the range of items and assumed to be less than the input size.
154
155
    if the range is big (like in big_arr), the complexity is dominated by k
156
157
    However in application, k usually small.
158
    """
159
    c1, c2, c3 = 0, 0, 0  # Use to look at the counts.
160
161
    # Set up
162
    max_number = max(arr)
163
    count = [0] * (max_number+1)            # is the array of "buckets" which starts at 0 and goes to max+1
164
    output = [0] * len(arr)
165
166
    # Count occurrences of each number in arr and put it in 'bucket' in count.
167
    for number in arr:                      # the item at index number of count += 1 to found occurrence of that number
168
        count[number] += 1
169
        c1 += 1
170
171
    # Cumulative sum of occurrences.
172
    for i in range(1, len(count)):          # cumulative sum
173
        count[i] += count[i-1]
174
        c2 += 1
175
176
    # Put into output stably.
177
    for j in range(len(arr)-1, -1, -1):     # work backwards to keep stable
178
        output_idx = count[arr[j]] - 1      # -1 as output len = arr len
179
        output[output_idx] = arr[j]         # put in right place in output
180
        count[arr[j]] -= 1                  # decrement value in count
181
        c3 += 1
182
    print("first loop counting: " + str(c1) + "\nsecond loop summing: " + str(c2) + "\nthird loop copying: " + str(c3))
183
    return output

16
def CombSort(array):
17
 
18
    # The inc starts from the highest value
19
    inc = len(array)
20
21
    # This boolean tracks whether a swap occured in the current iteration
22
    swap = True
23
 
24
    # if inc is 1 and no swaps are happening, the array has been sorted
25
    # if either of them are true, trudge forward because work needs to be done
26
    while not inc == 1 or swap == True:
27
28
        # Get a new value for the inc
29
        inc = RecalibrateInc(inc)
30
31
        # Set swap to False
32
        swap = False
33
 
34
        # Do the bubb.. bubb.. CombSort
35
        # len(array) - inc because len(array) - inc + inc onwards, no elements exist
36
        for i in range(0, len(array) - inc): 
37
38
            if array[i] > array[i + inc]:
39
            
40
                # swap the array elements
41
                array[i], array[i + inc] = array[i + inc], array[i]
42
            
43
                swap = True

115
def counting_sort(arr):
116
    c1, c2, c3 = 0, 0, 0
117
118
    # set up
119
    max_number = max(arr)
120
    count = [0] * (max_number+1)            # is the array of "buckets" which starts at 0 and goes to max+1
121
    output = [0] * len(arr)
122
123
    # count occurrences of each number in arr and put it in 'bucket' in count
124
    for number in arr:                      # the item at index number of count += 1 to found occurrence of that number
125
        count[number] += 1
126
127
        c1 += 1
128
129
    # cumulative sum of occurrences
130
    for i in range(1, len(count)):          # cumulative sum
131
        count[i] += count[i-1]
132
133
        c2 += 1
134
135
    # put into output stably
136
    for j in range(len(arr)-1, -1, -1):       # work backwards to keep stable
137
        output_idx = count[arr[j]] - 1      # -1 as output len = arr len
138
        output[output_idx] = arr[j]         # put in right place in output
139
        count[arr[j]] -= 1                  # decrement value in count
140
141
        print(output)
142
        c3 += 1
143
144
    print("first loop: " + str(c1) + "\nsecond loop: " + str(c2) + "\nthird loop: " + str(c3))
145
    """
146
    for array [7,1,5,2,2] len = 5, range of values from 0 = 0 to 7
147
    the algorithm is
148
    O(len) to count (and find max?)
149
    O(range) for cumulative sum
150
    O(len) to copy back
151
152
    so O(3n + k) = O(n)
153
154
    if the range is big (like in big_arr), the complexity is dominated by k
155
156
    however in application, k usually small
157
    """
158
    return output

102
def sorttest(A):
103
  bubblesort(A)

38
def sort(a):
39
      mergeSort(a,0,len(a)-1)

113
def sort(packed, ref, reverse=True):
114
    """
115
    Sort a series of packed list, according to a ref list.
116
    Also return the original index before the sort.
117
    """
118
    assert (isinstance(packed, tuple) or isinstance(packed, list)) and isinstance(ref, list)
119
    packed = [ref] + [range(len(ref))] + list(packed)
120
    sorted_packed = [list(t) for t in zip(*sorted(zip(*packed), reverse=reverse))]
121
    return tuple(sorted_packed[1:])

7
def BitonicSort(direction, arr):
8
9
    '''
10
    
11
    The obvious condition that we have over here is that is the length of the array is less than or equal to 1, then it makes no sense to call the BitonicMerge function on the array as it contains only one element.
12
    
13
    '''
14
15
    if len(arr) <= 1:
16
17
        return arr
18
19
    else: 
20
21
        '''
22
23
        When you split the array to form a Bitonic Sequence, you want the first half to be in an increasing order and the second half to be in a decreasing order. The booleans True and False respresent increasing and decreasing order of values respectively and this will become more obvious in the BitonicCompare functions. 
24
25
        '''
26
27
        first = BitonicSort(True, arr[:len(arr) // 2])
28
        second = BitonicSort(False, arr[len(arr) // 2:])
29
30
        '''
31
32
        This is the only line that might be a little confusing and the reason for this is very simple. When we looked at the example, we executed the increasing and decreasing sorting of the array to form Bitonic Sequences simultaneously. As it turns out, we are not following the same procedures here. In fact, these operations are being done at very different times in the execution of the array but don't let that confuse you. This is the part in the process where you move to the next stage and increase the size of the Bitonic Sequence in the array.
33
34
        '''
35
36
        return BitonicMerge(direction, first + second)