TRAKLA2 - Counting methods for sorting

Counting methods for sorting

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions Sort the following array of key values by means of counting sort. Some additional problems. Click an element in the Input array. This makes the corresponding key value visible. The visible key values can be drag and dropped either into Auxliary Table or Output. Each time an element is drag & dropped into Auxliary Table, the number of corresponding elements is increased by one. The result is the distribution of the key values. After this, the items in Auxliary Table can be dragged and dropped on top of each other in order to add a value to another one. The idea is to calculate the cumulative distribution of the key values. This cumulative distribution can be used to determine the correct Output position for each key value in the Input array. Each time an element is added to Output, the corresponding item in Auxliary Table is decreased by one.
Counting Sort 1. for (j=0; j<M; j++) 2. aux[j] = 0; 3. for (i=0; i<N; i++) 4. aux[input[i]]++; 5. for (j=1; j<M; j++) 6. aux[j] += aux[j-1]; 7. for (i=N-1; i>=0; i--) { 8. output[aux[input[i]]] = input[i]; 9. aux[input[i]]--; 10. }