Basic Bubble Sort

Scripting Forums Code Exchange
,
#1

Figured I’d post this for the heck of it
This is how you accomplish your really basic bubble sort

property SortedAlready : false
property Temp : missing value
property Finish : missing value

set myList to {"156789", "12345", "234567", "23567", "122334"}


Bubble(myList)
return myList
on Bubble(theList)
	
	
	set Finish to (count of theList) as integer
	repeat until SortedAlready or Finish = 1
		set SortedAlready to true
		repeat with i from 1 to (Finish - 1)
			if item i of theList > item (i + 1) of theList then
				set SortedAlready to false
				set Temp to item i of theList
				set item i of theList to item (i + 1) of theList
				set item (i + 1) of theList to Temp
			end if
		end repeat
		set Finish to Finish - 1
	end repeat
end Bubble
#2

coercion police ;): the result of count is always an integer!

count i[/i] Return the number of elements of an object (from Standard Suite)
FUNCTION SYNTAX
set theResult to count reference ¬
each type class
RESULT
integer the number of elements

#3

speed police ;): bubble sorts are really slow!

On a 400 MHz PowerBook, the above sort takes four minutes and six seconds to sort 500 random integers! On the first run, at least.

property police ;): properties and globals retain their values between runs!

SortedAlready needs to be reset to false on every run, otherwise the handler will terminate almost immediately while testing the outer repeat conditions.

The below bubble sort takes just six seconds on the 400 MHz PowerBook :cool:, but that’s still a crawl in comparison with other methods:

on bubblesort(theList)
	script o
		property lst : theList
	end script
	
	repeat with i from (count theList) to 2 by -1
		set a to beginning of o's lst
		repeat with j from 2 to i
			set b to item j of o's lst
			if (a > b) then
				set item (j - 1) of o's lst to b
				set item j of o's lst to a
			else
				set a to b
			end if
		end repeat
	end repeat
end bubblesort

set l to {}
repeat 500 times
	set end of my l to random number 500
end repeat

set t to (GetMilliSec)
bubblesort(l)
l
((GetMilliSec) - t) / 1000
#4

thanks for the update guys :smiley: