OpenEuphoria

2. Re: confused on sorting algorithm

• Posted by DerekParnell (admin) Nov 27, 2010
• 1346 views

--------------------------------
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 

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 

4. Re: confused on sorting algorithm

• Posted by manorchurch Nov 30, 2010
• 1242 views

/*cynical humor mode on*/

It's the dream of every programmer to, someday, get to explain sorting to someone who's confused by a cryptic sort algorithm. And to intone, "Basically, every sort is a variation on the Bubble sort." Derek didn't do that, probably because he knew there would be loud screams of "The Shell Sort is NOT a bubble sort!"

/*cynical humor mode off*/