CS#61B#Data#Structures#and#Programming#Methodology##July#28,#2008#David#Sun#Announcements#• Midterm#II#on#Wed#7/31,#11:00am#–#12:30pm#– In#class#open#book.#No#computational#devices#allowed.#– Covers#everything#up#and#including#today’s#lecture.#• Revision#class#tomorrow.##– 45#minute#mini‐mock#exam.#• Project#3#will#be#out#later#today.#– Check#newsgroup#and#course#website.##– Option#to#work#in#pairs#or#groups#of#three.##• It’s#your#responsibility#to#stay#up‐to‐date#with#the#newsgroup!#Space#Complexity#• Not‐in‐place#version:##– Partitioning#uses#an#additional#Theta(n)#storage#space#(best#case)#andTheta(n2)*(worst#case).*• To#partition#in‐place:#– Given#an#array#a*and#sort#all#elements#between#l(eft)*and#r(ight).#– Choose#a#pivot#v#and#swap#with#a[r].#– Initialize#i#to#l*‐*1,#and#j#to#r##so#i#and#j#sandwich#the#items#to#be#sorted#(not#including#the#pivot).##– Enforce#the#following#invariants.##• All#items#at#or#left#of#index#i#have#a#key#<=#the#pivot's#key.##• All#items#at#or#right#of#index#j#have#a#key#>=#the#pivot's#key.#Quicksort#on#Arrays#• (continued)#– Advance#i#to#the#first#a[i]#greater#than#or#equal#to#the#pivot.#– Decrement#j#until#the#first#a[j]*less#than#or#equal#to#the#pivot.##– a[i]*and#a[j]*are#on#the#wrong#side#of#the#partition,#so#swap#a[i]*and#a[j].##– Repeat#until#the#indices#i#and#j#meet#in#the#middle.##– Move#the#pivot#back#into#the#middle#–#swapping#the#last#item#with#a[i].##public static void quicksort(Comparable[] a, int left, int right) { // If there's fewer than two items, do nothing. if (left < right) { int pivotIndex = random number from left to right; //Swap pivot with last item Comparable pivot = a[pivotIndex]; a[pivotIndex] = a[right]; a[right] = pivot; int i = left - 1; int j = right; do { do { i++; } while (a[i].compareTo(pivot) < 0); do { j--; } while ((a[j].compareTo(pivot) > 0) && (j > left)); if (i< j) { swap a[i] and a[j]; } } while (i< j); a[right] = a[i]; a[i] = pivot; // Put pivot in the middle where it belongs quicksort(a, left, i - 1); // Recursively sort left list quicksort(a, i + 1, right); // Recursively sort right list }Some#Details#• Can#the#"do { i++ }"#loop#walk#off#the#end#of#the#array#and#generate#an#out‐of‐#bounds#exception?##– No,#because#a[right]#contains#the#pivot,#so#i#will#stop#advancing#when#i#==#right#(if#not#sooner).#• There#is#no#such#assurance#for#j,#though,#so#the#"do { j-- }"#loop#explicitly#tests#whether#"j#>#left"#before#decrementing.#Comparison#of#O(n*log*n)*Algorithms#Worst‐case*Space*Comments*Quicksort#Theta(n2)##Theta(logn)#(in‐place#partitioning)#Heapsort#Theta(nlogn)##Theta(1)#Heapsort#requires#efficient##random#access.#Mergesort#Theta(nlogn)*Theta(n)#(on#arrays)#Works#well#with#linked#lists#(eg..#disk#storage).##Selection#• The#selection#problem:#we#want#to#find#the#kth#smallest#key#in#a#list,#i.e.#what’s#the#kth*item#in#the#list#when#it’s#in#sorted#order?#• One#approach:#sort#the#list,#then#look#up#the#item#at#index#k.##• But#what#if#we#don’t#care#if#the#rest#of#the#list#is#in#sorted#order#or#not,#is#there#a#faster#way?##Quickselct#• In#quicksort#obser ve#that:#– #after#the#partitioning#step,#we#have#three#lists:#L1,#Iv,#and#L2.#– We#know#which#of#the#three#lists#contains#index#j,#because#we#know#the#lengths#of#I1#and#I2.##– Therefore,#we#only#need#to#search#one#of#the#three#lists.#Quickselect# Start with an unsorted list I of n input items. Choose a pivot item v from I. Partition I into three unsorted lists I1, Iv, and I2. I1 contains all items whose keys are smaller than v's key. I2 contains all items whose keys are larger than v's. Iv contains the pivot v. if (j < |I1|) { Recursively find the item with index j in I1; return it. } else if (j < |I1| + |Iv|) { Return the pivot v. } else { // j >= |I1| + |Iv|. Recursively find the item with index j - |I1| - |Iv| in I2; return it. }Comparison#Sort#• All#the#sorting#algorithms#we’ve#seen#so#far#are#comparison*sorts:##– the#ordering#of#the#elements#can#be#determined#by#comparison#of#their#keys.##– All#actions#taken#by#the#sorting#algorithm#are#based#on#the#results#of#a#sequence#of#true/false#questions#(a#two#way#decision).#• If#all#you#can#do#is#comparison,#then#it#can#be#proven#that#you#can#do#no#better#than#Ω*(n*log*n)*in#the#worst#case#to#sort#n#elements#– In#this#sense,#merge#sort#and#heapsort#are#asymptotically#optimal.#Lower#Bound#of#Comparison#Sort#• Given#a#random#scrambling#of#n#numbers#in#an#array,#with#each#number#from#1...n*occurring#once.#How#many#possible#orders#(or#permutations)#can#the#numbers#be#in?##– The#answer#is#n!,#where#n!*=*1*x*2*x*3*x*...*x*(n‐2)*x*(n‐1)*x*n.#– Observe#that#if#n*>*0,##n!*=*1*x*2*x*...*x*(n‐1)*x*n*<=**n**x*n*x*...*x*n*x*n*x*n*=*nn#and##n!*=*1*x*2*x*...*x*(n‐1)*x*n#>=#n/2#x#(n/2#+#1)#x#...#x#(n‐1)#x#n##* * * * * * * **>=#(n/2)(n/2)##– So#(n/2)(n/2)**<=*n!*<=*nn.*– #Let's#look#at#the#logarithms#of#both#these#numbers:##log((n/2)(n/2)*=*(n/2)*log*(n/2),#which#is#in#Theta(n*log*n),#and#log(nn)*=*n*log*n.##– Hence,#log(n!)*is*also*in*Theta(n*log*n).*Lower#Bound#of#Comparison#Sort#• Given#n!*of#the#input,#a#correct*sorting#algorithm#must#do#n!#different#permutations#of#comparisons#and#swap#operations.#• Therefore,#there#must#be#n!#possible#permutations#of#true/false*answers#for#the#n!*permutations#of#inputs.#• If#a#sorting#algorithm#never#asks#more#than#k#true/false#questions,#it#generates#less#than#or#equal#to#2k#different#sequences#of#true/false#answers.##– If#it#correctly#sorts#every#permutation#of#1...n,#then##n!*<=*2k,#so#log2*(n!)*<=*k,#and#k#is#in*Ω(n*log*n).*#Linear#Sorting#Algorithms#• But#suppose#can#do#more#than#comparing#keys.##• What#if#we#know#something#about#the#keys#that#are#being#sorted:#– For#example,#how#can#we#sort#a#set#of#n*integer#keys#whose#values#range#from#0#to#kn#,#for#some#small#constant*k?#• One#technique:#for#each#element#x,#determine#the#number#of#elements#less*than#x.*We#can#place#x*immediately#into#its#right#position.#– If#Mp#=##items#with#value#<*p,#then#in#sorted#order,#the#jth#item#with#value#p#must#be##Mp*+*j*.#•
View Full Document