CODEWITHSUNDEEP
algorithmsortingpseudocode
user2827137
user2827137

Reputation: 51

Pseudocode for comparison counting algorithm

I'm working on a homework question for my algorithms class and I'm boggled by how this particular algorithm works. I already found the answer online so I'm not looking for answers, just some help working through the code step by step. From what I can figure out so far, the algorithm accepts an array of an unspecified length and through multiple iterations, sorts the numbers by comparing an individual element with smaller elements within the array. At the end of the iterations, it assigns each element a location index that specifies what order the elements should be arranged in to be in a non-decreasing order. But what I cannot figure out is how the second for-do loop start off the iteration after the first loop is completed? Any assistance would be greatly appreciated

Question: Consider the algorithm for the sorting problem that sorts an array by counting, for each of its elements, the number of smaller elements and then uses this information to put the element in its appropriate position in the sorted array. Sort the following list of numbers, (60, 35, 81, 98, 14, 47):

Algorithm ComparisonCountingSort(A[0..n − 1], S[0..n − 1])
//Sorts an array by comparison counting
//Input: Array A[0..n − 1] of orderable values
//Output: Array S[0..n − 1] of A’s elements sorted in nondecreasing order

for i ← 0 to n − 1 do
     Count[i] ← 0

for i ← 0 to n − 2 do
     for j ← i + 1 to n − 1 do
          if A[i] < A[j]
               Count[j] ← Count[j] + 1
          else
               Count[i] ← Count[i] + 1

for i ← 0 to n − 1 do
     S[Count[i]] ← A[i]

return S

Upvotes: 2

Views: 3966

Answers (2)

user2827137
user2827137

Reputation: 51

thanks for any assistance that was given but I was able to figure it out after working on it for awhile. In laymen's terms, you start with the first column which is the current i, and compare it to each column following it (which would be j in the comparison), and if i is greater than j, then i gets a 1. If j is higher, j gets a 1. After the first row which consists of all zeroes, the second row is iterated. Using 60 as i, you compare it to 35 which is the current j, since 60 is greater than 35, 60 gets a 1 (tally mark if you will). Then you compare 60 to 81 since that becomes the new j. Since 81 is higher than 60, 81 gets the tally mark. This continues on until the rest of the row is finished. In the next iteration, the next column becomes the new i, and the following will become the new j one after another. Rinse and repeat until all columns and rows are finished and you have a new index value for each element which you then is put in order.

Upvotes: 0

Pankrates
Pankrates

Reputation: 3094

The crux of this sorting algorithm is the realization that if a number x in the array has exactly n elements in the array that are smaller, then in the sorted array it should be the n'th element (in a zero-indexed array).

So what the algorithm wants to do is check for each element how many other elements are smaller. But then you end up checking each pair twice which is unnecessary. The second loop is built in such a way that each pair is compared exactly once.

The second loop, which is the double for loop can be visualized as follows, for the case where the length N is 4:

1st outer loop   | i ->  [0]
                 | j ->  [1] [2] [3]

2nd outer loop   | i ->  [1]
                 | j ->  [2] [3]

3rd outer loop   | i ->  [2]
                 | j ->  [3]

Here i and j are your loop iterators and the values between brackets are the values of the index they take on. Now you can clearly see that with this construction each pair is compared once

Upvotes: 1

Related Questions