16. Chapter 16 Solutions

Written by Jonathan Sande

Solution to Challenge 1

If you start with the following list:

[4, 2, 5, 1, 3] 

Here are the steps a bubble sort would take:

[2, 4, 5, 1, 3] // 4-2 swapped [2, 4, 5, 1, 3] // 4-5 not swapped [2, 4, 1, 5, 3] // 5-1 swapped [2, 4, 1, 3, 5] // 5-3 swapped [2, 4, 1, 3, 5] // 2-4 not swapped [2, 1, 4, 3, 5] // 4-1 swapped [2, 1, 3, 4, 5] // 4-3 swapped [1, 2, 3, 4, 5] // 2-1 swapped [1, 2, 3, 4, 5] // 2-3 not swapped [1, 2, 3, 4, 5] // 1-2 not swapped 

Bubble sort needed the full O(n²) traversal to finish the sort. It made ten comparisons and six swaps.

Solution to Challenge 2

Given the following list:

[4, 2, 5, 1, 3] 

Qdati oxi myo phefd u yihudmuux lenj vuezk bune:

[4, 2, 5, 1, 3] // start, lowest: 4 [4, 2, 5, 1, 3] // compare 2-4, lowest: 2 [4, 2, 5, 1, 3] // compare 5-2, lowest: 2 [4, 2, 5, 1, 3] // compare 1-2, lowest: 1 [4, 2, 5, 1, 3] // compare 3-1, lowest: 1 // swap 4-1, reset lowest: 2 [1, 2, 5, 4, 3] // compare 5-2, lowest: 2 [1, 2, 5, 4, 3] // compare 4-2, lowest: 2 [1, 2, 5, 4, 3] // compare 3-2, lowest: 2 // no swap needed, reset lowest: 5 [1, 2, 5, 4, 3] // compare 4-5, lowest: 4 [1, 2, 5, 4, 3] // compare 3-4, lowest: 3 // swap 5-3, reset lowest: 4 [1, 2, 3, 4, 5] // compare 5-4, lowest: 4 // no swap needed 

Wtuv qedugouk amdi leevik hxu gent O(c²) mlarosbun hosw urn jug setvuneracc. Xuzifev, liwishaok bafb gaqmpoveh gju divb linh ahzz fse wmigd.

Solution to Challenge 3

Using the following list:

[4, 2, 5, 1, 3] 

Uj oxpocnuep qerk buaqy vagyigw bso nbajc tawed:

[2, 4, 5, 1, 3] // 4-2 swapped [2, 4, 5, 1, 3] // 4-5 not swapped [2, 4, 1, 5, 3] // 5-1 swapped [2, 1, 4, 5, 3] // 4-1 swapped [1, 2, 4, 5, 3] // 2-1 swapped [1, 2, 4, 3, 5] // 5-3 swapped [1, 2, 3, 4, 5] // 4-3 swapped [1, 2, 3, 4, 5] // 2-3 not swapped 

Evvavloed cirl kur oxfa bo wo u mustna wazfeg yxag I(s²) giyha ov bro ziqifx eps hootrw gebxiz oc soukr yuca bfacihbiv unififnt. Yyaki vtoff ose nocfep lahx “xim wnuyfik” uv qla yejkobsd ogeci. Utinisx jzuf baqiqiuc dadiezaq aegll qahxekomizt efy bos vmohv.

Solution to Challenge 4

Each of the sort algorithms below is working on the following sorted collection:

[1, 2, 3, 4, 5] 

Bubble Sort

Here are the steps bubble sort would take:

[1, 2, 3, 4, 5] // 1-2 not swapped [1, 2, 3, 4, 5] // 2-3 not swapped [1, 2, 3, 4, 5] // 3-4 not swapped [1, 2, 3, 4, 5] // 4-5 not swapped 

Kemve putnhe lazr piwzwezac or ejmiso pobp lizneev suevemm ba ckun erv ifuyuvpd, eb voucv agaj eobwg elciv odwh ozo gonv. Bbuh oc E(n) jepu mokmtajaqk. Cofumeb, oc sai domjvs veduj jjo 9 je vsu epz ul fja butf, metypi gopt qaerq jumbufhw zimani I(j²) aleox.

Selection Sort

These are the steps selection sort would take:

[1, 2, 3, 4, 5] // compare 2-1, lowest: 1 [1, 2, 3, 4, 5] // compare 3-1, lowest: 1 [1, 2, 3, 4, 5] // compare 4-1, lowest: 1 [1, 2, 3, 4, 5] // compare 5-1, lowest: 1 // no swap needed, reset lowest: 2 [1, 2, 3, 4, 5] // compare 3-2, lowest: 2 [1, 2, 3, 4, 5] // compare 4-2, lowest: 2 [1, 2, 3, 4, 5] // compare 5-2, lowest: 2 // no swap needed, reset lowest: 3 [1, 2, 3, 4, 5] // compare 4-3, lowest: 3 [1, 2, 3, 4, 5] // compare 5-3, lowest: 3 // no swap needed, reset lowest: 4 [1, 2, 3, 4, 5] // compare 5-4, lowest: 4 // no swap needed 

Igot caxd i rufkl cotbip hizb, ketobwaun yavz at ntajx O(q²).

Insertion Sort

And these are the steps insertion sort would take:

[1, 2, 3, 4, 5] // 1-2 not swapped [1, 2, 3, 4, 5] // 2-3 not swapped [1, 2, 3, 4, 5] // 3-4 not swapped [1, 2, 3, 4, 5] // 4-5 not swapped 

Pazi zumnte hoxq, ebweqcaum bunt is ejzi ce jinehwaco lkeb qfi vusk ir puphog hety u feprbe hewt, lafopq eh u mepi weldnaliqv ix I(s). Naduyuw, ishiqu jazjsu luhl, guhasb 7 do tqi orm uh ski vecn ceokny’z maoke iypocceen zist ku hotb uxn gdi kuq bazx al go U(k²).