# Quick Sorting algorithm with example code in C/C++/Java languages

jojo September 18, 2012 65 Comments

We have seen 3 simple sorting algorithms already 1) Bubble Sorting 2) Selection Sorting and finally Insertion sorting. All these algorithms were so simple to understand and were easy to implement as a program in C/C++ or even Java. But at the same time all 3 of them were too inefficient.  Their execution time was of the order of n*n, where n is the number of elements to be sorted. In practice, these simple sorting algorithms are seldom used.

Tony Hoare

Quick sort is an improved sorting algorithm developed by Tony Hoare (C.A.R Hoare) in 1960, at the  age of 26, while he was working on a machine translation project in Soviet union. You can read more about Tony Hoare and his story of developing Quick sort in Wikipedia – Quicksort and Tony Hoare

Quick sort is considered as the best general purpose sorting algorithm available till date. The algorithm is developed in a “divide and conquer” method which is an important algorithm design paradigm in computer science. Quick sort algorithm divides the array into 2 partitions. To perform this partition, algorithm selects one element in the array as a ‘comparand’. Based on this comparand, the algorithm divides all other elements in the array into 2 partitions, one to left side of comparand and other to right side of comparand. Elements on left side partition are all less than comparand and elements on right side partition are all greater than comparand. Now each of these partitions are sorted separately using the same above process.

Example:- Consider the array was initially array[5] = {4,3,2,5,1};  2 is selected as comparand. After the first pass of the qsort function (as defined in the program below), the array would be rearranged as shown below.

array[]= {1, 2, 3, 5, 4};

See, the elements less than comparand ,1 forms first partition (left partition) and elements greater than comparand 3,5,4 forms second partition (right partition). The comprand itself may fit into any one of the partitions as per algorithm. Dont worry about it!

Now look at the bottom lines of the program given below.  The same qsort() function is called recursively to sort left partition and right partition separately.

To understand the working of quick sort algorithm perfectly, you may observe the below given program carefully. Take a piece of paper and pen, work on the program flow line by line. I have given appropriate comments on each important line of code.  If you feel any confusion/doubt – just ask here in comments section.

#### Example program to implement Quick Sorting in C/C++

```//PROGRAM TO DEMO QUICK SORTING #include #include void qsort(int *array,int left,int right); //Function qsort declared. Array to sort is passed to function as a pointer. void main() { int array[5]={4,3,2,5,1}; //Array of 5 elements declared and intialized with elements. int left=0,right=4; // right is assigned the index of the last element in the array. int x;```

