Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

16. Chapter 16 Solutions
Written by Jonathan Sande

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

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]
[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

Solution to Challenge 3

Using the following list:

[4, 2, 5, 1, 3]
[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

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

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

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
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now