Sorting

---

Q) Selection Sort

Consider the following unsorted array of integers:

int data[] {8, 2, 9, 4, 1, 7};

If we were to do one pass on this array with selection sort, what value would be in the first element of the array (data[0])? By "one pass", I mean one of the steps as shown in the slides.

a) 8
b) 2
c) 9
d) 1

Q) Insertion Sort

Consider the following unsorted array of integers:

int data[] {8, 2, 9, 4, 1, 7};

If we were to do one pass on this array with insertion sort, what value would be in the first element of the array (data[0])? By "one pass", I mean one of the steps as shown in the slides.

a) 8
b) 2
c) 9
d) 1

Q) Fewest Swaps on Selection Sort

Imagine that you are using selection sort to sort an array of data.

Which of the following arrays will generate the fewest swap operations?

To answer this question, consider each array below and decide how many values in the array would be moved when using selection sort. Only count it when a number is moved to a new location in the array. For example, "swapping" the value already in index i into index i does not count as a swap because it doesn't actually move.

int a[] {9, 8, 6, 4, 2, 1};
    int b[] {8, 7, 1, 9, 4, 3};  
    int c[] {9, 5, 7, 3, 8, 4};  
    int d[] {9, 1, 2, 3, 4, 5};

---

Answers

1 = d) a 1 because it picks the best element and swaps it into place.
2 = d) 2 because insertion sort picks the next element and puts it into sorted order.
3 = a) because swapping 1 will also swap 9, thus putting both in the right spot.