Interview Question #2: Counting Sort

Kyu Hwan Choi·2022년 5월 15일
0

Interview Question

목록 보기
2/2
post-thumbnail

Problem:

You are given with an unsorted_ints list and max_int_limit of the list. Sort the int list in time O(n).
We can treat the max_int_limit as a constant. By doing this, we are assuming that the max_int_limit should not be volatile and be fixed for whatever values we have in the unsorted_ints list.


Process:

We will be using a counting sort.
1. We will count the unsorted_ints list in a seperate list
2. We will traverse through it in inorder step to retrieve values from the lowest int. This should automatically sort out the list.


Solution:

Attempt #1: Counting Sort

  • Time Complexity: O(n)
  • Space Complexity: O(n)

How it works

  1. We will create a int_count list with a length of max_int_limit in order to count the ints in the unsorted_ints list.
  2. We will iterate over the unsorted_ints list to input the values in to int_count list. The index will be the int and the int_count[int] value will be the # of int in the list.
  3. We will reversely iterate over the int_count list to retrieve int from the highest int in int_count list. We will append int multiple times according to the int_count[int] value in case there was a repeated score. This should give us a sorted int list.

Code

def sort_ints(unsorted_ints, max_int_limit):

    # Sort the ints in O(n) time
    int_count = [0] * (max_int_limit+1)
    
    # Initialize final sorted list
    sorted_ints = []
    
    # Populate int_count
    for int in unsorted_ints:
        int_count[int] += 1
    
    # Traversing through int_count to retrieve ints in inorder
    for int in range(max_int_limit+1, 0, -1):
        
        # Iterative over number of ints in the list
        for repeat in range(int_count[int-1]):
            # Add the int to sorted list
            sorted_ints.append(int-1)

    return sorted_ints

Time Complexity Analysis
Assume that n is the number of ints in unsorted_ints list and k is the max_int_limit

  1. Creating int_count list - O(n)

  2. Iterating over int_count list and mutiple iteration over repeated number - O(n+k)

However, if we consider O(k) to be constant, then the time complexity of this function will be O(n)O(n)

Space Complexity Analysis
The int_count list will take up O(k) and the sorted_int_list will take up O(n). Therefore, it will be O(n+k). Yet again, if we consider O(k) to be constant, then the space complexity of this function will be O(k)O(k).

Limitations
1. Because we tried to reduce the runtime of this function, we had to use up extra O(k). This takes up a lot of space. We could probably reduce this by sacrificing a bit of our time efficiency.

0개의 댓글