pramod wrote: > It's hard to understand the code. I will appreciate if you can give > some verbal explanation of these algorithms.
Here is a small example (for the 2nd algorithm). Start with the array: 0:2, 1:2, 2:1, 3:2, 4:1 The number before the : is the entry's original location in the array, and the number after the : gives the entry's value. After the first 'for' loop, the array becomes: 0:-(2+3*0), 1:-(2+3*1), 2:-(1+3*0), 3:-(2+3*2), 4:-(1+3*1) The value of each entry is changed to -(s + 3 * pos), with s being the orginal value of the entry, and pos being the 0-base relative position of the entry among entries with the same value. The first 'for' loop also fills in the 'aux' array with value counts. aux[0] is set to 2, the number of entries of value 1. aux[1] is set to 3, the number of aux entries of value 2. The second 'for' loop changes 'aux' so it contains the index in the sorted array of the first entry of the corresponding value. aux[0} is set to 0, the index of the first location that will contain a 1. aux[1] is set to 2, the index of the first location that will contain a 2. The 'for' loop with a nested 'while' loop sorts the array by executing a single permutation of it (which is why I beleve that the algorithm is O(n)). The outer loop finds entries that have not yet been moved. The inner loop executes cycles of the permutation (in the straight- forward way) and restores the orginal array values. 0:-(2+3*0), 1:-(2+3*1), 2:-(1+3*0), 3:-(2+3*2), 4:-(1+3*1) entry 0 moves to location 2: 0:-(2+3*0), 1:-(2+3*1), 0:2, 3:-(2+3*2), 4:-(1+3*1) entry 2 moves to location 0: 2:1, 1:-(2+3*1), 0:2, 3:-(2+3*2), 4:-(1+3*1) 'for' loop moves to location 1, entry 1 moves to location 3: 2:1, 1:-(2+3*1), 0:2, 1:2, 4:-(1+3*1) entry 3 moves to location 4: 2:1, 1:-(2+3*1), 0:2, 1:2, 3:2 entry 4 moves to location 1: 2:1, 4:1, 0:2, 1:2, 3:2 The 'for' loop exits, and the array is stably sorted. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
