[go: up one dir, main page]
Scribd
Upload
17 views5 pages

Quick Sort

The document explains the Quick Sort algorithm, a widely used sorting method that employs a divide and conquer approach to efficiently sort an array of elements. It details the process of selecting a pivot, partitioning the array into sub-arrays, and recursively sorting those sub-arrays, while also discussing the time complexities for best, average, and worst cases. Additionally, it includes a C program implementation of the Quick Sort algorithm.

Uploaded by

baji shaik
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
17 views5 pages

Quick Sort

The document explains the Quick Sort algorithm, a widely used sorting method that employs a divide and conquer approach to efficiently sort an array of elements. It details the process of selecting a pivot, partitioning the array into sub-arrays, and recursively sorting those sub-arrays, while also discussing the time complexities for best, average, and worst cases. Additionally, it includes a C program implementation of the Quick Sort algorithm.

Uploaded by

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

Quick Sort Algorithm

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.

Time Complexity
o Best Case Complexity - In Quicksort, the best-case occurs when the pivot element is the
middle element or near to the middle element. The best-case time complexity of quicksort
is O(n*logn).
o Average Case Complexity - It occurs when the array elements are in jumbled order that
is not properly ascending and not properly descending. The average case time complexity
of quicksort is O(n*logn).
o Worst Case Complexity - In quick sort, worst case occurs when the pivot element is
either greatest or smallest element. Suppose, if the pivot element is always the last
element of the array, the worst case would occur when the given array is sorted already in
ascending or descending order. The worst-case time complexity of quicksort is O(n2).

Working of Quick Sort Algorithm:


Program:
#include<stdio.h>
#include<conio.h>
quick(int a[],int,int);
void quicksort(int a[],int,int);
intlow,high,n,a[25],b[25];
void main()
{
int i;
clrscr();
printf("enter the limit");
scanf("%d",&n);
printf("enter elements");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
low=1;
high=n;
quicksort(a,1,n);
printf("\n sorted elements are");
for(i=1;i<=n;i++)
printf("\n %d",a[i]);
getch();
}
void quicksort(int a[],intlow,int high)
{
int p;
if(low<high)
{
p=quick(a,low,high);
quicksort(a,low,p-1);
quicksort(a,p+1,high);
}
}
quick(int a[],intl,int r)
{
int pivot,t,first,last;
pivot=a[l];
first=l;
last=r;
while(first<last)
{
while(a[first]<=pivot&&first<r)
first++;
while(a[last]>=pivot&&last>l)
last--;
if(first<last)
{
t=a[first];
a[first]= a[last];
a[last]=t;
}
}
t=a[l];
a[l]=a[last];
a[last]=t;
return(last);
}

You might also like