Re: confused on sorting algorithm
- Posted by DerekParnell (admin) Nov 27, 2010
- 1247 views
pls can someone tell me what will be the values of j in this code or better still explain this code to me.am a bit confused in the sorting algorithm as i try to read the program flow manually by myself but i get stuck.i know this is a simple code but am really going nuts and that's the truth
-------------------------------- function simple_sort(sequence x) object temp for i = 1 to length(x) - 1 do for j = i + 1 to length(x) do ? j if compare(x[j],x[i]) < 0 then -- swap x[j], x[i] temp = x[j] x[j] = x[i] x[i] = temp end if end for end for return x end function
This sorting algorithm is a type of bubble sort. It works by going through the items one at a time, making sure that the 'current' item is the lowest of the remaining items. It does this by comparing the current item with each other item in turn, and when it finds an item lower than the current item, it swaps them. This continues until the last item is compared. Then it moves on to the next item after the current item and calls that the new current item.
For example, lets say you have a list of numbers {4,6,2,7,1,7,6,9}
Starting with the current item at position 1, we compare each of the others, swapping them when we find a lower one.
pass 1 : {4,6,2,7,1,7,6,9}
^ ^ -- no swap
pass 1 : {4,6,2,7,1,7,6,9}
^ ^ -- swap required.
pass 1 : {2,6,4,7,1,7,6,9}
^ ^ -- no swap
pass 1 : {2,6,4,7,1,7,6,9}
^ ^ -- swapping
pass 1 : {1,6,4,7,2,7,6,9}
^ ^ -- no swap
pass 1 : {1,6,4,7,2,7,6,9}
^ ^ -- no swap
pass 1 : {1,6,4,7,2,7,6,9}
^ ^ -- no swap
now we shift the current item to be the next item.
pass 2 : {1,6,4,7,2,7,6,9}
^ ^ -- swapping
pass 2 : {1,4,6,7,2,7,6,9}
^ ^ -- no swap
pass 2 : {1,4,6,7,2,7,6,9}
^ ^ -- swapping
pass 2 : {1,2,6,7,4,7,6,9}
^ ^ -- no swap
pass 2 : {1,2,6,7,4,7,6,9}
^ ^ -- no swap
pass 2 : {1,2,6,7,4,7,6,9}
^ ^ -- no swap
pass 3 : {1,2,6,7,4,7,6,9}
^ ^ -- no swap
pass 3 : {1,2,6,7,4,7,6,9}
^ ^ -- swapping
pass 3 : {1,2,4,7,6,7,6,9}
^ ^ -- no swap
pass 3 : {1,2,4,7,6,7,6,9}
^ ^ -- no swap
pass 3 : {1,2,4,7,6,7,6,9}
^ ^ -- no swap
pass 4 : {1,2,4,7,6,7,6,9}
^ ^ -- swapping
pass 4 : {1,2,4,6,7,7,6,9}
^ ^ -- no swap
pass 4 : {1,2,4,6,7,7,6,9}
^ ^ -- no swap
pass 4 : {1,2,4,6,7,7,6,9}
^ ^ -- no swap
pass 5 : {1,2,4,6,7,7,6,9}
^ ^ -- no swap
pass 5 : {1,2,4,6,7,7,6,9}
^ ^ -- swapping
pass 5 : {1,2,4,6,6,7,7,9}
^ ^ -- no swap
pass 6 : {1,2,4,6,6,7,7,9}
^ ^ -- no swap
pass 6 : {1,2,4,6,6,7,7,9}
^ ^ -- no swap
pass 7 : {1,2,4,6,6,7,7,9}
^ ^ -- no swap
