# Demo entry 6315341

integer_sort

Submitted by anonymous on Nov 01, 2016 at 12:03
Language: Python. Code size: 1.7 kB.

```#!/usr/bin/env python2.7
# -*- coding: utf-8 -*-
'''
Assignment 1: Integer Sort

Team Number: 10
Student Names: Jonas Olander & Johan Lejdung
'''

def integer_sort(A, k):
'''
Sig: int array[0..n-1], int -> int array[0..n-1]
Pre: The elements of A belongs to the integer interval 0 . . k
Post: A[0..n-1] is a permutation of its original elements in ascending order.
Example: integer_sort([5, 3, 6, 7, 12, 3, 6, 1, 4, 7]), 12) =
[1, 3, 3, 4, 5, 6, 6, 7, 7, 12]
'''

#Declare and initialize an auxiliary array.
aux_list = [0] * (k+1)

"""
Iterate through the input array and for each index,
increment aux_list[value_from_array] by 1.
Where value_from_array = A[index_in_array].
"""
for index_in_array in range(len(A)):
# Invariant: len(A[0:index_in_array]) == sum(aux_list)
# Variant: (len(A)-1) − index_in_array
aux_list[A[index_in_array]] += 1

#Declare and initialize an auxiliary index.
aux_index = 0

"""
Iterate through the auxiliary array and for each v = index_in_aux,
if (n = aux_list[index]) > 0 then store n number of v values in A.
"""
for index_in_aux in range(len(aux_list)):
# Invariant: A[0:aux_index] is a sorted subset of its original elements
# Variant: (len(aux_list)-1) − index_in_aux
value_from_aux = aux_list[index_in_aux]
if value_from_aux > 0:
for index in range(value_from_aux):
# Invariant: A[0:aux_index] is a sorted subset of its original elements
# Variant: (value_from_aux-1) − index
A[aux_index] = index_in_aux
aux_index += 1

return A
```

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.