FIT1008 Lecture Notes - Lecture 4: Bubble Sort, Minimax
18 Jun 2018
School
Department
Course
Professor
Bubble&-stable,&pair-swapping.
Insertion&-stable,&since&the&first&element&in&the&unsorted&position&is&inserted&just&
before&the&element&greater&than&it&(not&greater/equals&strictly)&in&the&sorted&portion&
of&the&list&[take&eg&of&[2,8,51,52,9]&-->&[2,51,8,52,9]&-->&52won't&go&behind&51
Selection&-least&number&of&swaps&(chooses&max/min&and&puts&at&end/beginning&
with&only&1&swap,&thus&would&only&do&n&swaps&in&worst&case),&but¬&stable
Stability
=&the&relative&order&of&elements&with&the&same&value&is&maintained&after&list&has&
been&sorted
Instability normally&happens&when&non-adjacent&elements&are&swapped.
If&swap&involves&the&first&elem&with&that&same&value&as&another,&it&could&be&
moved&to&after&that&other&elem&with&the&same&value.
•
Results&in&change&of&relative&order&of&elements&with&same&key•
Sort
Description
Best&case
Worst&case
How&to&remb
Stable?
Bubble
Finds&biggest&in&
each&iteration&
(decreases&size&by&
1&each&time)&by&
swapping&adjacent&
elems&during&each
O(n2)&-no&
swaps,&still&
has&to&go&
through&
entire&list&to&
check&anyway
O(n2)&-all&
swaps
Ring&slowly&
shrinking&in&
size,&only&
swap&adj&
elems&each&
time
Y
Selection
(least&
swaps)
On&each&iteration&
(decreases/&
increases&by&1&
each&time)&labels&
max/min,&then&
swaps&at&end&of&
each
O(n2)
O(n2)
Only&1&swap&
per&iteration.&
Find&
max/min&in&
unsorted&and&
push&out
-
Insertion
Elems&before&the&
target&(one&being&
compared)&are&
sorted
Elem&immediately&
after&is&inserted&
into&sorted§ion
O(n)&-
everything&
alrdy&sorted
O(n2)&-
have&to&
sort&all
Sort&from&L&>&
R,&compare&
target&(elem&
immediately&
after&sorted&
part)
Y
Merge
Recursive.
Divides&list&into&
elems,&then&
combine&slowly&
until&entire&list&has&
been&combined
O(nlogn)
[number&of&
comparisons&
made&@&each&
stage&*&max&
number&of&
times&list&of&
size&n&can&be&
halved]
O(nlogn)
Split&
everything&
then&
recombine.
Easy&split,&
hard&
combine.
Y
Quick
Recursive.
Last&element&is&
pivot,&until&elem&
greater&than&it&is&
found.
Pivot&moves&to&
next&elem&on&L,&
and&greater&elem&
and&old&pivot&swap
O(nlogn)&-
when&pivot&
halves&list&size&
w/&every&
partition
O(n2)&-
when&pivot&
happens&to&
reduces&
size&of&list&
by&1&in&
each&
partition
Hard&split,&
easy&
combine.
-
Shaker Like&bubble&sort,&
except&when&one&
iteration&reaches&
the&other&end&of&
the&list,&next&
iteration&is&in&
opposite&direction
Iterates&until&list&is&
sorted
O(n)&
**&can&leave&
loop&early&if&
needed&to&
speed&up&
process,&using&
boolean&
swapped
O(n2)Bubble&sort&
but&reflected&
like&glow&
hockey.
Y
Binary:
search
Search&scope&
keeps&halving&until&
elem&is&found
O(1)&&-target&
in&middle&of&
list
O(logn)&-
target¬&
in&list
Search&scope&
keeps&halving
NA
Week$4:$sorting,$stability
Thursday,& 14&June&2018
14:14
Document Summary
Finds biggest in each iteration (decreases size by. 1 each time) by swapping adjacent elems during each. O(n2) - no swaps, still has to go through entire list to check anyway. On each iteration (decreases/ increases by 1 each time) labels max/min, then swaps at end of each. Insertion elems before the target (one being compared) are sorted. Elem immediately after is inserted into sorted section. Divides list into elems, then combine slowly until entire list has been combined. [number of comparisons made @ each stage * max number of times list of size n can be halved] Ring slowly shrinking in size, only swap adj elems each time. R, compare target (elem immediately after sorted part) Last element is pivot, until elem greater than it is. O(nlogn) - when pivot halves list size w/ every. Shaker reduces size of list by 1 in each partition. Pivot moves to next elem on l, and greater elem and old pivot swap.
