**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)**

{

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**

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=7for 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 pivotPerform 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

Choose some element called a pivotPerform 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. / --

--

--

--

--