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.

Delete this entry (admin only).