Bubble Sort

64,596 Views

Report

• # A simple sorting algorithm that steps through the array element by element,
  # comparing and swapping two elements if they're not in order.
  # When no swaps are done, then the list is sorted.
  BubbleSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<transacts>:[]t=
      Length:int = Array.Length
      var OrderedArray:[]t = Array
  
      # Iterate through the whole array.
      for:
          FirstIndex := 0..Length - 1
      do:
          # Tracking if any swaps were performed.
          var DidSwap:logic = false
  
          # Go element by element and compare adjacent elements.
          # Largest elements will "bubble up" to the end first,
          # so can ignore as many elements at the end as we've already checked.
          for:
              SecondIndex := 0..Length - FirstIndex - 1
              not Compare[OrderedArray[SecondIndex], OrderedArray[SecondIndex + 1]]
              ArrayWithSwappedElements := OrderedArray.Swap[SecondIndex, SecondIndex + 1]
          do:
              set OrderedArray = ArrayWithSwappedElements
              set DidSwap = true