``` qsort(array,left,right); //Fucnction call to perform quicksort. printf("\n\tThe Sorted array is\n\t"); for(x=0;x<=4;x++) { printf("%d",array[x]); } getch(); } void qsort(int *array,int left,int right) //Function definition of qsort begins. { int i,j,comp,temp; //comp - variable to hold the comparand value. i=left; j=right; comp=array[(left+right)/2]; //comparanad value is determnined as the middle element in array and is assigned to variable comp. // Code lines to divide the array into 2 partitions begins. Partitions the array with elements < comp to left side and elments >comp to right side. do { while((array[i]comp)&&(j>left)) //Checks if the elements on right side of comp is already greater than comp. { j--; //If YES, no need to move that element to left side of comp. So j is decremented. } if(i<=j) //Code lines to interchange elements to left and right of comp begins. { temp=array[i]; array[i]=array[j]; array[j]=temp; i++;j--; } }while(i<=j); // Continues the process as long as i<=j // When this do while loop finishes, array will be partitioned into 2 - with elementscomp on right side. // The 2 partitions needs to be sorted seperately. This sorting is achieved with following lines of codes. if(left   Note:- Even if you want into implement quick sort in another programming language like Java, the basic algorithm implementation using loops & recursive calls remains the same. Only the syntax differs. Selection of the comparand value:-  The selection of comparand value is of some importance in quick sort as it can directly affect the speed of sorting. If the 'comparand' value is selected as the largest value/lowest value in the array, then quick sort will degrade drastically in performance, with speed of execution in the order of n*n. The ideal case is to select the middle value as comparand, which may not be practical unless we have an idea about the nature of data. Generally a comparand is selected inrandom. A much more efficient way is to take the average of 2 or 3 elements and choose the average as comparand.  ```
``` (adsbygoogle = window.adsbygoogle || []).push({}); Categories: C plus plus C Programming ```
``` Previous post Next post (adsbygoogle = window.adsbygoogle || []).push({}); You may also like: Control structures and statements in C and C++ Insertion sorting algorithm with example in C/C++/Java languages Selection Sort in C/C++/Java programming languages Difference between Procedure Oriented(POP) and Object Oriented Programming(OOP) What is C++ ? An Introduction to programming with C++ We recommend: Interface Arduino and Color Sensor - RGB Sensor TCS230 8051 Simulator Intelligent trailing switch. Class D amplifier circuit Blinking LED using 8051 Leave a Reply You must be logged in to post a comment. ```
``` ```
``` (adsbygoogle = window.adsbygoogle || []).push({}); Sort By Type 101-Announcements (30) 555 Timer IC (16) 8051 (26) 8051 projects (21) Amplifier Circuits (39) Arduino (70) ARM (3) Audio Circuits (104) Automotive Circuits (28) AVR (23) Basic Electricity (1) Basic Electronics (17) Battery Circuits (23) C plus plus (7) C Programming (14) Cable TV Circuits (1) Camera Technology (5) Clipping and Clamping Circuits (7) Clocking & Timer Circuits (2) Conversion Circuits (10) Counter Circuits (2) Counters (2) Digital Electronics (11) Drones (1) Education & Training (7) Electronic Components (31) Electronic Keys & Locks (3) Electronics Books (10) Electronics Jobs (5) Embedded Systems (7) Equipment Reviews (1) Events (3) Fan Circuits (1) Filter Circuits (16) Fire Alarm (3) Fun & Game Circuits (14) Gadget Reviews (6) Guides (15) Ham Radio Circuits (2) High Voltage Circuits (1) History (26) Home Circuits (35) Industrial Circuits (15) Industry News (1) Infographics (1) Instruments (13) Integrated Circuits (20) Inverters (5) Lab Manuals (20) LED related (3) Light Related (14) Lighting Circuits (44) MATLAB (3) Microcontrollers (12) Mobile Phone Related (3) Motor Related (14) Nanotechnology (14) Oscillators (25) PCB (2) Peripheral Interface Controller (PIC) (29) Power Controller Circuits (8) Power Electronics (3) Power Supplies (72) Product Reviews (12) Project Ideas (1) Projects (7) Proteus (16) Proximity Detectors (3) Radio Circuits (30) Radio Transmitters (19) Raspberry Pi (3) Relays (3) Remote Circuits (12) Reviews (8) Robotics (7) RTOS (2) Security & Saftey (17) Sensor Circuits (16) Signal Conditioners (11) Signal Generators (13) Speed Controller Circuits (1) State space analysis (2) Switching Circuits (6) Tech News (86) Telephone Related (9) Television Related (4) Temperature Related (3) Test & Measurement Circuits (38) Testing Components (9) Three phase circuits (1) Timer Circuits (3) Tone generator circuits (20) Tools and Softwares (6) Transmitters (7) Tutorials (163) UPS (2) USB Circuits (3) Videos (5) VLSI (36) Voltage Regulators (15) Other Links About Advertise With Us Authors Datasheets Disclaimer Electronic Circuit Symbols Electronic Project Kits Lab Manuals Electronic Circuits Lab Microcontroller lab Microprocessor Lab Privacy Policy Resistor Color Code Calculator Testing Components Write For Us ```
``` ```
``` ```
``` ```
``` ```
``` ```
``` Р’В© 2018 CircuitsToday. All rights reserved. About| Privacy Policy| Write For Us|Earn Money| Latest Electronic Circuits ( function( grecaptcha ) { var anr_onloadCallback = function() { grecaptcha.execute( '6LdyoKsUAAAAAKrBfPSvRg1SE2q0Y_B118ISJFi1', { action: 'advanced_nocaptcha_recaptcha' } ).then( function( token ) { for ( var i = 0; i < document.forms.length; i++ ) { var form = document.forms[i]; var captcha = form.querySelector( 'input[name="g-recaptcha-response"]' ); if ( null === captcha ) continue; captcha.value = token; } }); }; grecaptcha.ready( anr_onloadCallback ); document.addEventListener( 'wpcf7submit', anr_onloadCallback, false ); if ( typeof wc_checkout_params !== 'undefined' ) { jQuery( document.body ).on( 'checkout_error', anr_onloadCallback ); } } )( grecaptcha ); ```