A less slow bubble sort

There’s not much that can be done to make a bubble sort fast, but it can be an interesting exercise to try and make it as “least slow” as possible. :slight_smile:

The algorithm I learned years ago involved cycling repeatedly through the list, comparing adjacent items and swapping them when necessary. The sort was complete when a clear run took place with no swaps. But StefanK posted a version in the OS X forum the other day (I don’t know if it was his own or somebody else’s) which makes use of the fact that the “highest” value in the list is bound to end up in the last slot during the first cycle. This item doesn’t need to be included in the next cycle and in fact each subsequent cycle can be one item shorter than the one preceding it. This reduces the total number of comparisons done over the course of the sort and the process is complete when there are less than two items left to consider.

on bubblesort(array)
	repeat with i from length of array to 2 by -1 --> go backwards
		repeat with j from 1 to i - 1 --> go forwards
			tell array
				if item j > item (j + 1) then
					set {item j, item (j + 1)} to {item (j + 1), item j} -- swap
				end if
			end tell
		end repeat
	end repeat
	return array
end bubblesort

However, on my old 400 MHz PowerBook, this takes 268.43 seconds to sort only 500 random integers! But the time can be reduced to 5.64 seconds with the coding below. Besides using the old referencing-via-script-object trick, it dispenses with the setting of multiple items by list “ which is time consuming “ and assigns the current values to variables so that they’re only read from the list once. At the end of each iteration of the inner repeat, the higher value of the current pair is preserved in the variable ‘a’ so that it doesn’t need to be read again from the list on the next iteration.

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

13th September 2010: I’ve uploaded a new version of this script with more flexible range parameters, as part of a collection, to ScriptBuilders.

Of course it’s somebody else’s. My math knowledge is too bad.
I just took a formula from wherever and translated it into AppleScript
:slight_smile:

:smiley:

I invented a sort method in February “ though I’m sure I’m not the first person to have thought of it. It finds the lowest and highest values in the list (or range thereof) and swaps them with the leftmost and rightmost values. Then it decreases the range at both ends and goes again, continuing until the ends meet in the middle. I call it a “squeeze sort” “ though since it’s a bit like a bubble sort without the bubbles, it might also qualify as a “fart sort”. :wink: It’s quite a bit faster than a bubble sort, but still a lot slower than a merge sort or quicksort:

on squeezeSort(theList, l, r) -- Sort items l thru r of theList.
	script o
		property lst : theList
	end script
	
	repeat (r - l + 1) div 2 times -- while (l < r)
		-- Initialise the 'lowest' and 'highest' pointers to the leftmost item in this range.
		set lowest to item l of o's lst
		set loPos to l
		set highest to lowest
		set hiPos to loPos
		-- Also get the leftmost and rightmost values into variables to avoid possible confusion during the swap.
		set leftmost to lowest
		set rightmost to item r of o's lst
		
		-- Find the lowest and highest values in the range.
		repeat with i from l + 1 to r
			set a to item i of o's lst
			if (a < lowest) then
				set lowest to a
				set loPos to i
			else if (a > highest) then
				set highest to a
				set hiPos to i
			end if
		end repeat
		
		-- Swap the lowest and highest values with the leftmost and rightmost values respectively:
		-- Overwrite the lowest and highest positions with the leftmost and rightmost values.
		set item loPos of o's lst to leftmost
		set item hiPos of o's lst to rightmost
		-- Overwrite the leftmost and rightmost positions with the lowest and highest values.
		set item l of o's lst to lowest
		set item r of o's lst to highest
		
		-- Narrow the range for the next iteration.
		set l to l + 1
		set r to r - 1
	end repeat
end squeezeSort

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

squeezeSort(l, 1, (count l))
l

13th September 2010: I’ve uploaded a new version of this script with a bug fix and more flexible range parameters, as part of a collection, to ScriptBuilders.

I was searching for a way to sort an array of numbers and found this thread.

however it doesn’t seem to work for may array ??? any help would be greatly appreciated

here is my array


