
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


A   bubble   sort is generally considered to be the simplest sorting algorithm.

A   bubble   sort is also known as a   sinking   sort.



Because of its simplicity and ease of visualization, it is often taught in introductory computer science courses.

Because of its abysmal O(n2) performance, it is not used often for large (or even medium-sized) datasets.

The bubble sort works by passing sequentially over a list, comparing each value to the one immediately after it.   If the first value is greater than the second, their positions are switched.   Over a number of passes, at most equal to the number of elements in the list, all of the values drift into their correct positions (large values "bubble" rapidly toward the end, pushing others down around them).  
Because each pass finds the maximum item and puts it at the end, the portion of the list to be sorted can be reduced at each pass.  
A boolean variable is used to track whether any changes have been made in the current pass; when a pass completes without changing anything, the algorithm exits.

This can be expressed in pseudo-code as follows (assuming 1-based indexing):

repeat
    if itemCount <= 1
        return
    hasChanged := false
    decrement itemCount
    repeat with index from 1 to itemCount
        if (item at index) > (item at (index + 1))
            swap (item at index) with (item at (index + 1))
            hasChanged := true
until hasChanged = false



Task

Sort an array of elements using the bubble sort algorithm.   The elements must have a total order and the index of the array can be of any discrete type.   For languages where this is not possible, sort an array of integers.



