Iterative Sorting

# TO-DO: Complete the selection_sort() function below 
def selection_sort( arr ):
    # loop through n-1 elements
    for i in range(0, len(arr) - 1):
        smallest_index = i

        # TO-DO: find next smallest element
        # (hint, can do in 3 loc) 
        for j in range(i+1, len(arr)):
            if arr[j] < arr[smallest_index]:
                smallest_index = j

        # TO-DO: swap
        arr[i], arr[smallest_index] = arr[smallest_index], arr[i]

    return arr

# TO-DO:  implement the Bubble Sort function below
def bubble_sort( arr ):

    # Compare two and swap if a > b
    for i in range(0, len(arr)-1):
        for j in range(i+1, len(arr)):
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]

    return arr

# STRETCH: implement the Count Sort function below
def count_sort( arr, maximum=-1 ):
    hash_length = 0

    for i in range(0, len(arr)):
        # If any negative numbers, returns error
        if arr[i] < 0:
            return "Error, negative numbers not allowed in Count Sort"
        # Find highest number in arr
        if arr[i] > hash_length:
            hash_length = arr[i]
        
    # Create hash table with maximum arr values as keys, set to 0
    hash = { i: 0 for i in range(0, hash_length+1)}

    # In hash, increase count of each instance of i in arr
    for i in range(0, len(arr)):
        hash[arr[i]] += 1
    
    # Adds two instance totals to find indices of each element in arr
    for i in range(1, len(hash)):
        hash[i] = hash[i] + hash[i-1]
    
    sorted_arr = [None] * len(arr)
    for i in range(0, len(arr)):
        # Places arr[i] instance into correct index of sorted_arr
        sorted_arr[hash[arr[i]]-1] = arr[i]
        # Decreases i's index in hash
        hash[arr[i]] = hash[arr[i]]-1

    return sorted_arr

Last updated