Can You Help To Trace The Quick Sort Algorithm For The Array Having These Elements?


1 Answers

John Nawrocki Profile
John Nawrocki answered
My understanding of quick sort is that you compare an entry in the array to other entries and if the entry being compared to is greater or less than the first entry, depending on whether you want to sort ascending or descending, you exchange their positions.
There are two common methods, one works in place and requires no other storage and the other works with two arrays the greater than array and the less than array.
The method you chose should be predicated on the amount of storage you have to work with. In a small list such as you have, I would use the in place version.
So basically (sorting descending) compare 65 to 70, 70 is greater so exchange the numbers. Since all of these numbers are less than 255 they can fit in a single byte and be exchanged with three machine instructions called "exclusive or". In most assembly languages it is coded as "xor" or "xr".
Since we exchanged 70 and 65, we start over comparing 70 to the entries below it. Now we would be comparing 70 and 75. 75 is greater so exchange again and start comparing 75. When you have gone through the entire list with no exchanges the list is sorted.

Answer Question