QUICK SORT

Quick sort is divide and conquer algorithm .Its one of the most influential algorithm of 20th century.

Its a top down approach every time a element  is taken and is fixed to some position and then from that fixed place array is portioned in two sub arrays(fixing the position of the pivot is termed as portioning the data) which a recursively portioned further.
It is in place sorting algorithm or in situ

Generally we make first element as the pivot in an array but this in all ready  sorted array does n^2 number of steps thus we prefer to do random shuffling to an array before passing it to quick sort function

Explanation-Here we have taken first element of  the array as the pivot we can take any element as the pivot or median for the best performance.If an array was sorted then we would have taken first element as pivot it would have resulted in worst performance.Thus while doing qsort we must put the given array to a shuffling function

Here split function helps in implementing the divide and conquer stuff by dividing the array into sub-arrays and qsort fixes the position of pivot

Time complexity

Best Case  nlogn (in best case number of compares are 1.39nlog(n))

Average Case   nlogn  (Depth of recursion is logarthmic)  

Worst Case n^2

Space Complexity O(n)

Stability* -In normal and efficient implementation of Quick sorting it is not  stable

Shuffling is needed for performance grantee

Optimizing  quick sort

• Use of extra array may help in partitioning but its not worth using it because it takes extra memory(and becomes same as merge sorting)
• it can be improved by using cut off ie after dividing array into small sub arrays and applying insertion sort, insertion sort handles the nearly sorted array efficiently and moreover it can sort the numbers during runtime
•  we can make pivot=median of the data and for large data we can get the median by taking sample the data

Comparison

In average case merge sorting do 39% more compares than quick sorting but quick sorting is faster than merge sorting because it has less data movement

Insertion and merge sort are stable while bubble selection and quick(in an efficient implimentation) are not stable

Insertion and merge sort are stable because in their algorithm we never make equal item pass or swap

What are stable sorting algorithms-:

In a stable sorting algorithms  relative order of the equal elements are maintained because we never swap the elements having the equal values(use full when we have lot many fields and need to arrange the data according to any field as required)

power of 2 in constant time

Checking if number can be presented in power of 2 in constant time:

Algorithm

Number which can be represented in power of 2 its binary form will have 1 only at msb while
number one less than it will have 0 at msb while all other will have 1.
For examble
64=1000000
63=0111111
Now if we multiply each bit of 64 with corresponding bit of 63 we will get 0

SOURCECODE
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
int m=64;
int n=63;
if((m&n)==0)//bitwise operator
cout<<"yes number can be represented in power of two";
else
cout<<"cannot be represented in power of two";
getch();
}