Solved Assignment: Quick Sort, Merge Sort, and Heap Sort Algorithm Exercises with C++ Code Examples

 Question 1 (25 pts): Quick Sort with Middle Pivot

Assume the following list of keys:
49, 4, 89, 25, 67, 46, 83, 30, 60, 22, 12

This list is to be sorted using the quick sort algorithm as discussed in this chapter.
Use the pivot as the middle element of the list, and fill in the blank squares below.

(pivotpivot pivotpivot pivot pivot pivotpivot pivotpivot pivot)

---

Question 2 (25 pts): Merge Sort

Assume the following list of keys:
32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51

This list is to be sorted using the merge sort algorithm as discussed in this chapter.
Fill in the blank squares below.

---

Question 3 (25 pts): Heap Sort

Assume the following list:
32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51, 14, 26, 5

(a) Using the function buildHeap as given in this chapter, convert the list into a heap.
(b) Show the resulting list after three passes of heapsort. (Use the heapify procedure as given in this chapter.)

• One pass:

• Two passes:

• Three passes:

---

Question 4 (25 pts): Quick Sort with Median Pivot (Programming)

Modify the quick sort implementation in the textbook to sort the array using the pivot as the median of the first, last, and middle elements of the array.

Add the modified quick sort implementation to the arrayListType class provided (arrayListType.h).
Ask the user to enter a list of positive integers ending with -999, sort the integers, and display the pivots for each iteration and the sorted array.

Submit the source code, and copy and paste the screenshot of the output here.

Solution

Question 1: Quick Sort Using Middle Element as Pivot

Given List:

49, 4, 89, 25, 67, 46, 83, 30, 60, 22, 12

---

Step-by-Step Solution:

Step 1: First Partition

• List: 49, 4, 89, 25, 67, 46, 83, 30, 60, 22, 12

• Middle index: (0 + 10) // 2 = 5 → Pivot = 46

Partitioning around 46:

• Numbers less than 46: 4, 25, 30, 22, 12

• Pivot: 46

• Numbers greater than 46: 49, 89, 67, 83, 60

After partition:
4, 25, 30, 22, 12, 46, 49, 89, 67, 83, 60

---

Step 2: Left Sublist (4, 25, 30, 22, 12)

• Sublist: 4, 25, 30, 22, 12

• Middle index: (0 + 4) // 2 = 2 → Pivot = 30

Partitioning around 30:

• Less than 30: 4, 25, 22, 12

• Pivot: 30

• Greater than 30: None

Result:
4, 25, 22, 12, 30

---

Step 3: Left Sublist (4, 25, 22, 12)

• Sublist: 4, 25, 22, 12

• Middle index: (0 + 3) // 2 = 1 → Pivot = 25

Partitioning around 25:

• Less than 25: 4, 22, 12

• Pivot: 25

• Greater than 25: None

Result:
4, 22, 12, 25

---

Step 4: Left Sublist (4, 22, 12)

• Sublist: 4, 22, 12

• Middle index: (0 + 2) // 2 = 1 → Pivot = 22

Partitioning around 22:

• Less than 22: 4, 12

• Pivot: 22

• Greater than 22: None

Result:
4, 12, 22

---

Step 5: Left Sublist (4, 12)

• Sublist: 4, 12

• Middle index: (0 + 1) // 2 = 0 → Pivot = 4

Partitioning around 4:

• Less than 4: None

• Pivot: 4

• Greater than 4: 12

Result:
4, 12

Now, put it all together (left side):
4, 12, 22, 25, 30

---

Right Sublist (49, 89, 67, 83, 60)

• Sublist: 49, 89, 67, 83, 60

• Middle index: (6 + 10) // 2 = 8 → Pivot = 67

Partitioning around 67:

• Less than 67: 49, 60

• Pivot: 67

• Greater than 67: 89, 83

Result:
49, 60, 67, 89, 83

---

Right Sublist (89, 83)

• Sublist: 89, 83

• Middle index: (9 + 10) // 2 = 9 → Pivot = 89

Partitioning around 89:

• Less than 89: 83

• Pivot: 89

Result:
83, 89

---

Sorted Right Side:
49, 60, 67, 83, 89

---

Combine all:
4, 12, 22, 25, 30, 46, 49, 60, 67, 83, 89

---

Summary Table for Pivots (Each Partition):

Partition	Pivot
49, 4, 89, ... , 12	46
4, 25, 30, 22, 12	30
4, 25, 22, 12	25
4, 22, 12	22
4, 12	4
49, 89, 67, 83, 60	67
49, 60	60
89, 83	89

---

Question 2: Merge Sort

Given List:

32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51

Step-by-Step Solution:

