[go: up one dir, main page]
Scribd
Upload
308 views15 pages

Quick Sort

The document describes the quicksort algorithm. It begins by reviewing insertion sort and merge sort. It then introduces quicksort and discusses its algorithm, which involves choosing a pivot element, partitioning the array around the pivot so that all elements less than the pivot come before it and all elements greater than the pivot come after it, and then recursively applying the same process to the sub-arrays on each side of the pivot. The document provides an example and more details on the partition process. It then analyzes quicksort's time complexity, proving it is O(n log n) on average but O(n^2) in the worst case, and notes it only requires O(1) additional memory.

Uploaded by

Adeel Durrani
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
308 views15 pages

Quick Sort

The document describes the quicksort algorithm. It begins by reviewing insertion sort and merge sort. It then introduces quicksort and discusses its algorithm, which involves choosing a pivot element, partitioning the array around the pivot so that all elements less than the pivot come before it and all elements greater than the pivot come after it, and then recursively applying the same process to the sub-arrays on each side of the pivot. The document provides an example and more details on the partition process. It then analyzes quicksort's time complexity, proving it is O(n log n) on average but O(n^2) in the worst case, and notes it only requires O(1) additional memory.

Uploaded by

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

Design and Analysis of Algorithms

Quicksort

Review of insertion sort and merge


sort
Insertion sort
Algorithm
Worst case number of comparisons =
O(?)

Merge sort
Algorithm
Worst case number of comparisons =
O(?)

Sorting Algorithms
Algorithm

Worst Time

Expected
Time

Extra Memory

Insertion sort

O(1)

Merge sort

O(n)

Quick sort

O(1)

Heap sort

O(1)

Quicksort Algorithm
Input: A[1, , n]
Output: A[1, .., n], where A[1]<=A[2]
<=A[n]
Quicksort:
1. if(n<=1) return;
2. Choose the pivot p = A[n]
3. Put all elements less than p on the left; put all
elements lager than p on the right; put p at the
middle. (Partition)
4. Quicksort(the array on the left of p)
5. Quicksort(the array on the right of p)

Quicksort Algorithm
Quicksort example
2

7
3

1
4

3
7

5
5

6
6

Current pivots

Quicksort

Hi, I am nothing
Nothing
3rd

Previous pivots

Nothing Jr.

Quicksort Algorithm
More detail about partition
Input: A[1, , n] (p=A[n])
Output: A[1,k-1, k, k+1, n], where A[1, , k1]<A[k] and A[k+1, n] > A[k], A[k]=p
Partition:
1. t = the tail of smaller array
2. from i= 1 to n-1{
if(A[i]<p) {
exchange A[t+1] with A[i];
update t to the new tail;
}

3. exchange A[t+1] with A[n];

Quicksort Algorithm
Partition example
tail

Exchange 2 with
A[tail+1]

Do nothing

tail

2
tail

2
tail

Do nothing

Quicksort Algorithm
Partition example
tail

Exchange 1 with
A[tail+1]

Exchange 3 with
A[tail+1]

Do nothing

tail

tail

3
tail

Do nothing

Final step: exchange


A[n] with A[tail+1]

Quicksort Algorithm
The final version of quick sort:
Quicksort(A, p, r){
if(p<r){

//if(n<=1) return;

q = partition(A, p, r); //small ones on left;


//lager ones on
right
Quicksort(A, p, q-1);
Quicksort(A, q+1, r);
}
}

Analysis of Quicksort
Time complexity
Worst case
Expected

Space complexity - extra memory


0 = O(1)

Analysis of Quicksort
Worst

case
The most unbalanced one -- Is it the worst case?
Strict proof
Expected time complexity
Strict proof

Strict proof of the worst case time


complexity

Proof that
1. When n=1, (1)=

2. Hypothesis: when
induction statement: when

Strict proof of the worst case time


complexity

Since ,

Strict proof of the expected time


complexity
Given

A[1, , n], after sorting them


to , the chance for 2 elements, A[i]
and A[j], to be compared is .
The total comparison is calculated
as:

Java implementation of
Quicksort
Professional programmers DO NOT
implement sorting algorithms by themselves
We do it for practicing algorithm
implementation techniques and
understanding those algorithms
Code quicksort
Sort.java // the abstract class
Quicksort_Haydon.java // my quicksort
implementation
SortingTester.java // correctness tester

You might also like