References

 The article on Wikipedia.
 Dance interpretation.


 
  [Bubble sort demo for Rosetta Code website]
  [EDSAC program. Initial Orders 2]
 
  [Sorts a list of double-word integers.
   List must be loaded at an even address.
   First item gives number of items to follow.
   Address of list is placed in location 49.
   List can then be referred to with code letter L.]
          T49K
          P300F [<---------- address of list here]
 
  [Subroutine R2, reads positive integers during input of orders.
   Items separated by F; list ends with #TZ.]
  GKT20FVDL8FA40DUDTFI40FA40FS39FG@S2FG23FA5@T5@E4@E13Z
 
  [Tell R2 where to store integers it reads from tape.]
        T    #L  ['T m D' in documentation, but this also works]
 
  [Lists of integers, comment out all except one]
  [10 integers from digits of pi]
  10F314159F265358F979323F846264F338327F950288F419716F939937F510582F097494#TZ
 
  [32 integers from digits of e ]
  [32F
   27182818F28459045F23536028F74713526F62497757F24709369F99595749F66967627F
   72407663F03535475F94571382F17852516F64274274F66391932F00305992F18174135F
   96629043F57290033F42952605F95630738F13232862F79434907F63233829F88075319F
   52510190F11573834F18793070F21540891F49934884F16750924F47614606F68082264#TZ]
 
  [Library subroutine P7, prints positive integer at 0D.
   35 locations; load at aneven address.]
        T  56 K
  GKA3FT26@H28#@NDYFLDT4DS27@TFH8@S8@T1FV4DAFG31@SFLDUFOFFFSFL4F
  T4DA1FA27@G11@XFT28#ZPFT27ZP1024FP610D@524D!FO30@SFL8FE22@
 
  [The EDSAC code below implements the following Pascal program,
   where the integers to be sorted are in a 1-based array x.
   Since the assembler used (EdsacPC by Martin Campbell-Kelly)
   doesn't allow square brackets inside comments, they are
   replaced here by curly brackets.]
  [   
    swapped := true;
    j := n; // number of items 
    while (swapped and (j >= 2)) do begin
      swapped := false;
      for i := 1 to j - 1 do begin
        // Using temp in the comparison makes the EDSAC code a bit simpler
        temp := x{i};
        if (x{i + 1} < temp) then begin
          x{i} := x{i + 1};
          x{i + 1} := temp;
          swapped := true;
        end;
      end;
      dec(j);
    end;
  ]
    [Main routine]
        T 100 K
        G     K
    [0] P F P F [double-word temporary store]
    [2] P     F [flag for swapped, >= 0 if true, < 0 if false]
    [3] P     F ['A' order for x{j}; implicitly defines j]
    [4] P   2 F [to change list index by 1, i.e.change address by 2]
    [5] A    #L ['A' order for number of items]
    [6] A   2#L ['A' order for x{1}]
    [7] A   4#L ['A' order for x{2}]
    [8] I2046 F [add to convert 'A' order to 'T' and dec address by 2]
    [9] K4096 F [(1) minimum 17-bit value (2) teleprinter null]
   [10] P     D [constant 1, used in printing]
   [11] #     F [figure shift]
   [12] &     F [line feed]
   [13] @     F [carriage return]
 
       [Enter here with acc = 0]
   [14] T   2 @ [swapped := true]
        A     L [get count, n in Pascal program above]
        L   1 F [times 4 by shifting]
        A   5 @ [make 'A' order for x{n}; initializes j := n]
 
       [Start 'while' loop of Pascal program.
        Here acc = 'A' order for x{j}]
   [18] U   3 @ [update j]
        S   7 @ [subtract 'A' order for x{2}]
        G  56 @ [if j < 2 then done]
        T     F [acc := 0]
        A   2 @ [test for swapped, acc >= 0 if so]
        G  56 @ [if not swapped then done]
        A   9 @ [change acc from >= 0 to < 0]
        T   2 @ [swapped := false until swap occurs]
        A   6 @ ['A' order for x{1}; initializes i := 1]
 
       [Start 'for' loop of Pascal program.
        Here acc = 'A' order for x{i}]
   [27] U  36 @ [store order]
        S   3 @ [subtract 'A' order for x{j}]
        E  52 @ [out of 'for' loop if i >= j]
        T     F [clear acc]
        A  36 @ [load 'A' order for x{i}]
        A   4 @ [inc address by 2]
        U  38 @ [plant 'A' order for x{i + 1}]
        A   8 @ ['A' to 'T', and dec address by 2]
        T  42 @ [plant 'T' order for x{i}]
   [36] A    #L [load x{i}; this order implicitly defines i]
        T    #@ [temp := x{i}]
   [38] A    #L [load x{i + 1}]
        S    #@ [acc := x{i + 1} - temp]
        E  49 @ [don't swap if x{i + 1} >= temp]
 
       [Here to swap x{i} and x{i + 1}]
        A    #@ [restore acc := x{i + 1} after test]
   [42] T    #L [x{i} := x{i + 1}]
        A  42 @ [load 'T' order for x{i}]
        A   4 @ [inc address by 2]
        T  47 @ [plant 'T' order for x{i + 1}]
        A    #@ [load temp]
   [47] T    #L [to x{i + 1}]
        T   2 @ [swapped := 0 (true)]
 
   [49] T     F [clear acc]
        A  38 @ [load 'A' order for x{i + 1}]
        G  27 @ [loop (unconditional) to inc i]
 
   [52] T     F
        A   3 @ [load 'A' order for x{j}]
        S   4 @ [dec address by 2]
        G  18 @ [loop (unconditional) to dec j]
 
       [Print the sorted list of integers]
   [56] O  11 @ [figure shift]
        T     F [clear acc]
        A   5 @ [load 'A' order for head of list]
        T  65 @ [plant in code below]
        S     L [load negative number of items]
   [61] T     @ [use first word of temp store for count]
        A  65 @ [load 'A' order for item]
        A   4 @ [inc address by 2]
        T  65 @ [store back]
   [65] A    #L [load next item in list] 
        T     D [to 0D for printing]
   [67] A  67 @ [for subroutine return]
        G  56 F [print integer, clears acc]
        O  13 @ [print CR]
        O  12 @ [print LF]
        A     @ [negative count]
        A  10 @ [add 1]
        G  61 @ [loop back till count = 0]
   [74] O   9 @ [null to flush teleprinter buffer]
        Z     F [stop]
        E  14 Z [define entry point]
        P     F [acc = 0 on entry]
 