Sorting

Question 1

Counting Sort Input

Answer 1

Array of Integers, Useful if the range of numbers is small

n length list

k amount of unique numbers

Question 2

Counting Sort Time Complexity

Answer 2

O(n + k) because passing over array many times

O(n) if k <= n that means fewer unique numbers than length n

Question 3

Counting Sort Algorithm General

Answer 3

First initialize c[] from 1 to k to 0

Count occurrence of each different number of A[] in C[] length k

Then Each i in C, you need to sum the previous C. Basically c[i] += c[i-1] for i = 2 to k. What this does is correctly adjust the index of each number

Create B[] that is of length n, will be our aux array, just input like this B[C[A[i]]] = A[i]

Then just change each value of A to B

Question 4

Counting Sort Actual Algo

Answer 4

Function CountSort(A, n, k)
1: for i ← 0 to k−1 do C[i] ← 0
2: for i ← 1 to n do C[A[i]] ← C[A[i]] + 1
3: for i ← 1 to k−1 do C[i] ← C[i − 1] + C[i]
4: for i ← n downto 1 do
5: B[C[A[i]]] ← A[i]
6: C[A[i]] ← C[A[i]] − 1
7: for i ← 1 to n do A[i] ← B[i]

Question 5

Radix Sort Input

Answer 5

It is the general version of Counting sort

Works with larger ranges, and an array of objects with a property integer key.

n is length of array

Question 6

Radix Sort Time Complexity

Answer 6

Time complexity is the amount you run the Count sort helper function, which will be O(cn) where c is c times. O(n) if c = O(1);

Question 7

Radix Sort Algorithm

Answer 7

We use the identical version of Counting Sort as a helper function and we just modify by doing .key when we use a key corresponding to A[i].

Treats values as base-n numbers, first sorting by A[i] % n (least significant digit) and then sorting by A[i] / n (most significant digit)

First, we create a new array x[]

Function RadixSort(A, n)
1: for i ← 1 to n do
2: X[i].key ← A[i] mod n
3: X[i].data ← A[i]
4: CountSort(X, n, n)
5: for i ← 1 to n do
6: X[i].key ← X[i].data div n
7: CountSort(X, n, n)
8: for i ← 1 to n do A[i] ← X[i].data

Function CountSort(A, n, k)
1: for i ← 0 to k−1 do C[i] ← 0
2: for i ← 1 to n do
C[A[i].key] ← C[A[i].key] + 1
3: for i ← 1 to k−1 do C[i] ← C[i − 1] + C[i]
4: for i ← n downto 1 do
5: B[C[A[i].key]] ← A[i]
6: C[A[i].key] ← C[A[i].key] − 1
7: for i ← 1 to n do A[i] ← B[i]

Question 8

Why Does Radix Sorting Work

Answer 8

It works because we are sorting based on each digit, least sig to most sig

EX:
15, 06, 25, 33, 36, 47, 52, 70

Sort 1:
70, 52, 33, 15, 25, 06, 36, 47

Sort 2:
06, 15, 25, 33, 36, 47, 52, 70