Scribd
Upload
17 views5 pages

r22 Ds Unit - 4 Quick Sort

Quicksort is an efficient sorting algorithm that utilizes the divide and conquer approach, making an average of n log n comparisons for sorting an array of n elements. The algorithm involves selecting a pivot, partitioning the array into sub-arrays based on the pivot, and recursively sorting the sub-arrays. Its time complexity varies with the worst case being O(n^2) and the best and average cases being O(n log n).

Uploaded by

suryagoda8
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
17 views5 pages

r22 Ds Unit - 4 Quick Sort

Quicksort is an efficient sorting algorithm that utilizes the divide and conquer approach, making an average of n log n comparisons for sorting an array of n elements. The algorithm involves selecting a pivot, partitioning the array into sub-arrays based on the pivot, and recursively sorting the sub-arrays. Its time complexity varies with the worst case being O(n^2) and the best and average cases being O(n log n).

Uploaded by

suryagoda8
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

Quick Sort

Sorting is a way of arranging items in a systematic manner. Quicksort is the


widely used sorting algorithm that makes n log n comparisons in average
case for sorting an array of n elements. It is a faster and highly efficient
sorting algorithm. This algorithm follows the divide and conquer approach.
Divide and conquer is a technique of breaking down the algorithms into
subproblems, then solving the subproblems, and combining the results
back together to solve the original problem.

Divide: In Divide, first pick a pivot element. After that, partition or


rearrange the array into two sub-arrays such that each element in the left
sub-array is less than or equal to the pivot element and each element in the
right sub-array is larger than the pivot element.

Conquer: Recursively, sort two subarrays with Quicksort.

Combine: Combine the already sorted array.

Quicksort picks an element as pivot, and then it partitions the given array
around the picked pivot element. In quick sort, a large array is divided into
two arrays in which one holds values that are smaller than the specified
value (Pivot), and another array holds the values that are greater than the
pivot.

After that, left and right sub-arrays are also partitioned using the same
approach. It will continue until the single element remains in the sub-array.
Choosing the pivot
In Quick sort algorithm, partitioning of the list is performed using following steps...

 Step 1 - Consider the first element of the list as pivot (i.e., Element at first
position in the list).
 Step 2 - Define two variables i and j. Set i and j to first and last elements of the
list respectively.
 Step 3 - Increment i until list[i] > pivot then stop.
 Step 4 - Decrement j until list[j] < pivot then stop.
 Step 5 - If i < j then exchange list[i] and list[j].
 Step 6 - Repeat steps 3,4 & 5 until i > j.
 Step 7 - Exchange the pivot element with list[j] element.

Following is the sample code for Quick sort...

Quick Sort Logic


//Quick Sort Logic

void quickSort(int list[10],int first,int last){

int pivot,i,j,temp;

if(first < last){

pivot = first;

i = first;

j = last;
while(i < j){

while(list[i] <= list[pivot] && i < last)

i++;

while(list[j] && list[pivot])

j--;

if(i < j){

temp = list[i];

list[i] = list[j];

list[j] = temp;
}

temp = list[pivot];

list[pivot] = list[j];

list[j] = temp;

quickSort(list,first,j-1);

quickSort(list,j+1,last);

Example
Complexity of the Quick Sort Algorithm

To sort an unsorted list with 'n' number of elements, we need to make ((n-1)+(n-2)+(n-3)+......+1) = (n (n-
1))/2 number of comparisions in the worst case. If the list is already sorted, then it requires 'n' number
of comparisions.

Worst Case : O(n2)

Best Case : O (n log n)

Average Case : O (n log n)

You might also like