Scribd
Upload
3 views11 pages

Quick Sort Algorithm Overview

Quicksort is a divide and conquer sorting algorithm that efficiently sorts large datasets by partitioning an array around a chosen pivot element. The algorithm involves selecting a pivot, partitioning the array, and recursively sorting the resulting subarrays. While it is efficient and uses minimal additional memory, its performance can degrade with poor pivot selection in sorted data.

Uploaded by

priya.a
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
3 views11 pages

Quick Sort Algorithm Overview

Quicksort is a divide and conquer sorting algorithm that efficiently sorts large datasets by partitioning an array around a chosen pivot element. The algorithm involves selecting a pivot, partitioning the array, and recursively sorting the resulting subarrays. While it is efficient and uses minimal additional memory, its performance can degrade with poor pivot selection in sorted data.

Uploaded by

priya.a
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

QUICK SORT

PRESENTED BY RAMPRASAD B
QUICK SORT

Quicksort is a sorting algorithm based on the divide and


conquer approach where an array is divided into
subarrays by selecting a pivot element.
Quick Sort performs well with large datasets, often faster
than other sorting algorithms.
Quick Sort Algorithm

1. Choose a pivot element.


2. Partition the array around the pivot.
3. Recursively apply Quick Sort to the subarrays on each
side of the pivot.
Pivot selection

The pivot can be chosen in different ways, such as:


a. Last element.
b. Random element.
c. Median of three (first, middle, and last elements).
Partitioning
● After sorting once, the array is partitioned with
respect to the pivot element,.
● The elements on the left which are smaller than
pivot is partition 1 a subarray.
● On the right is partition 2.
● This is done recursively to sort the array.
Program
void quickSort(int arr[], int low, int high) {
if (low
more < high)
than {
one element to sort // Check if
int pivot = arr[high];
element // Choose pivot as last

int i = low
for smaller - 1;
element // Pointer

for (int j = low; j < high; j++) { // Partition around pivot


if (arr[j] < pivot) {
than pivot // If element is less
Increment i++;
smaller element pointer //
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;}}
int temp = arr[i + 1];
position // Place pivot in sorted
arr[i + 1] = arr[high];
arr[high] = temp;
int pi = i +//1;Pivot index

quickSort(arr, low, pi - 1); // Sort left subarray


quickSort(arr, pi + 1, high); // Sort right subarray
}
}
Advantages:

● Efficiency: Fast and efficient for large datasets.


● In-place: Uses little additional memory, saving space.

Disadvantages:

● Worst-case Performance: May be slow for sorted data if the pivot


choice is poor.
● Recursive Calls: Recursive approach can use more stack space, but
this can be optimized.
THANK YOU

You might also like