set myArray to {36, 1189, 2342, 37, 1190, 2343, 38, 1191, 2344, 39, 1192, 2345, 40, 1193, 2346, 41, 1194, 2347, 42, 1195, 2348, 43, 1196, 2349, 44, 1197, 2350, 45, 1198, 2351, 46, 1199, 2352, 47, 1200, 2353, 48, 1201, 2354, 49, 1202, 2355, 50, 1203, 2356, 51, 1204, 2357, 52, 1205, 2358, 53, 1206, 2359, 54, 1207, 2360, 55, 1208, 2361, 56, 1209, 2362, 57, 1210, 2363, 58, 1211, 2364, 59, 1212, 2365, 60, 1213, 2366, 61, 1214, 2367, 62, 1215, 2368, 63, 1216, 2369, 64, 1217, 2370, 65, 1218, 2371, 66, 1219, 2372, 67, 1220, 2373, 68, 1221, 2374, 69, 1222, 2375, 70, 1223, 2376, 71, 1224, 2377, 72, 1225, 2378, 73, 1226, 2379, 74, 1227, 2380, 75, 1228, 2381, 76, 1229, 2382, 77, 1230, 2383, 78, 1231, 2384, 79, 1232, 2385, 80, 1233, 2386, 81, 1234, 2387, 82, 1235, 2388, 83, 1236, 2389, 84, 1237, 2390, 85, 1238, 2391, 86, 1239, 2392, 87, 1240, 2393, 88, 1241, 2394, 89, 1242, 2395, 90, 1243, 2396, 91, 1244, 2397, 92, 1245, 2398, 93, 1246, 2399, 94, 1247, 2400, 95, 1248, 2401, 96, 1249, 2402, 97, 1250, 2403, 98, 1251, 2404, 99, 1252, 2405, 100, 1253, 2406, 101, 1254, 2407, 102, 1255, 2408, 103, 1256, 2409, 104, 1257, 2410, 105, 1258, 2411, 106, 1259, 2412, 107, 1260, 2413, 108, 1261, 2414, 109, 1262, 2415, 110, 1263, 2416, 111, 1264, 2417, 112, 1265, 2418, 113, 1266, 2419, 114, 1267, 2420, 115, 1268, 2421, 116, 1269, 2422, 117, 1270, 2423, 118, 1271, 2424, 119, 1272, 2425, 120, 1273, 2426, 121, 1274, 2427, 122, 1275, 2428, 123, 1276, 2429, 124, 1277, 2430, 125, 1278, 2431, 126, 1279, 2432, 127, 1280, 2433, 128, 1281, 2434, 129, 1282, 2435, 130, 1283, 2436, 131, 1284, 2437, 132, 1285, 2438, 133, 1286, 2439, 134, 1287, 2440, 135, 1288, 2441, 136, 1289, 2442, 137, 1290, 2443, 138, 1291, 2444, 139, 1292, 2445, 140, 1293, 2446, 141, 1294, 2447, 142, 1295, 2448, 143, 1296, 2449, 144, 1297, 2450, 145, 1298, 2451, 146, 1299, 2452, 147, 1300, 2453, 148, 1301, 2454, 149, 1302, 2455, 150, 1303, 2456, 151, 1304, 2457, 152, 1305, 2458, 153, 1306, 2459, 154, 1307, 2460, 155, 1308, 2461, 156, 1309, 2462, 157, 1310, 2463, 158, 1311, 2464, 159, 1312, 2465, 160, 1313, 2466, 161, 1314, 2467, 162, 1315, 2468, 163, 1316, 2469, 164, 1317, 2470, 165, 1318, 2471, 166, 1319, 2472, 167, 1320, 2473, 168, 1321, 2474, 169, 1322, 2475, 170, 1323, 2476, 171, 1324, 2477, 172, 1325, 2478, 173, 1326, 2479, 174, 1327, 2480, 175, 1328, 2481, 176, 1329, 2482, 177, 1330, 2483, 178, 1331, 2484, 179, 1332, 2485, 180, 1333, 2486}

thanks again
mm

edit: sorry I’m not sure what is wrong here but your code is of course fine

Hi,

your array is actually a list and Nigel’s squeezeSort routine works perfectly

squeezeSort(myArray, 1, count myArray)
myArray --> {36, 37, 38., 2485, 2486}

Yes. mcgrailm hasn’t said in what way it’s not working for him, but people are sometimes confused by the fact that my sort implementations sort the actual lists passed to them; they don’t return sorted copies. (This is helps with the speed.) Additionally, since squeezeSort is almost fast enough to be useful, I’ve embellished it with the ability to sort just a certain range of the target list. So it needs three parameters: the list itself and the indices of the first and last items in the range. To have the entire list sorted, the indices need to be 1 and the length of the list.

Hope that clears things up a little. :slight_smile: