Navigation Name Recipes/Basic/Bubble Synopsis Variout styles to write bubble sort. Description Bubble sort is a classical (albeit not the most efficient) technique to sort lists of values. We present here several styles to implement bubble sort. Also see Rascal:Libraries/Prelude/Set/sort for a more efficient library function for sorting. Examples ```module demo::basic::Bubble import List; import IO; // Variations on Bubble sort // sort1: uses list indexing and a for-loop public list[int] sort1(list[int] numbers){ if(size(numbers) > 0){ for(int i <- [0 .. size(numbers)-1]){ if(numbers[i] > numbers[i+1]){ = ; return sort1(numbers); } } } return numbers; } bool isSorted(list[int] lst) = !any(int i <- index(lst), int j <- index(lst), (i < j) && (lst[i] > lst[j])); test bool sorted1a() = isSorted([]); test bool sorted1b() = isSorted([10]); test bool sorted1c() = isSorted([10, 20]); test bool sorted1d() = isSorted([-10, 20, 30]); test bool sorted1e() = !isSorted([10, 20, -30]); // sort2: uses list matching and switch public list[int] sort2(list[int] numbers){ switch(numbers){ case [*int nums1, int p, int q, *int nums2]: if(p > q){ return sort2(nums1 + [q, p] + nums2); } else { fail; } default: return numbers; } } test bool sorted2(list[int] lst) = isSorted(sort2(lst)); // sort3: uses list matching and while public list[int] sort3(list[int] numbers){ while([*int nums1, int p, *int nums2, int q, *int nums3] := numbers && p > q) numbers = nums1 + [q] + nums2 + [p] + nums3; return numbers; } test bool sorted3(list[int] lst) = isSorted(sort3(lst)); // sort4: using recursion instead of iteration, and splicing instead of concat public list[int] sort4([*int nums1, int p, *int nums2, int q, *int nums3]) { if (p > q) return sort4([*nums1, q, *nums2, p, *nums3]); else fail sort4; } public default list[int] sort4(list[int] x) = x; test bool sorted4(list[int] lst) = isSorted(sort4(lst)); // finally, sort 6 inlines the condition into a when: public list[int] sort5([*int nums1, int p, *int nums2, int q, *int nums3]) = sort5([*nums1, q, *nums2, p, *nums3]) when p > q; public default list[int] sort5(list[int] x) = x; test bool sorted5(list[int] lst) = isSorted(sort5(lst)); ``` `sort1` is a classic, imperative style, implementation of bubble sort: it iterates over consecutive pairs of elements and when a not-yet-sorted pair is encountered, the elements are exchanged, and `sort1` is applied recursively to the whole list. `sort2` uses list matching and consists of a switch with two cases: a case matching a list with two consecutive elements that are unsorted. Observe that when the pattern of a case matches, the case as a whole can still fail. a default case. `sort3` also uses list matching but in a more declarative style: as long as there are unsorted elements in the list (possibly with intervening elements), exchange them. `sort4` is identical to `sort3`, except that the shorter `*`-notation for list variables is used and that the type declaration for the the non-list variables has been omitted. `sort5` uses tail recursion to reach a fixed point instead of a while loop. One alternative matches lists with out-of-order elements, while the default alternative returns the list if no out-of-order elements are found. Let's put them to the test: ```rascal>import demo::basic::Bubble; ok rascal>L = [9,8,7,6,5,4,3,2,1]; list[int]: [9,8,7,6,5,4,3,2,1] rascal>sort1(L); |clib-rascal:///demo/basic/Bubble.rsc|(671,1,<23,33>,<23,34>): IndexOutOfBounds(9) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(645,142,<23,7>,<27,4>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at sort1(|clib-rascal:///demo/basic/Bubble.rsc|(758,15,<25,16>,<25,31>)) at ___SCREEN_INSTANCE___(|stdin:///|(0,9,<1,0>,<1,9>)) rascal>sort2(L); list[int]: [1,2,3,4,5,6,7,8,9] rascal>sort3(L); list[int]: [1,2,3,4,5,6,7,8,9] rascal>sort4(L); list[int]: [1,2,3,4,5,6,7,8,9] rascal>sort5(L); list[int]: [1,2,3,4,5,6,7,8,9] rascal>sort6(L); |stdin:///|(0,5,<1,0>,<1,5>): Undeclared variable: sort6 ```  | [New Subconcept] | [Recompile Course] | [Warnings] 2 warnings in this concept Is this page unclear, or have you spotted an error? Please add a comment below and help us to improve it. For all other questions and remarks, visit ask.rascal-mpl.org.