This is a technique to sort a given array in an acending order.

Here is the steps we follow while performing quick sort :-

1. The last element of array is assumed to be "infinity".
2. " i " (which is an integer type variable) point to the lowest index and " j " (another integer type variable) points to the highest index of the array.
3. First element is assinged asthe "pivot" element.
4. " i " is incremented till larger or equal element than pivot is found.
5. " j " is decremented till smaller or equal element then pivot is found.
6. If " i " is less than " j " then interchange a[i] with a[j] and repeat the steps 4 and 5, else interchange a[j] and "pivot".

When the element (a[j])  is exchanged with "pivot" then the position of that element is fixed in the array and divides the array into two parts ie. on the right of the array all maximum elemnts will be there and on the left of the array all minimum elements will be there. Now sort the two parts in the same manner as of the parent array.

Now as we see that the no. of iterations will be " n log₂(n )" since " 2^x " times of comparison is made in one iteration and total number of iterations is "n", hence the total number of iterations will be " n X 2^x " ie. " n log₂(n) ".

Hence, the complexcity of this sorting technique is n log₂(n).

" n " here is the size of the array.

Now we will discuss how did the term log₂(n) came.

Since 2^x iterations are made and in the worst case the "2^x = n".

Then,

x = log₂(n)

Where " log₂ " refers to the base of logarithmic function ie. 2.

Hope when you read this article your understanding will we enhanced and you will be able to write the coding efficiently.

• Written by sauveer goel.
• In category C & C++.
• 13 years ago.

Hot Hits: 3461

Like it on Facebook, Tweet it or share this article on other bookmarking websites.