Skip to main content

C Program To Implement Quick Sort Algorithm.

Quick sort is an efficient sorting algorithm. It is even two or three times faster than mergesort and heapsort in some particular cases. The sorting method compares n items in O(nlogn) time in average and best cases, while it is O(n^2) in worst case. Quick sort comes under divide and conquer algorithm which divides the large set of array in small by picking up a pivot element as a reference element, and do sorting.

Algorithm:
(1) Make a list of items that need to be sorted, let’s apply in an array.
(2) Choose a suitable element as pivot element from the array list, because complexity largely depends on choosing the pivot element.
(3) Rearrange the array list so that all the elements with value less than the pivot will come before the pivot and the element with value greater will come after the pivot with in the same array, which make pivot element in the sorted position.
(4) Apply recursively the third step to the sub array of the element with smaller values and separate the sub array of the elements with the greater values.



Note: In the following quicksort program, the first element is always used as the Pivot element for the remaining unsorted list.

#include<stdio.h>
#include<conio.h>

//quick Sort function to Sort Integer array list
void quicksort(int array[], int firstIndex, int lastIndex) {
int pivotIndex, temp, index1, index2;

//assigninh first element index as pivot element
if(firstIndex < lastIndex)
{
pivotIndex = firstIndex;
index1 = firstIndex;
index2 = lastIndex;

//Sorting in Ascending order with quick sort
while(index1 < index2) {

while(array[index1] <= array[pivotIndex] && index1 < lastIndex) {
/* To sort in descending order, change to index1 > lastIndex */
index1++;
}

while(array[index2]>array[pivotIndex]) {
/* To sort in descending order, change > to < */
index2--;
}

//Swapping opertation
if(index1<index2)
{
temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}}

//At the end of first iteration, swap pivot element with index2 element
temp = array[pivotIndex];
array[pivotIndex] = array[index2];
array[index2] = temp;

//Recursive call for quick sort, with partiontioning
quicksort(array, firstIndex, index2-1);
quicksort(array, index2+1, lastIndex);
}}

int main() {
int array[100],n,i;

printf("Enter How Many Data You Want To Sort: ");
scanf("%d",&n);

if(n<=0) printf("\n\tWrong Input?\t");
else {
printf("\n\nEnter %d Elements: ",n);

for(i = 0; i < n; i++) {
scanf("%d",&array[i]);
}

//calling quickSort function defined above
quicksort(array,0,n-1);

printf("\n\nAfter Sorting In Ascending Order: ");
for(i=0;i<n;i++)
printf(" %d",array[i]);
}
getch();
printf("\n\n");
}
Labels:

Popular posts from this blog

Introduction To Algorithms, 3rd Edition

Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing. This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. In this book, the authors tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor. Each chapter presents an algorithm, a design technique, an application area, or a related topic. Algorithms are described in English and in a pseudocode designed to be readable by anyone who has done a little programming. The book contains 244 figures — many with multiple parts — illustrating how the algorithms work. It also includes careful analysis of the running times of all algorithms. In this third edition, the entire book once again updated including changes cove...
Read more

C Program To Check Whether A Number Is Palindrome Or Not.

This program takes an integer from user and the integer is reversed. If the reversed integer is equal to the integer entered by user then that number is a palindrome. If not that number is not a palindrome.   #include <stdio.h> int main()  { int num, temp, remainder, reverse = 0; printf("Enter an integer: "); scanf("%d", &num); /*  original number is stored at temp */ temp = num; while (num > 0)  { remainder = num % 10; reverse = reverse * 10 + remainder; num /= 10;   }
Read more

C++ Program To Implement Bank Management System.

#include<iostream> #include<fstream> #include<cctype> #include<iomanip> #include <cstdlib> using namespace std; class account { int acno; char name[50]; int deposit; char type; public: void create_account(); //function to get data from user void show_account() const; //function to show data on screen void modify(); //function to add new data void dep(int); //function to accept amount and add to balance amount void draw(int); //function to accept amount and subtract from balance amount void report() const; //function to show data in tabular format int retacno() const; //function to return account number int retdeposit() const; //function to return balance amount char rettype() const;  //function to return type of account }; void account::create_account() { cout<<"\nEnter The Account No. : "; cin>>acno; cout<<"\n\nEnter The Name Of The Account Holder : "; cin.ig...
Read more

C++ Program To Implement Casino Number Guessing Game.

#include <iostream> #include <string> #include <cstdlib> #include <ctime> using namespace std; void drawLine(int n, char symbol); void rules(); int main() { string playerName; int amount; int bettingAmount; int guess; int dice; char choice; srand(time(0)); drawLine(70,'_'); cout << "\n\n\n\t\tCASINO GAME\n\n\n\n"; drawLine(70,'_'); cout << "\n\nEnter Your Name : "; getline(cin, playerName); cout << "\n\nEnter Deposit Amount To Play Game : $"; cin >> amount;
Read more