Searching and Sorting

Jim Mahoney
September 29 2004

This notebook looks at the binary search and bubble sort algorithms.
Both are implemented as programs, and then analyzed for how costly they are.

This week's assignment asks you to play around with something like this, for a different sorting function;
however, I've put more technical stuff into these programs than I expect you to do for your own work.

(The original version of this file became corrupted after saving as html and couldn't be read back in;
this one has been re-typed from the .gif images in the html version.  
See the as_html folder for more detail; I didn't have time to re-type everything.)

Definitions

This section defines

  binaryFindIndex[ sortedList, number ]                           search a list for a number
  bubbleSort[ list ]                                                             sort a list with the bubble sort algorithm
  
as well as two utility functions for generating random lists
  
  randomList[ nItems, maxNumber ]
  randomSortedList[ nItems, maxNumber ]

and a few functions for testing things out.

Both binaryFindIndex and bubbleSort use two global variables for use in debugging and analysis, "verbose" and "loopCount".
To see how they're working, set "verbose=True", while to just have them shut up, set "verbose=False".
After either one runs, loopCount will be set to the number of times through the innermost loop.

\(\(\( (*a\ binary\ search\ algorithm*) \)\(
\)\(\(binaryFindIndex::usage = "binaryFindIndex[list,x] returns i such that list[[i]]==x, or returns False if x isn't in the list
Set verbose to True or False to turn diagnostic printing on or off.
The global loopCount is wet to the number of times through the main loop.";\)

    \(verbose = 
        True;\) (*turns\ printing\ of\ results\ on\ or\ off*) 

    \(binaryFindIndex[list_, x_] := 
        Module[{iLow, iHigh, i}, 
loopCount = 
            0;  (*global\ to\ measure\ expense\ of\ search*) 
If[verbose, 
            Print["Looking for i such that " <> 
                ToString[list] <> "[i] == " <> 
                ToString[x]]]; 
If[\(! OrderedQ[
                list]\), 
Return["Oops - binaryFindIndex[list,x] only works if the list is ordered."]]; 
iLow = 1; 
iHigh = 
            Length[list]; 
While[
            True, 
\(loopCount++\); 
i = 
              Floor[\((iLow + iHigh)\)/2]; 
If[
              verbose, 
Print[" iLow = " <> 
                  ToString[iLow] <> ", iHigh = " <> 
                  ToString[iHigh] <> ", i = " <> 
                  ToString[i]]]; 
If[
              list[\([i]\)] == x, Return[i]];  (*Match\ found; 
              we' re\ \(\(done\)\(.\)\)*) 
If[
              iLow ≥ iHigh, 
              Return[False]];  (*No\ where\ else\ to\ look, 
              x\ isn' t\ in\ \(\(list\)\(.\)\)*) 
If[
              x < list[\([i]\)], iHigh = i - 1];  (*If\ x\ is\ in\ list, 
              it' s\ below\ \(\(i\)\(.\)\)*) If[x > list[\([i]\)], 
              iLow = i + 1];  (*If\ x\ is\ in\ list, 
              it' s\ above\ \(\(i\)\(.\)\)*) 
];
];\)

 (*testSearch[]\ prints\ out\ what\ the\ search\ does\ on\ some\ small\ \(\(lists\)\(.\)\)*) 

    \(testSearch[] := 
        Module[{answer}, 
          verbose = 
            True; 
 (*What\ happens\ if\ list\ is\ in\ wrong\ \(\(order\)\(.\)\)*) Print[
            binaryFindIndex[{10, 5, 1}, 
              5]]; 
 (*Empty\ \(\(list\)\(?\)\)*) Print[
            binaryFindIndex[{}, 10]]; 
Print[
            binaryFindIndex[{12}, 
              5]]; 
 (*One\ element\ \(\(list\)\(?\)\)*) 
            Print[binaryFindIndex[{12}, 12]]; 
Print[
            binaryFindIndex[{12}, 
              20]]; 
 (*Two\ element\ \(\(lists\)\(?\)\)*) 
            Print[binaryFindIndex[{5, 10}, 1]]; 
Print[
            binaryFindIndex[{5, 10}, 5]]; 
Print[
            binaryFindIndex[{5, 10}, 7]]; 
Print[
            binaryFindIndex[{5, 10}, 10]]; 
Print[
            binaryFindIndex[{5, 10}, 20]]; 
Print[
            binaryFindIndex[{5, 10}, 
              20]]; 
 (*Three\ element\ \(\(lists\)\(?\)\)*) 
            Print[binaryFindIndex[{1, 5, 10, 20, 30}, 
              7]]; 
Print[
            binaryFindIndex[{1, 5, 10, 20, 30}, 
              5]];
];\)


     (*generate\ a\ random\ list*) \(randomList[nItems_, maxNumber_] := 
        Table[Random[Integer, maxNumber], {nItems}];\)

     (*generate\ a\ random\ sorted\ list*) \ \(randomSortedList[nItems_, 
          maxNumber_] := 
        Sort[randomList[nItems, 
            maxNumber]];\)

 (*bubble\ sort - double\ loop, comparing\ 1.  . rest, 2.  . rest, 
      3.  . rest,  ... *) 

    \(bubbleSort[input_] := 
        Module[{list, n}, 
list = input;  (*\ 
            make\ a\ copy\ of\ input\ *) 
n = 
            Length[list]; 
loopCount = 
            0; 
If[verbose, 
            Print["Applying bubble sort to" <> 
                ToString[
                  input] <> "..."]]; 
Do[
Do[
\(loopCount++\); 
If[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ list[\([i]\)] > 
                  list[\([j]\)], 
 (*then*) \ \ temp = 
                  list[\([i]\)]; 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ list[\([i]\)] = 
                  list[\([j]\)]; 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ list[\([j]\)] = temp]
, {j, i + 1, 
                n}], 
{i, 1, n - 1}]; 
If[
            verbose, 
            Print[" ... result is " <> 
                ToString[list]]]; 
Return[
            list];
];\)

 (*does\ the\ bubble\ \(\(work\)\(?\)\)*) 

    \(testBubble[] := 
        Module[{}, 
verbose = 
            True; 
bubbleSort[{}]; 
bubbleSort[{1}]; 
bubbleSort[{1, 
              2}]; 
bubbleSort[{2, 
              1}]; 
bubbleSort[{5, 4, 3, 2, 
              1}]; 
Print[" loopCount = " <> 
              ToString[loopCount]];
];\)\)\)\)

Testing

See if they work...

testSearch[]

testBubble[]

O(n) examination of a search algorithm, binarySearch[ {10,20,20,30}, 10]

verbose = False;   
counts = {};
times = {};
\(\(Do[
n = 
          10\^logn; 
timeTaken = \(Timing[
binaryFindIndex[randomSortedList[n, 10  n], 
                Random[Integer, 
                  10\ n]]]\)
[\([1]\)]; 
Print[" {log(n),loopCount} = " <> 
            ToString[{logn, loopCount}] <> " in "\  <> \ 
            ToString[timeTaken]]; 
AppendTo[
          times, {logn, timeTaken[\([1]\)]}]; 
AppendTo[
          counts, {logn, loopCount}]
, {logn, 1, 
          6}
];\)\)

ListPlot[counts, PlotStyle -> PointSize[0.03]]

ListPlot[times, PlotStyle -> PointSize[0.03]]

O(n) examination of a sort algorith, bubbleSort[ {10,5,2} ]

verbose = False;   
countSort = {};
timeSort = {};
Do[
n = 
          Floor[(10^logn)]; 
timeTaken = Timing[
              bubbleSort[
                randomList[n, 
                  10  n]]][[1]]; 
Print[" \
{n,loopCount} = " <> ToString[{n, loopCount}] <> " in "  <>  
            ToString[timeTaken]]; 
AppendTo[
          timeSort, {n, timeTaken[[1]]}]; 
AppendTo[
          countSort, {n, loopCount}]
, {logn, 1, 
          3,  .25}
];

ListPlot[countSort, PlotStyle -> PointSize[0.03]]

ListPlot[timeSort, PlotStyle -> PointSize[0.03]]

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

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

So this is O((n^2)).  Other sorting algorithms, like the quick sort, run in O(n log(n)) time - generally much quicker for large n.