[go: up one dir, main page]
Scribd
Upload
230 views25 pages

Quick Sort: Algorithms and Data Structures

Quicksort is one of the most widely used sorting algorithms. It works by recursively partitioning the array around pivot points and sorting the subarrays. It has average case performance of O(n log n) but worst case of O(n^2). Variations include choosing better pivot points like the median to improve performance. Quicksort is used in many applications due to its simplicity, speed, and ability to sort in-place without extra memory.

Uploaded by

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

Quick Sort: Algorithms and Data Structures

Quicksort is one of the most widely used sorting algorithms. It works by recursively partitioning the array around pivot points and sorting the subarrays. It has average case performance of O(n log n) but worst case of O(n^2). Variations include choosing better pivot points like the median to improve performance. Quicksort is used in many applications due to its simplicity, speed, and ability to sort in-place without extra memory.

Uploaded by

Haris Muhibic
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 25

Quick Sort

Algorithms and Data Structures

Dino KECO
Agenda
 quick sort
 selection
 duplicate keys
 system sorts
Two classic sorting algorithms:
merge sort and quick sort
Critical components in the world’s computational infrastructure.
 Full scientific understanding of their properties has enabled us to
develop them into practical system sorts.
 Quick sort honored as one of top 10 algorithms of 20th century in
science and engineering.
Quick Sort
Basic plan.
 Shuffle the array.
 Partition so that, for some j
 entry a[j] is in place

 no larger entry to the left of j

 no smaller entry to the right of j

 Sort each subarray recursively.


Quick Sort – important people
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].
Quick Sort partitioning
Repeat until i and j pointers cross.
 Scan i from left to right so long as (a[i] < a[lo]).
 Scan j from right to left so long as (a[j] > a[lo]).
 Exchange a[i] with a[j].

When pointers cross.


 Exchange a[lo] with a[j].

This was Sadgewick 2-way partitioning, there are other strategies like
 Dijkstra 3-way partitioning
 Bentley-McIlroy 3-way partitioning
 dual-pivot partitioning
Quick Sort: Java code for
partitioning
Quick Sort: Java implementation
Quick Sort: implementation details

 Partitioning in-place. Using an extra array makes


partitioning easier, but is not worth the cost.
 Terminating the loop. Testing whether the
pointers cross is trickier than it might seem.
 Equal keys. When duplicates are present, it is
(counter-intuitively) better to stop scans on keys
equal to the partitioning item's key.
 Preserving randomness. Shuffling is needed for
performance guarantee.
 Equivalent alternative. Pick a random
partitioning item in each subarray.
Quick Sort analysis

 Best case.
Number of compares is ~ N log N.

 Worst case.
Number of compares is ~ ½ N2 .
Quick Sort: practical
improvements
Insertion sort small subarrays.
 Even quick sort has too much overhead for tiny
subarrays.
 Cutoff to insertion sort for ≈ 10 items

Median of sample.
 Best choice of pivot item = median.
 Estimate true median by taking median of
sample.
 Median-of-3 (random) items
Selection
Goal. Given an array of N items, find the k th smallest item.
Ex. Min (k = 0), max (k = N - 1), median (k = N/ 2).

Applications.
 Order statistics.

 Find the "top k."

Use theory as a guide.


 Easy N log N upper bound. How?

 Easy N upper bound for k = 1, 2, 3. How?

 Easy N lower bound. Why?

Which is true?
 N log N lower bound?

 N upper bound?
Duplicate keys

 Often, purpose of sort is to bring items with equal


keys together.
 Sort population by age.
 Remove duplicates from mailing list.
 Sort job applicants by college attended.

 Typical characteristics of such applications.


 Huge array.
 Small number of key values
Duplicate keys
 What is the result of partitioning the following
array (skip over equal keys)?
Duplicate keys: partitioning
strategies
 Bad. Don't stop scans on equal keys.
[ ~ ½ N2 compares when all keys equal ]

 Good. Stop scans on equal keys.


[ ~ N lg N compares when all keys equal ]

 Better. Put all equal keys in place. How?


 [ ~ N compares when all keys equal ]
 Dijkstra 3-way partitioning
Sorting applications
Sorting algorithms are essential in a broad variety of applications:
 Sort a list of names.

 Organize an MP3 library.


 Display Google PageRank results.
 List RSS feed in reverse chronological order.

 Find the median.


 Identify statistical outliers.
 Binary search in a database.
 Find duplicates in a mailing list.

 Data compression.
 Computer graphics.
 Computational biology.
 Load balancing on a parallel computer.
...
Questions?

You might also like