ENG1003 Lecture Notes - Lecture 10: Binary Search Algorithm, Merge Sort, Big O Notation
30 May 2018
School
Department
Course
Professor
!"#$%&'() !"#"$%&'%$"()"'*$+&,-+'(*$ +("$(./%"#"0&(1.%2 (&"0&(3,-%"#"0#&+'-,.#&"
(,+-(2%
456"-(20,+%&"$7$+%2",$%3"+("-(*+&(."%.%/#+(&"1%8#/'(,&
97$+%2"8#$"*("'*+&'*$'-":*(;.%35%"()"#*"%.%/#+(&
○
<.."-(*+&(.".(5'-"2,$+"1%"$0%-')'%3"#$"#*"#.5(&'+82
○
=
>8%&%"#&%"/#&'(,$"$+&#+%5'%$ +8#+"0&(3,-%"?1%++%&?"&%$,.+$"5'/%*"$(2%"
3%$'&%3"-&'+%&'#
=
*$%'&+# !"5((3")(&"3'$-,$$'*5"%))'-'%*-7 ()"#.5(&'+82$")&2"#"0&#-+'-#."
0%&$0%-+'/%
@(*-%0+,#..7"$'20.%"1,+"2#*7"3'))%&%*+"#00&(#-8%$
=
*,",-'&$+./$%'
!"0&(5&%$$'/%.7"1,'.3'*5"#".'$+"()"%.%2%*+$"'*"$(&+%3"(&3%&"ABBC"D
>("#33 %#-8"*%;"%.%2%*+E"$%.%-+$".(;%$+ /#.,%")&2"&%2#'*'*5"
,*$(&+%3 .'$+"#*3"$;#0$ +8'$"'*+("0.#-%
=
0+/,%'&$+./$%' !"F,$+".':%"#&&#*5'*5"0(:%&"-#&3$"'*"8#*3"BBC"$+&#'58+#;#7
G*/(./%$"$8')+'*5"()"%.%2%*+$"+("2#:%"&((2")(&"*%;
12&-3/$%' !"H#/#9-&'0+"1,'.+B'*"Array.sort() 2%+8(3"Bfaster+8#*"
$%.%-+'(*"$(&+I
4,%5$%)6+-,.7$)86%&/$+
!"17"2#:'*5"#"H#/#9-&'0+"+%$+"8#&*%$$"+("2%#$,&%"+8%"+'2% +#:%*"17"%#-8"
#.5(&'+82"+("$(&+"+8%"$#2%"3#+#$%+
*,",-'&+# 6+.!"#$%&'()
J&#-+'-#."$0%%3 K,$,#..7"0&'2#&7"-(*-%&*L
=
M,#.'+7 ()"&%$,.+$
456"'*")'*3'*5"&(,+%$E"2#7";#*+"+("2'*"+,&*$E"3'$+#*-%"+&#/%..%3E"
(&"0&%)%&".#&5%&"-#0#-'+7"&(#3$
○
=
>70%$"()"(0$ 0%&)(&2%3
456"&%#3'*5")&2N;&'+'*5"+("#"3'$:E"2#+8$"(0$E"+#:'*5"#3/#*+#5%"
()"3#+#".':%.7"+("1%"'*"-#-8%
○
9)"#))%-+$"0%&)
○
=
9+(% &%O$
456"-8%-:'*5"')"#"*,21%&"'$"0&'2%P"3#+#1#$%"()"Q2'."R9"9'%/%"()"
4&#+8($+%*%$"#.5(&'+82
○
=
D%#3#1'.'+7"S",*3%&$+#*3#1'.'+7
G)"2,$+"1%"-(&&%-+"#*3"2#'*+#'*#1.%
○
90%%3"*(+"$("'20+
○
=
9+#1.% &%$,.+$P
G)"%.%2$";N"%O,#."/#.,%"3("*(+"8#/%"&%.#+'/%"(&3%&"-8#*5%3"17"
$(&+
○
456"$%.%-+'(*"$(&+"K*TL"R9"O,'-:$(&+"KUV>L
○
=
<.5(&'+82$"()")%;(&:$N#00$"-(22(*.7"3%0%*3 (*"2#*7")#-+(&$
W%0"(*"(0+'(*$"$0%-')'%3"17",$%& VD"3%+%&2'*%3"17"$'X%N+70%"()"'*0,+"
3#+#
456"H#/#9-&'0+Y$"Array.sort
U,2%&'-P"$+3"O,'-:$(&+")&2"@ZZ
U(*B*,2%&'-"-(*+'5,(,$"#&P"2%&5%$(&+
V+8%&$P"$%.%-+'(*"$(&+
7$)8",9&': !"#"+8%(&%+'-#."2%#$,&%"+8#+"3%#.$";N"+8%"5%*%&#."-.#$$"()"),*-+'(*"
1(,*3'*5"+8%"&,*"+'2%E"1,+"'$",*-(*-%&*%3";N"-(*$+#*+N,*-8#*5'*5")#-+(&$"
,*&%.#+%3"+("'*0,+"$'X%
['/%$",$"#*"'3%#"()"8(;"2,-8"$.(;%& #*"#.5(&'+82"5%+$"0&(0(&+'(*#..7"+("
5&(;+8"()"'*0,+"$'X%
;;<,+=/.'$.>,.,98%,//,=.&+.',%)/.$5.'(,./&?,.$5.'(,.&+82' '(6'.'(,.-$=,.
&/.%2+.$+@.,A#A@.'(,./6),.6"#$%&'().B&"".2/26"":.'63,.6."$'."$+#,%.'$./$%'.
6."&/'.$5.6.)&""&$+.&',)/.'(6+.&'.B&"".'$./$%'.6."&/'.$5.',+A.C$%.'(&/.%,6/$+@.
-$)8",9&':.-6+.>,.%,8%,/,+',=.6/./$),.52+-'&$+.$5.'(,.&+82'./&?,A
7$=,.-(20.%\'+7
!"-(*-%&*%3";'+8"8(;"(0+'2#. -%&+#'*"#.5(&'+82$"#&%E
0#&+'-,.#&.7"8(;"2,-8"+'2%E"$0#-%N2%2(&7"(&"(+8%&"&%$(,&-%$ +8%7"
&%O,'&%"+("$(./%"0#&+'-,.#&"0&(1.%2$
W%0%*3%*+"(*"$'X%"()"'*0,+ -(3%"'$"&,*"(*=
D%0&%$%*+%3"#$"$(2%"),*-+'(* ()"'*0,+"$'X%"+=
<&), -(20.%\'+7"K-(*$'3%&'*5"%\%-,+'(*"+'2%L
4\0&%$$%3"#$"]'5BV"*(+#+'(*"VK^L=
7$+/'6+' '&),D.E.FGH
<*7"0'%-%"()"-(3%"+8#+"#.;#7$"&,*$"'*"#"$'2'.#&"#2*+"()"+'2%E"
&%5#&3.%$$"()"'*0,+"$'X%N.%*5+8"()"#&
○
9'*-%"#&$"#&%"$+(&%3"'*"2%2(&7"#$"#"-(*+'5,(,$"&#*5% K*%\+"+("
%#-8"(+8%&"'*"$%O,%*-%LE"#..(;'*5"+8%"0($'+'(*"()"#*7"/#.,%"+("1%"
-#.-,.#+%3"#*3"#--%$$%3")&2"'+$"'*3%\E"&%5#&3.%$$"()"$'X%"()"#&
○
456"3'&%-+.7"#--%$$'*5"#*7"%.%2%*+"()"#*"#&
○
I$#6%&'()&- '&),D.E.F"$#.J+H.;;>,'',%.'(6+."&+,6%
<.5(&'+82$"+8#+"+#:%"+'2%"+("&,*"0&(0(&+'(*#."+("+8%".(5#&'+82 ()"
+8%"'*0,+"$'X%
○
456"1'*#&7"$%#&-8
<*"#.5(&'+82"+8#+"-#*"1%",$%3"+(")'*3"+8%"0($'+'(* ()"#*"
%.%2%*+"()"#"0#&+'-,.#&"/#.,%"'*"#"$(&+%3"#&
§
]7"$0.'++'*5"+8%"$%#&-8"$0#-%"'*"8#.)";N"%#-8"0&(5&%$$'/% $+%0
§
_$%3")(&"3%1,55'*5 K)'*3'*5";&(*5"-(22'+L"K['+"8#$"
-(22#*3"git bisectL
§
9+%0$P
§
9%.%-+$"2'33.%"%.%2"()"#&'6
G)"2'33.%"!!!"3%$'&%3"/#.,%E"#.5(&'+82"$+(0$''6
4.$%
G)"2'33.%"C"3%$'&%3"/#.,%E"&%0%#+";'+8")'&$+"8#.)"()"#&QL
G)"2'33.%"`"3%$'&%3"/#.,%E"&%0%#+";'+8"$%-(*3"8#.)"()"
#&
TL
'''6
○
I&+,6% '&),D.E.F+H
<.5(&'+82$"+#:%"+'2%"3'&%-+.7"0&(0(&+'(*#."+("$'X% ()"'*0,+
○
a'*3'*5"+8% .(;%$+N8'58%$+ /#.,%"'*"#*",*$(&+%3 #&
○
V*.7"*%%3"+(".((:"#+"%#-8"%.%2"()"+8%"#&"(*-%"b,$'*5"#")(&".((0"
+("5("+8&(,58"%#-8"%.%2%*+"'*"+8%"#&bE"$("$+&'-+.7"3%0"(*"#&"
$'X%
○
<33'*5N3%.%+'*5"#*"%.%2")&2"2'33.%"()"#&"'$"AGU4<D '*"+8%"
.%*5+8"()"+8%"#&
9'*-%"#*"#&"(--,0'%$"#"-(*+'5,(,$"&#*5%"()"2%2(&7E"8#/%"
+("2(/%"+8%"%*+'&%"#&")(&"2#:%"$0#-%")(&"#33%3"%.%2"VD"
)'.."'*"%20+7"$0#-%"()"&%2(/%3"%.%2
§
○
126=%6'&- '&),D.E.F+JH
<.5(&'+82$"+#:%"+'2%"0&(0(&+'(*#."+("+8%"$O,#&%"()"$'X%"()"'*0,+
V,+%&".((0".((:$"#+"%/%&7"%.%2"()"#&
§
a(&"%#-8"()"+8($%E"'**%&".((0".((:$"#+"#.."&%2#'*'*5"%.%2$"()"
#&
§
○
456"$%.%-+'(*"$(&+"-(3%"BBC"0%&)(&2$"$.(;%&"+8#*"M,'-:$(&+"1-($"()"
+8'$
○
A'*%#&'+82'-"+'2%"'$"$(2%;8%&%"1+;*"A'*%#&"S"M,#3&#+'-"+'2%
○
Week$10:$Algos$&$Efficiency
9#+,&3#7E"c"d#7"TeQf
QgPgh
Document Summary
Algorithm = a series of instructions to solve a problem or produce a particular outcome. Eg. computer system used to control elevator behaviour. System has no intrinsic knowledge of an elevator. All control logic must be specified as an algorithm. There are various strategies that produce better results given some desired criteria. Sorting = good for discussing efficiency of algorithms frm a practical perspective. = progressively building a list of elements in sorted order l--> r. To add each new element, selects lowest value frm remaining unsorted list and swaps this into place. Insertion sort = just like arranging poker cards in hand --> straightaway. Involves shifting of elements to make room for new. Quicksort = javascript built-in array. sort() method - faster than selection sort! = by making a javascript test harness to measure the time taken by each algorithm to sort the same dataset.