Merge sort divides the list into halves recursively, then merges sorted halves.

Splitting:

• First half: 32, 47, 3, 28, 92, 7, 87, 37

• Second half: 22, 43, 40, 74, 13, 35, 51

Keep splitting until single elements:

First half → [32, 47, 3, 28], [92, 7, 87, 37]
Then further → [32, 47], [3, 28], [92, 7], [87, 37]
and so on...

Merging (Sorting):

• Merge [32], [47] → [32, 47]

• Merge [3], [28] → [3, 28]

• Merge [32, 47], [3, 28] → [3, 28, 32, 47]

• Merge [92], [7] → [7, 92]

• Merge [87], [37] → [37, 87]

• Merge [7, 92], [37, 87] → [7, 37, 87, 92]

• Merge [3, 28, 32, 47], [7, 37, 87, 92] → [3, 7, 28, 32, 37, 47, 87, 92]

Repeat for the second half...

• Merge [22], [43] → [22, 43]

• Merge [40], [74] → [40, 74]

• Merge [22, 43], [40, 74] → [22, 40, 43, 74]

• Merge [13], [35] → [13, 35]

• [13, 35], [51] → [13, 35, 51]

• [22, 40, 43, 74], [13, 35, 51] → [13, 22, 35, 40, 43, 51, 74]

Final merge:

• [3, 7, 28, 32, 37, 47, 87, 92], [13, 22, 35, 40, 43, 51, 74]
  → [3, 7, 13, 22, 28, 32, 35, 37, 40, 43, 47, 51, 74, 87, 92]

---

Question 3: Heap Sort

Given List:

32, 47, 3, 28, 92, 7, 87, 37, 22, 43, 40, 74, 13, 35, 51, 14, 26, 5

(a) Build Heap:

• Heapify the list into a max heap (largest element at root).

• After building, the array becomes:

92, 47, 87, 37, 51, 74, 35, 32, 22, 43, 40, 7, 13, 3, 28, 14, 26, 5

---

(b) Three Passes of Heap Sort:

One Pass:
Swap 92 (root) with 5 (last), heapify remaining:

• 87, 47, 74, 37, 51, 40, 35, 32, 22, 43, 5, 7, 13, 3, 28, 14, 26, 92

Two Passes:
Swap 87 (root) with 26 (last unsorted), heapify remaining:

• 74, 47, 51, 37, 26, 40, 35, 32, 22, 43, 5, 7, 13, 3, 28, 14, 87, 92

Three Passes:
Swap 74 (root) with 14, heapify remaining:

• 51, 47, 40, 37, 26, 28, 35, 32, 22, 43, 5, 7, 13, 3, 14, 74, 87, 92

---

Question 4: Modified Quick Sort (Median-of-Three Pivot) — C++ Code Example

Task:
Modify quick sort to use the median of the first, middle, and last element as the pivot. Add this to arrayListType, get user input (ends with -999), and display pivots and sorted array.

---

Sample Implementation (Pseudo-code/Code):

cpp
// Add to arrayListType
int medianOfThree(int low, int high) {
    int mid = (low + high) / 2;
    if ((list[low] < list[mid] && list[mid] < list[high]) || (list[high] < list[mid] && list[mid] < list[low]))
        return mid;
    else if ((list[mid] < list[low] && list[low] < list[high]) || (list[high] < list[low] && list[low] < list[mid]))
        return low;
    else
        return high;
}

int partition(int low, int high) {
    int pivotIndex = medianOfThree(low, high);
    int pivot = list[pivotIndex];
    swap(list[pivotIndex], list[high]); // move pivot to end
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (list[j] < pivot) {
            i++;
            swap(list[i], list[j]);
        }
    }
    swap(list[i + 1], list[high]);
    return i + 1;
}

void quickSortMedian(int low, int high) {
    if (low < high) {
        int p = partition(low, high);
        cout << "Pivot: " << list[p] << endl;
        quickSortMedian(low, p - 1);
        quickSortMedian(p + 1, high);
    }
}

User interaction:

• Ask user for numbers (ends with -999)

• Print pivots at each step

• Print sorted array at the end

Example Output:

Enter numbers: 12 6 8 22 3 -999
Pivot: 8
Pivot: 3
Pivot: 12
Pivot: 22
Sorted: 3 6 8 12 22

---

Summary

• Quick Sort: Sort the list by always picking the middle element as the pivot.

• Merge Sort: Repeatedly split and merge; final list is sorted.

• Heap Sort: Convert list to max heap, swap and heapify; show result after each pass.

• Modified Quick Sort: Use median-of-three as pivot; display pivots and sorted result.

📩 Need a similar solution? Email me: adel455@hotmail.com