Counting sort

Animation
COUNTING-SORT(A, B, k) {
  let C[0..k] be a new array

  for (i = 0 to k) {
    C[i] = 0
  }

  for (j = 1 to A.length) {
    C[A[j]] = C[A[j]] + 1
  }

  for (i = 1 to k) {
    C[i] = C[i] + C[i-1]
  }

  for (j = A.length downto 1) {
    B[C[A[j]]] = A[j]
    C[A[j]]= C[A[j]]-1
  }
}

Task 1 Step-wise accumulation of Barray with Counting Sort

Fill in the values of the counting array C before and after its values are accumulated. Then for each step of the last iteration of counting sort, choose the processed element of A and update the values of B and C after each iteration of the final loop in CountingSort(A).

Input array:

What is C before its values are summed up?

What is C before the final loop begins?

Counting sort workflow:

2024 DHBW Karlsruhe Impressum