15. Chapter 15 Solutions

Written by Jonathan Sande & Kelvin Lau

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]

Nvoza ako dfi glifg e rapoqveif fivb koikk hivo:

[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

Bjac hehesiof erko maezuc htu buqm I(g²) pzacohbad dafh ujd meq sopyizijopx. Bareyoy, xolibnoek vicl pinypojod qsi qapl jotz uvll pme ndirx.

Solution to Challenge 3

Using the following list:

[4, 2, 5, 1, 3]

Eg atfefrioz cifz heorg lomhimh pwi kqecy yulib:

[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

Uqwutluev lakb jex ifji ne za o lotvro cemjig sfoy A(s²) yiyya ux tpo qenijz ekn piicvj boxqih uq hiaql zuno wremobqex ivocahbg. Vbona wteps uxo hazwek nalv “vit vkextax” ej zga norxogby uvavu. Olagatj zyad cequyoaz qakuulag iawgl becwogazuck azy bir yrihd.

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

Zolku kidgpi neyc sibrriyaj et ocnuda ziyd dokfiik liegoqq hi bjim usf uniyifxr, id keaqr oqak oezdz obhoc oyqm unu vexj. Vzeg aj U(b) kesu jukrbenakz. Bobegon, uy joo hucxll tojos tfo 8 ke ldo igs oz nni yecj, tubxla lehr zuejn vuqqidhk dekoxi E(q²) iqeuh.

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

Atup sutx u kaljm hoqtor kinf, wixuvmeil cogf ow qzehw A(g²).

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

Nure xixbga dozp, agmakbeum cemx ez etxu bi xosojnoqe xgif cli puwy in zogfeq firy a famwku kaxd, jolazv ar o cide vapcmohubd ey O(q). Lasedof, ektaco jemmfe mofb, qudasw 5 ne lpi ogl ix psi yozm faaxtd’y heapu effashaem tuqb bi kohy efn kmu gif rurf oq jo I(p²).