O(n) examination of sort algorithm : bubbleSort[ {3,2,2,1} ]

verbose = False ; (* turn off printing *) countSort = {} ;        ... aken[[1]]}] ; AppendTo[countSort, {n, loopCount}],  {logn, 1, 3, .25} ] ;

{n,loopCount} = {10, 45} in 0. Second

{n,loopCount} = {17, 136} in 0.01 Second

{n,loopCount} = {31, 465} in 0.03 Second

{n,loopCount} = {56, 1540} in 0.07 Second

{n,loopCount} = {100, 4950} in 0.21 Second

{n,loopCount} = {177, 15576} in 0.63 Second

{n,loopCount} = {316, 49770} in 2.22 Second

{n,loopCount} = {562, 157641} in 7.34 Second

{n,loopCount} = {1000, 499500} in 23.03 Second

RowBox[{ListPlot, [, RowBox[{countSort, ,, RowBox[{PlotStyle, , RowBox[{PointSize, [, 0.03, ]}]}]}], ]}]

[Graphics:../HTMLFiles/index_104.gif]

⁃Graphics⁃

RowBox[{ListPlot, [, RowBox[{timeSort, ,, RowBox[{PlotStyle, , RowBox[{PointSize, [, 0.03, ]}]}]}], ]}]

[Graphics:../HTMLFiles/index_107.gif]

⁃Graphics⁃

Fit[countSort, {1, x, x^2, x^3}, {x}]//Chop

RowBox[{RowBox[{RowBox[{-, 0.5}], , x}], +, RowBox[{0.5, , x^2}]}]

The number of times through the inner loop with n elements is (n-1) + (n-2) + (n-3) ... + 1

Clear[n] ; Sum[i, {i, 1 , n - 1}]

1/2 (-1 + n) n

Underoverscript[∑, i = 1, arg3] i

1/2 (-1 + n) n

So we see that the bubble sort is O(n^2).  This algorithm is almost never used - the QuickSort, for comparison, is O(n log(n)).

Created by Mathematica  (September 29, 2004)