Search

mardi 21 février 2017

Sort: Bubble sort

Context

There are multiple ways to sort an array in computer theory. One of them is called Bubble sort.
This algorithm is clearly not the best one, though it's quite easy to implement:

  • Consider 2 adjacent cells
  • Compare values
    • If second is smaller, then swap the 2 values
  • Move to next pair of 2 cells (the one that includes the second element of my current pair)
  • When reaching end of array, redo the whole loop as long as at least one swap has been made (sort is not over)
The name comes from the behaviour of biggest / smaller elements (according to the sort direction) : they are pushed to the top of the list like bubbles in liquids.

Let's write our own bubble sort implementation

Initial state

  • Memory: 0 0 [array] 0 0 0 0 0 0 ... where array is an array of nullable integers (2 cells per item, one set to 1 and second set to the value)
  • Cursor: just after array
  • Input: any

Process

  • Set a loop indicator to 1 and start a loop
    • Reset loop indicator
    • Go to last two cells
      • Move and copy the second cell to the right (leave enough space for comparison)
      • Copy first cell value
      • Compare first and second value copies
      • If second is smaller than first
        • Swap the 2 values
        • RESET the loop indicator and set to 1. Reset is mandatory, otherwise (simply adding 1) will fail if there are 256 changes (loop indicator will then be 0). Here, instead, let's just have the indicator reset and set to 1
      • Move to the next pair if any
    • Move array back to its original location
    • Go back to loop indicator and loop if needed

Code - try it

set loop indicator and loop
>>>>>>>+[
  reset indicator and go to last 2 cells
  -<<<<<<<<<<<
  while there are 2 cells to compare
  [
    copy / move second cell
    >>->[->+>>>>>+<<<<<<]>>>>>+<<<<[-<+>]
    copy first cell
    <<<[->+>>+<<<]>[-<+>]
    compare 2 values
    >>>+<<[->[->]>[<<[-]>>->>]<<+<<]>[[-]<+>]>-<<
    [-
      second is smaller : swap
      temporarily move first cell
      <<[->+<]
      move first cell
      >>>>>>>>[-<<<<<<<<+>>>>>>>>]
      reset and set loop indicator
      >[>>]>[-]+<<<[<<]<<<<
      move second value
      [->>>>>>>+<<<<<<<]
      go back to position before if
      >
    ]
    move to last 2 cells and loop
    <<<<<
  ]
  move array back to initial location
  >>>>>>>>>>[[-<<<<<<+>>>>>>]>[-<<<<<<+>>>>>>]>]
  go to loop indicator and loop
  >
]

Final state

  • Memory: 0 0 [array] 0 0 0 0 0 0
  • Cursor: 6 cells after the array
  • Input: unchanged
  • Output: unchanged

Aucun commentaire:

Enregistrer un commentaire