13.3. SORTINGALGORITHMS 231
willcutthesizeoftheproblemin halfeachtime.Inorderto dothis,weneedtospecifytherangeoflocations
inthelistthatarestill“inplay”foreachrecursive call. We candothisbypassingthevaluesoflowand
highalongwiththelist.Eachinvocationwillsearchthelistbetweenthelow andhighindexes.
Hereis a directimplementationoftherecursive algorithmusingtheseideas:
def recBinSearch(x,nums, low, high):
if low > high: # No place left to look,return -1
return -1
mid = (low + high)/ 2
item = nums[mid]
if item == x: # Found it! Return the index
return mid
elif x < item: # Look in lower half
return recBinSearch(x,nums, low, mid-1)
else: # Look in upper half
return recBinSearch(x,nums, mid+1, high)
We canthenimplementouroriginalsearchfunctionusinga suitablecallto therecursive binarysearch,telling
it tostartthesearchbetween0 andlen(nums)-1
def search(x, nums):
return recBinSearch(x,nums, 0, len(nums)-1)
Ofcourse,asinthecaseoffactorial,wealreadyimplementedthisalgorithmusinga loop,andthere
isnocompellingreasontousea recursive implementation. Infact,theloopingversionisprobablya bit
fasterbecausecallingfunctionsis generallyslowerthaniteratinga loop. Therecursive version,however,
makesthedivide-and-conquerstructureofbinarysearchmuchmoreobvious.Below, wewillseeexamples
whererecursive divide-and-conquerapproachesprovidea naturalsolutiontosomeproblemswhereloopsare
awkward.
13.3 SortingAlgorithms
Thesortingproblemprovidesa nicetestbedforthealgorithmdesigntechniqueswehave beendiscussing.
Recall,thebasicsortingproblemis totake a listandrearrangeit sothatthevaluesareinincreasing(actually,
nondecreasing)order.
13.3.1 Naive Sorting:SelectionSort
Let’s startwitha simple“bethecomputer”approachtosorting.Supposeyouhave a stackofindex cards,
eachwitha numberonit. Thestackhasbeenshuffled,andyouneedtoputthecardsbackinorder. How
wouldyouaccomplishthistask?
Thereareany numberofgoodsystematicapproaches.Onesimplemethodis tolookthroughthedeck
tofindthesmallestvalueandthenplacethatvalueatthefrontofthestack(orperhapsina separatestack).
Thenyoucouldgothroughandfindthesmallestoftheremainingcardsandputit next in line,etc.Ofcourse,
thismeansthatyou’ll alsoneedanalgorithmforfindingthesmallestremainingvalue.Youcanusethesame
approachweusedforfindingthemaxofa list(seeChapter6).Asyougothrough,youkeeptrackofthe
smallestvalueseensofar, updatingthatvaluewhenever youfinda smallerone.
ThealgorithmI justdescribedis calledselectionsort. Basically, thealgorithmconsistsofa loopand
eachtimethroughtheloop,weselectthesmallestoftheremainingelementsandmove it intoitsproper
position.Applyingthisideatoa list,weproceedbyfindingthesmallestvalueinthelistandputtingit into
the0thposition.Thenwefindthesmallestremainingvalue(frompositions1–(n-1))andputit inposition1.
Nextthesmallestvaluefrompositions2–(n-1)goesintoposition2,etc.Whenwegettotheendofthelist,
everythingwillbeinitsproperplace.
Thereis onesubtletyinimplementingthisalgorithm.Whenweplacea valueintoitsproperposition,we
needtomake surethatwedonotaccidentlylosethevaluethatwasoriginallystoredinthatposition.For
example,if thesmallestitemis inposition10,movingit intoposition0 involvesanassignment.