CSIS 10B Assignment 12 Sorting12 Pts Max

CSIS 10B Assignment 12 Sorting12 pts max

Read Nyhoff Ch13

Exercises 13.2 1, 4, 84 pts

Lab 11.1 Sorting4 pts

(Turn incode for selectionSort and insertionSort

plus your table of sort times on p171)

Project 11.1Sorting Analysis3 pts

Also add the heapSort test times to your table

(Turn in table of sort times including heapSort on p173)

Challenge: Implement and test a merge sort function8 pts

In Class Sort Demos (0 pts)

Show the arrays after several passes (cell 0 is left blank for all arrays)

void bubbleSort(vector<ElementType> & x)
{
int numElements = x.size() - 1;
for (int listSize = numElements; listSize > 1; listSize--)
for (int j = 1; j <= listSize - 1; j++)
if (x[j] > x[j+1])
interchange(x[j], x[j+1]);
} / --- / 67 / 33 / 21 / 84 / 49 / 50 / 75
---
---
---
---
INSERTION SORT (n is 7, last valid position)
For i = 2 to n do the following
a. set NextElement = x[i] and
x[0] = nextElement
b. set j = i
c. While nextElement < x[j – 1] do following
set x[j] equal to x[j – 1]
decrement j by 1
End wile
d. set x[j] equal to nextElement
End for / --- / 67 / 33 / 21 / 84 / 49 / 50 / 75
---
---
---
---
SELECTION SORT (n is 7 last valid position)
For i = 1 to n-1 do the following
a. set smallPos= i and smallest = x[smallPos]
b. For j = i + 1 to n do the following
if x[j] < smallest
set smallPos= j and smallest=x[smallPos]
End for
c. set x[smallPos]= x[i] and x[i]=smallest
End for / --- / 67 / 33 / 21 / 84 / 49 / 50 / 75
---
---
---
---

Heapsort

A) Heapify the array

PERCOLATE DOWN ALGORITHM (n=7, r=3)
1. Set c = 2 * r
2. While c<= n do following
a. If c < n and myArray[c] < myArray[c + 1]
Increment c by 1
b. If myArray[r] < myArray[c]
i. Swap myArray[r] and myArray[c]
ii. set r = c
iii. Set c = 2 * c
else
Terminate repetition
End while
then do again for n=7, r=2
then do again for n=7, r=1 / --- / 67 / 33 / 21 / 84 / 49 / 50 / 75
---
---
---
---

B) Select and re-heapify copy heapified array from above

SELECT AND RE-HEAP the remaining subtree: n=7
for i = n down to 2:
a. Interchange x[1] and x[i]
(puts largest element at end)
b. Apply percolate_down(n=i-1,r=1) to convert binary
tree corresponding to sublist in
x[1] .. x[i-1] /
---
---
---
---

QuickSort

Choose some element called a pivot
Perform a sequence of exchanges so that
All elements that are less than this pivot are to its left and
All elements that are greater than the pivot are to its right.
Divides the (sub)list into two smaller sub lists,
Each of which may then be sorted independently in the same way. / -- / 67 / 33 / 21 / 84 / 49 / 50 / 75 / 99
--
--
--
--

QuickSort on left sublist from above