Hey everyone,
I really need help to solve this one question from the 2014 HSC paper (question is attached as an image).
Quick Version: I can't figure out how to produce the answer (D) using any of the 3 sorting methods we're taught
Question: What will the 2nd pass produce?
Initial: 4 2 8 5 7 1
1st Pass: 4 2 8 5 7 1
My Working:
(Note: Insertion sorts always assume one item is already sorted)
Using Insertion (Moving from left to right)
Initial: 4 * 2 8 5 7 1
1st Pass: 2 4 * 8 5 7 1
2nd Pass: 2 4 8 * 5 7 1
3rd Pass: 2 4 5 8 * 7 1
4th Pass: 2 4 5 7 8 * 1
LastPass: 1 2 4 5 7 8 *
Using Insertion (Moving from right to left)
Initial: 4 2 8 5 7 * 1
1st Pass: 2 4 8 5 * 7 1
2nd Pass: 2 4 8 * 7 5 1
3rd Pass: 2 4 * 8 7 5 1
4th Pass: 2 * 8 7 5 4 1
LastPass: * 8 7 5 4 2 1
Therefore, it can't be insertion.
Using selection (moving biggest to left)
Initial: * 4 2 8 5 7 1
1st Pass: 8 * 2 4 5 7 1
2nd Pass: 8 7 * 4 5 2 1
3rd Pass: 8 7 5 * 4 2 1
4th Pass: 8 7 5 4 * 2 1
LastPass: 8 7 5 4 2 1 *
Using selection (moving smallest to left)
Initial: * 4 2 8 5 7 1
1st Pass: 1 * 2 8 5 7 4
2nd Pass: 1 2 * 8 5 7 4
3rd Pass: 1 2 4 * 5 7 8
4th Pass: 1 2 4 5 * 7 8
5th Pass: 1 2 4 5 7 * 8
LastPass: 1 2 4 5 7 8 *
Thus, it can't be selection sort.
Using Bubblesort (selecting biggest moving left to right)
Initial:
4 2 8 5 7 1
1st Pass:
[2 4] 8 5 7 1
2 [4 8] 5 7 1
2 4 [5 8] 7 1
2 4 5 [7 8] 1
2 4 5 7 [1 8]
Using Bubblesort (selecting smallest moving left to right)
Initial:
4 2 8 5 7 1
1st Pass:
[4 2] 8 5 7 1
4 [8 2] 5 7 1
4 8 [5 2] 7 1
4 8 5 [7 2] 1
4 8 5 7 [2 1]
Using Bubblesort (selecting biggest moving right to left)
Initial:
4 2 8 5 7 1
1st Pass:
4 2 8 5 [7 1]
4 2 8 [7 5] 1
4 2 [8 7] 5 1
4 [8 2] 7 5 1
[8 4] 2 7 5 1
Using Bubblesort (selecting smallest moving right to left)
Initial:
4 2 8 5 7 1
1st Pass:
4 2 8 5 [1 7]
4 2 8 [1 5] 7
4 2 [1 8] 5 7
4 [1 2] 8 5 7
[1 4] 2 8 5 7
None of them produce 4 2 8 5 7 1 after the first pass. The bubble sort (biggest right to left/smallest left to right) does after the first part of the first pass, but none produce the correct answer for 2nd pass: 8 4 2 5 7 1
Please someone help me out here. I feel like I'm going nuts trying to figure this one out. And it's only worth one mark. Why??!?!?!?