Scribd
Upload
9 views13 pages

Quick Sort: Pros, Cons, and Comparisons

Quicksort is a sorting algorithm that works by picking a pivot element and partitioning the array into two subarrays of elements less than and greater than the pivot. It then recursively applies this process to each subarray until the entire array is sorted. It has average-case performance of O(n log n) but worst-case of O(n^2) if the pivot is always the smallest or largest element. It is generally faster than mergesort but lacks its guaranteed O(n log n) runtime.

Uploaded by

Joseph_Nuamah
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
9 views13 pages

Quick Sort: Pros, Cons, and Comparisons

Quicksort is a sorting algorithm that works by picking a pivot element and partitioning the array into two subarrays of elements less than and greater than the pivot. It then recursively applies this process to each subarray until the entire array is sorted. It has average-case performance of O(n log n) but worst-case of O(n^2) if the pivot is always the smallest or largest element. It is generally faster than mergesort but lacks its guaranteed O(n log n) runtime.

Uploaded by

Joseph_Nuamah
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Quick Sort

Basic Idea
Advantages and Disadvantages
Applications
Comparison with Heap sort
and Merge sort

1
Basic Idea
 Pick one element in the array, which will
be the pivot.
 Make one pass through the array, called a
partition step, re-arranging the entries so
that:
• entries smaller than the pivot are to the left
of the pivot.
• entries larger than the pivot are to the right

2
Basic Idea
 Recursively apply quicksort to the part of
the array that is to the left of the pivot, and
to the part on its right.

 No merge step, at the end all the elements


are in the proper order

3
Choosing the Pivot
Some fixed element: e.g. the first, the
last, the one in the middle.
Bad choice - may turn to be the
smallest or the largest element, then
one of the partitions will be empty
Randomly chosen (by random generator)
- still a bad choice

4
Choosing the Pivot

The median of the array


(if the array has N numbers, the
median is the [N/2] largest number).

This is difficult to compute - increases


the complexity.

5
Choosing the Pivot

The median-of-three choice:


take the first, the last and the
middle element.

Choose the median of these three


elements.

6
Complexity of Quick Sort
Average-case O(NlogN)
Worst Case: O(N2)
This happens when the pivot is the
smallest (or the largest) element.
Then one of the partitions is
empty, and we repeat recursively
the procedure for N-1 elements.
7
Complexity of Quick Sort
Best-case O(NlogN)
The pivot is the median of the array,
the left and the right parts have same
size.
There are logN partitions, and to
obtain each partitions we do N
comparisons (and not more than N/2
swaps). Hence the complexity is
O(NlogN) 8
Advantages and
Disadvantages
 Advantages:
 One of the fastest algorithms on average
 Does not need additional memory (the
sorting takes place in the array - this is
called in-place processing )
 Disadvantages:
 The worst-case complexity is O(N2)

9
Applications
Commercial applications

 QuickSort generally runs fast


 No additional memory
 The above advantages compensate for
the rare occasions when it runs with O(N2)

10
Warning:
Applications
Never use in applications which require a guarantee
of response time:
 Life-critical
(medical monitoring,
life support in aircraft, space craft)
    Mission-critical
(industrial monitoring and control in handling
dangerous materials, control for aircraft, defense,
etc)
unless you assume the worst-case
response time
11
Comparison with Heap Sort
 O(NlogN) complexity
 quick sort runs faster, (does not
support a heap tree)
 the speed of quick sort is not
guaranteed

12
Comparison with Merge Sort
 Merge sort guarantees O(NlogN) time
 Merge sort requires additional memory
with size N
 Usually Merge sort is not used for main
memory sorting, only for external memory
sorting

13

You might also like