Please help me understand this script

This a Bubble Sort script posted on this forum. I looked up Wiki’s Bubble sort and now have an understanding on how it is performed. I am however, unable to understand the script.

Can anyone explain it to me stop-by-step and in detail please. You may e-mail me directly if you sish.

Regards,
Tommy


set the composer_list to {“Ellington”, “Copland”, “Bach”, “Mozart”, “Chopin”}
bubbleSort(the composer_list)

on bubbleSort(theList)
– defining an internal script makes for faster run times!

script bs
property alist : theList
end script

set theCount to length of bs’s alist
if theCount < 2 then return bs’s alist
repeat with indexA from theCount to 1 by -1
repeat with indexB from 1 to indexA - 1
if item indexB of bs’s alist > item (indexB + 1) of bs’s alist then
set temp to item indexB of bs’s alist
set item indexB of bs’s alist to item (indexB + 1) of bs’s alist
set item (indexB + 1) of bs’s alist to temp
end if
end repeat
end repeat
return bs’s alist
end bubbleSort

Hi,

script bs

is a script object which will be created in the handler to hold the list for speed reasons

You can read details about script objects here

Hi Stefan,

Thank you for the link below. I do understand the scripting object, but what I don’t understand is how the Bubble Sorting code works.

Regards,
Tommy

Well, I think it does something like this: (My English is not so good, but I’m going to try)

It loops with every item of the list thru all other items.

So if you have 6 items in a list, you loop the list once for item 1, once for item 2, once for item 3, once for item 4, once for item 5 and once for item 6.

When looping with one of the six items, it compares the item with every other item. If your if-statement (which defines the order of the new list) returns true, the looped item just switches places with the other item.

Here’s the code again, but commented:

on bubbleSort(theList)
	-- defining an internal script makes for faster run times!
	
	script bs
		property alist : theList
	end script
	
	set theCount to length of bs's alist
	if theCount < 2 then return bs's alist
	
	
	repeat with indexA from theCount to 1 by -1 -- repeat with every item in the list
		repeat with indexB from 1 to indexA - 1 -- repeat with every item of the list for comperision 
			if item indexB of bs's alist > item (indexB + 1) of bs's alist then -- if A is bigger then B
				set temp to item indexB of bs's alist -- store the current item of the place in a variable
				set item indexB of bs's alist to item (indexB + 1) of bs's alist -- override the current item of the place with the new item
				set item (indexB + 1) of bs's alist to temp -- override the looped item with the one that was earlier placed in the variable
			end if
		end repeat
	end repeat
	return bs's alist
end bubbleSort

Hope it helps,
ief2

Maybe a little video demonstrating the Bubble Sort would help.

Description of a Bubble Sort

Compare adjacent elements and swap them if they are out of order (this is the if statement). This pair-wise compare-and-swap operation progresses from the beginning of the list to the end of the list processing each pair of elements (this is the repeat with indexB . loop). If the first element is larger, it is swapped with the second element (where it will be used as the first element of the next compare-and-swap operation).

Once one pass has been completed the largest element is now at the end of the list (the iterated compare-and-swap operation always ˜bubbles’ the largest element to the end of the list). So the last element is now “sorted”. Make another pass starting at the beginning of the list, but stop before processing the last element (since we know the last element is already “sorted”; this is the repeat with indexA . loop).

Make successive passes until no swaps are made, or stop after making a pass that processes only the first two elements (all the rest are sorted, this last pass sorts the first two elements, so now the whole list is sorted).

Depending on the nature of the compare operation, the smallest element (instead of the largest) will ˜bubble’ to the end (descending sort). Or by starting at the end and working towards the beginning (with each pass leaving off one more element from the beginning), the smallest/largest element will ˜bubble’ to the beginning of the list.

To complement ief2’s explanation (and Chris’s now, I see :)):

The Bubble sort algorithm is so called because the visual image is of values “bubbling” up through the list to their final positions, like bubbles in water. The script posted is an ascending sort, arranging the values with the lowest at the beginning of the list and the highest at the end.

The inner repeat loop compares the value in each list position with the value in the next position up. If the values aren’t in the right order with respect to each other, they’re swapped round. The repeat then moves one position up the list and does the same again. The higher position at each comparison becomes the lower position for the next, so it’s the higher value in each case that goes on to be compared with the next value in the list.

When the repeat reaches the end of the list, the highest value in the list will have “bubbled” up to the end position. The outer repeat then limits the inner repeat’s sort range to exclude the end position and sets it off again. This time, the inner repeat bubbles the second-highest value in the list to the penultimate position. The process continues with an ever-diminishing sort range until there’s nothing left to sort.

If you change the variable name ‘indexA’ to something like ‘sortLimit’ and ‘indexB’ to, say, ‘bubblePoint’, the script should be more self-explanatory.

The sort would still work if the inner repeat were allowed to iterate to the end of the list every time, but not bothering with the already-sorted items makes the process a little less slow.

Another possible optimisation (which I’ve implemented here) is not to put the higher value from each comparison back into the list every time, since it only has to be got out again for the next comparison. It’s faster just to switch variables ” and then only if necessary!

Thanks to everyone who replied to my post.

When you think about it, a bubble sort woud be much faster without the bubbles! If the idea’s just to get the next-highest value into the next highest list position, there’s no point in moving most of the other values at all. Simply locate the next highest remaining value and swap it with the current incumbent of the position where you want it to go. This is so blindingly obvious in retrospect, I’m sure it’s been thought of before!

set the composer_list to {"Ellington", "Copland", "Bach", "Mozart", "Chopin"}
stillSort(the composer_list)

on stillSort(theList) -- Bubble sort without the bubbles.
	-- defining an internal script makes for faster run times!
	
	script bs
		property alist : theList
	end script
	
	set theCount to length of bs's alist
	if (theCount < 2) then return bs's alist
	repeat with sortLimit from theCount to 2 by -1
		set hiVal to beginning of bs's alist
		set hiPos to 1
		repeat with thisPos from 2 to sortLimit
			set thisVal to item thisPos of bs's alist
			if (thisVal > hiVal) then
				set hiVal to thisVal
				set hiPos to thisPos
			end if
		end repeat
		set item hiPos of bs's alist to item sortLimit of bs's alist
		set item sortLimit of bs's alist to hiVal
	end repeat
	
	return bs's alist
end stillSort

I believe this is the selection sort algorithm (although the visualizations/demos on that Wikipedia page sort from the beginning of the list instead of the end). And indeed, the comparison section of the selection sort article says that it does usually outperform the bubble sort, but it is still not the fastest of the O(N²) algorithms (loosely, those algorithms that must make ˜on the order of’ N² comparisons to sort a list of length N).

A notable feature of the selection sort is that it makes at most N swaps (O(N) swaps), while other algorithms often make many more (O(N²) swaps). This makes it particularly useful in situations where writes are much more ˜expensive’ than reads and comparisons (e.g. flash memory).

Sorting is a deceptively detailed problem area. Depending on the characteristics of the data, different algorithms can produce dramatically different results (because they use different amounts of extra memory, use different numbers of swaps, comparisons, or other operations on the sequence structure being sorted, etc.).

Thanks, Chris. That’s an interesting Wikipedia article. It’s sorta gratifying to know that I’ve independently invented two recognised sort algorithms! The selection sort (stillSort() above) and the cocktail sort (squeezeSort() here).