Scribd
Upload
3 views2 pages

Quick Sort Algorithm Homework Guide

The document provides a homework assignment on Quick Sort, detailing its algorithm steps, recursive sorting process on a sample list, and advantages of the median-of-three pivot selection. It also outlines the time complexities for best, average, and worst cases, and compares Quick Sort with Merge Sort regarding algorithm type, time complexity, and space usage. Quick Sort is efficient but can degrade in performance, while Merge Sort is more consistent but requires more memory.

Uploaded by

17adarao
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views2 pages

Quick Sort Algorithm Homework Guide

The document provides a homework assignment on Quick Sort, detailing its algorithm steps, recursive sorting process on a sample list, and advantages of the median-of-three pivot selection. It also outlines the time complexities for best, average, and worst cases, and compares Quick Sort with Merge Sort regarding algorithm type, time complexity, and space usage. Quick Sort is efficient but can degrade in performance, while Merge Sort is more consistent but requires more memory.

Uploaded by

17adarao
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

A Level Computer Science – Quick Sort Homework

Answer all questions. Show all working where applicable. Total: 20 marks.

Question 1 (4 marks)
Explain the main steps of the Quick Sort algorithm.

The Quick Sort algorithm begins by selecting a pivot element from the list, which
can be chosen from various positions, such as the first or last element or even
the median of three elements. Once the pivot is selected, the next step is
partitioning the list by rearranging the elements so that all those less than the
pivot are positioned to its left, while those greater than the pivot are placed to its
right. After partitioning, the Quick Sort algorithm is applied recursively to the two
resulting sublists on either side of the pivot. Finally, the sorted list is created by
combining these sorted sublists along with the pivot itself, resulting in a fully
sorted array.

Question 2 (5 marks)
Perform Quick Sort on the list [7, 2, 9, 1, 5] using the first element as the pivot.
Show all recursive steps.

Initial list: [7, 2, 9, 1, 5] → Pivot = 7


1. Partition: [2, 1, 5] | 7 | [9]
Left sublist [2, 1, 5] → Pivot = 2
1. Partition: [1] | 2 | [5]
Left of 2: [1] → Already sorted
1. Right of 2: [5] → Already sorted
2. Right sublist [9] → Already sorted
Final sorted list: [1, 2, 5, 7, 9]

Question 3 (4 marks)
What is the advantage of using the median-of-three method to select the pivot in
Quick Sort?

Reduces the chance of worst-case performance by selecting a pivot closer to the


median value. It helps to balance partitions, particularly in nearly sorted or
reverse-sorted lists, thereby improving the efficiency and stability of Quick Sort in
practice.

Question 4 (3 marks)
State the best case, average case, and worst-case time complexities of Quick
Sort.
Best case: (O(n log n)) — balanced partitions.

Average case: (O(n log n)) — typical performance.

Worst case: (O(n^2)) — highly unbalanced partitions (e.g., sorted list with a poor
pivot choice).

Question 5 (4 marks)
Compare Quick Sort and Merge Sort in terms of:
(a) Algorithm type,
(b) Time complexity, and
(c) Space usage.

When comparing Quick Sort and Merge Sort, both use the divide and conquer
strategy, but they differ in implementation and performance. Quick Sort is an in-
place algorithm, which means it uses low memory and has a best and average
case time complexity of O(n log n), though it can degrade to O(n^2) in the worst
case. Merge Sort requires additional memory, leading to higher space usage, but
it maintains a consistent time complexity of O(n log n) across all cases, making it
more reliable in performance.

You might also like