1(6 points) Sort the array

7

4

1

6

2

3

8

5

using Bubble Sort . Show the results after each pass in the table below. Explain, briefly, what happened next to each row.

0	1	2	3	4	5	6	7	index
7	4	1	6	2	3	8	5	original array
4	1	6	2	3	7	5	8	7 bubbles up to position 5 8 bubbles up to position 7
1	4	2	3	6	5	7	8	4 bubbles up to position 1 6 bubbles up to position 4 7 bubbles up to position 6
1	2	3	4	5	6	7	8	4 bubbles up to position 3 6 bubbles up to position 5 the array is now sorted
1	2	3	4	5	6	7	8	these passes happen anyway
1	2	3	4	5	6	7	8	these passes happen anyway
1	2	3	4	5	6	7	8	these passes happen anyway
1	2	3	4	5	6	7	8	these passes happen anyway

2(6 points) Sort the array

7

4

1

6

2

3

8

5

using Insertion Sort . Show the results after each pass in the table below. Explain, briefly, what happened next to each row.

0	1	2	3	4	5	6	7	index
7	4	1	6	2	3	8	5	original array
4	7	1	6	2	3	8	5	A[1] = 4 is sifted into place
1	4	7	6	2	3	8	5	A[2] = 1 is sifted into place
1	4	6	7	2	3	8	5	A[3] = 6 is sifted into place
1	2	4	6	7	3	8	5	A[4] = 2 is sifted into place
1	2	3	4	6	7	8	5	A[5] = 3 is sifted into place
1	2	3	4	6	7	8	5	A[6] = 8 is sifted into place (stays put)
1	2	3	4	5	6	7	8	A[7] = 5 is sifted into place

3(6 points) Sort the array

7

4

1

6

2

3

8

5

using Selection Sort .
Show the results after each pass in the table below. Explain, briefly, what happened next to each row.

0	1	2	3	4	5	6	7	index
7	4	1	6	2	3	8	5	original array
1	4	7	6	2	3	8	5	1 swapped into position 0
1	2	7	6	4	3	8	5	2 swapped into position 1
1	2	3	6	4	7	8	5	3 swapped into position 2
1	2	3	4	6	7	8	5	4 swapped into position 3
1	2	3	4	5	7	8	6	5 swapped into position 4
1	2	3	4	5	6	8	7	6 swapped into position 5
1	2	3	4	5	6	7	8	7 swapped into position 6

4(8 points) Sort the array

7

4

1

6

2

3

8

5

using Quick Sort .
Select the pivot from the midpoint in the list. For each pass, show the results after each pass in the table below and indicate (on the right) all exchanges that move a corresponding pair of elements in the lower and upper sublist.

0	1	2	3	4	5	6	7	index
7	4	1	6	2	3	8	5	original array
5	4	1	3	2	6	8	7	lower = 0 Upper = 7 pivot = 6
1	4	5	3	2	6	8	7	lower = 0 Upper = 4 pivot = 1
1	4	2	3	5	6	8	7	lower = 1 Upper = 4 pivot = 5
1	2	4	3	5	6	8	7	lower = 1 Upper = 3 pivot = 2
1	2	3	4	5	6	8	7	lower = 2 Upper = 3 pivot = 4
1	2	3	4	5	6	7	8	lower = 5 Upper = 7 pivot = 8
1	2	3	4	5	6	7	8	lower = 5 Upper = 6 pivot = 6

Last Updated: June 1, 1997 11:24 am by