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

Screenshots from Windows 1.01

Windows 1.0 is a graphical personal computer operating environment developed by Microsoft, released on November 20, 1985, as the first version of the Microsoft Windows line. Version 1.01 , also released in 1985, was the first point-release after Windows 1.00.   Screenshots from Windows 1.01: ⇰ Desktop  First Run Empty Desktop Desktop With Applications ⇰  Office Applications Notepad Text Editor Calculator Calendar Clock Address Book ⇰  Multimedia Applications Media player, CD player, Volume level, and Sound: This GUI doesn’t have these features. ⇰  Networking Applications Terminal Phone Dialer: This GUI doesn’t have this feature. ⇰  Internet Applications Browser, and Mail: This GUI doesn’t have these features. ⇰  Accessibility Applications Keyboard Map:  This GUI doesn’t have this feature. ⇰  Settings Desktop themes,  Display,  S...
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 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

C Program To Convert Natural Numbers To Roman Numerals.

Roman Number System of representing numbers devised by the ancient Romans. The numbers are formed by combinations of the symbols I, V, X, L, C, D, and M, standing, respectively, for 1, 5, 10, 50, 100, 500, and 1,000 in the Hindu-Arabic numeral system. Natural numbers mean no negative numbers and no fractions, i.e. the whole numbers from 1 upwards: 1, 2, 3, and so on. Here is source code of the C program to convert natural numbers to Roman Numerals. It compiles and runs on any operating system. #include <stdio.h> void predigit(char num1, char num2); void postdigit(char c, int n); char romanval[1000]; int i = 0; int main() { int j; long number; printf("Enter any natural number: "); scanf("%d", &number);
Read more