Linked Lists

What is Linked Lists? Singly Linked Lists Doubly Linked Lists Circular Linked Lists Header Linked Lists

Stacks

What is Stack? Push Operation Pop Operation Peek Operation Linked Stack Multiple Stacks

Queues

What is Queues? Linear Queue

Searching

What is Searching? Linear Search Binary Search Interpolation Search Jump Search

Sorting

What is Sorting? Bubble Sort Insertion Sort Selection Sort Merge Sort Quick Sort Radix Sort Heap Sort Shell Sort Tree Sort

Hashing

What is Hashing? What is Collision?
The ones who are crazy enough to think they can change the world are the ones who do.
- Steve Jobs
NEXT

Quick Sort

Quick sort technique uses divide and conquer method, the n number of elements sorted in an array are divided into three segments.

  • Left Segment
  • Right Segment
  • Middle Segment

In the middle segment we will be having only one element and it is called the pivot. Also note that no element in left segment has a key larger than the key of the element in the middle and no element in right has a key that is smaller than that of the middle element. Due to this, the element in the left side and the middle side can be sorted independently, and no merge is needed following the sorting of left and right.

Advantages - Quick Sort

  • The quick sort algorithm produces the most effective and widely used method of sorting a list of any size of array.

Disadvantages - Quick Sort

  • Split stage is complex in quick sort algorithm as compared to merge sort algorithm.
  • In worst case of quick sort algorithm, the time efficieny is very poor which is very much likely to selection sort algorithm i.e) n(log 2 n).

C program - Quick Sort

Here is the program to demonstrate Quick Sort.

quick-sort.c 
#include <stdio.h>
int partition(int a[], int beg, int end);
void quick_sort(int a[], int beg, int end);
int main()
{
int arry[10], i, n;
printf("\n Enter the size of the array : ");
scanf("%d", &n);
printf("\nEnter %d elements in the array : \n",n);
for(i=0; i < n; i++)
scanf("%d",&arry[i]);
quick_sort(arry, 0, n-1);
printf("\nSorted Array in ascending order is : \n");
for(i = 0; i<n; i++)
printf("%d ", arry[i]);
return 0;
}
int partition(int a[], int beg, int end)
{
int left, right, temp, loc, flag;
loc = left = beg;
right = end;
flag = 0;
while(flag != 1)
{
while((a[loc] <= a[right]) && (loc != right))
right--;
if(loc == right)
flag = 1;
else if(a[loc] > a[right])
{
temp = a[loc];
a[loc] = a[right];
a[right] = temp;
loc = right;
}
if(flag != 1)
{
while((a[loc] > = a[left]) && (loc != left))
left++;
if(loc == left)
flag = 1;
else if(a[loc] < a[left])
{
temp = a[loc];
a[loc] = a[left];
a[left] = temp;
loc = left;
}
}
}
return loc;
}
void quick_sort(int a[], int beg, int end)
{
int loc;
if(beg < end)
{
loc= partition(a, beg, end);
quick_sort(a, beg, loc-1);
quick_sort(a, loc+1, end);
}
}
Enter the size of the array : 5 
Enter 5 elements in the array :
4 3 1 2 5 
Sorted Array in ascending order is : 
1 2 3 4 5
NEXT

Related to Quick Sort

Take a test

Report Us

We may make mistakes(spelling, program bug, typing mistake and etc.), So we have this container to collect mistakes. We highly respect your findings.

Report

Programming

Electrical

Interview

© Copyright 2019