Scribd
Upload
6 views9 pages

Quick Sort Algorithm Explained

The document discusses the Quick Sort algorithm, which is a divide and conquer strategy for sorting an array by selecting a pivot element and rearranging the array based on it. It outlines the recursive nature of the algorithm, including the partitioning process and the complexity analysis, indicating best and average cases of O(n log n) and worst case of O(n^2). Additionally, it emphasizes the importance of recursive problem-solving strategies in algorithm design.

Uploaded by

Ahmed Al-Afandi
Copyright
© All Rights Reserved
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
6 views9 pages

Quick Sort Algorithm Explained

The document discusses the Quick Sort algorithm, which is a divide and conquer strategy for sorting an array by selecting a pivot element and rearranging the array based on it. It outlines the recursive nature of the algorithm, including the partitioning process and the complexity analysis, indicating best and average cases of O(n log n) and worst case of O(n^2). Additionally, it emphasizes the importance of recursive problem-solving strategies in algorithm design.

Uploaded by

Ahmed Al-Afandi
Copyright
© All Rights Reserved
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

By: HMA
RECAP: Divide and Conquer
Algorithms
This term refers to recursive problem-solving strategies
in which 2 cases are identified:

• A case for a direct (non recursive) solution


• A case for a recursive solution containing the
following elements:

 Dividing the input into smaller problems


Finding recursive solutions for smaller
problems
Combining the solutions for the smaller
problems
Divide and Conquer Algorithms
Suppose we want to add the elements in an array A[1…N]

Add(A : array, min, max)


1. If min = max then return A[min]
Direct solution
2. If min > max then return 0
Dividing input 3. mid  floor((min+max)/ 2)
4. FirstHalf  Add(A,min, mid - 1)
Solve smaller
5. SecondHalf  Add(A, mid + 1,max)
Combining 6. Return FirstHalf + SecondHalf + A[mid]
solutions

Complexity
Complexity==O(Dir)
O(Dir)++O(Div)
O(Div)++O(Smaller)
O(Smaller)++O(Combining)
O(Combining)
Quicksort
• An element of the array is chosen. We call it the pivot
element.

• The array is rearranged such that


- all the elements smaller than the pivot are moved
before it
- all the elements larger than the pivot are moved
after it

• Then Quicksort is called recursively for these two parts.


Example

A [3 8 5 2 7 1 6 4]
Quicksort - Algorithm

Quicksort (A[L..R])
if L < R then
pivot = Partition( A[L..R])
Quicksort (A[1..pivot-1])
Quicksort (A[pivot+1...R)
Partition Algorithm
Partition (A[L..R])
p  A[L]; i  L; jR+1

while (i < j) do {
Questions:
repeat i  i + 1 until A[i] ≥ p
repeat j  j  1 until A[j] ≤ p •Why not choose
if (i < j) then swap(A[i], A[j]) for p the middle
} position in the
array?
swap(A[j],A[L])
return j •Complexity?
Example (again)

A [3 8 5 2 7 1 6 4]
Complexity Analysis
• Best Case: every partition splits half of the array
T(n) = n + 2T(n/2)
T(1) = 1

O(n log2n)
• Worst Case:
one array is empty; one has all elements
O(n2 ) T(n) = n + T(n-1)
T(1) = 1

• Average case:
O(n log2n)

You might also like