Youtube Video:
Analaysis though it seems little bit tough to me:
HackerRank video:
Pseudo Code from upper Youtube vid:
QuickSort(A, start, end) { if(start<end) pIndex=Partition(A,start,end); Quicksort(A,start,index-1); Quicksort(A,pIndex+1,end); } Partition(A,start,end) { pivot=A[end]; pIndex=start; for i=start to end-1 { if(A[i]<=pivot) { swap(A[i],A[pIndex]) pIndex=pIndex+1 } } swap(A[pIndex],A[end]) return pIndex }
Implementation:
#include<iostream> using namespace std; int Partition(int *A,int start,int ends){ int pivot=A[ends]; int pIndex=start; for(int i=start; i<ends; i++){ if(A[i]<=pivot) { //swap(A[i],A[pIndex]); int z=A[i]; A[i]=A[pIndex]; A[pIndex]=z; pIndex=pIndex+1; } } //swap(A[pIndex],A[ends]); int k=A[pIndex]; A[pIndex]=A[ends]; A[ends]=k; return pIndex; } void Quicksort(int *A,int start,int ends) { if(start<ends){ int pIndex=Partition(A,start,ends); Quicksort(A,start,pIndex-1); Quicksort(A,pIndex+1,ends); } } int main() { int A[]={3,4,1,4,0,9,6,5}; Quicksort(A,0,7); for(int i=0;i<8;i++) { cout<<A[i]<<" "; } return 0; }
Slightly edited in *A to A[]:
#include<iostream> using namespace std; int Partition(int A[],int start,int ends){ int pivot=A[ends]; int pIndex=start; for(int i=start; i<ends; i++){ if(A[i]<=pivot) { //swap(A[i],A[pIndex]); int z=A[i]; A[i]=A[pIndex]; A[pIndex]=z; pIndex=pIndex+1; } } //swap(A[pIndex],A[ends]); int k=A[pIndex]; A[pIndex]=A[ends]; A[ends]=k; return pIndex; } void Quicksort(int A[],int start,int ends) { if(start<ends){ int pIndex=Partition(A,start,ends); Quicksort(A,start,pIndex-1); Quicksort(A,pIndex+1,ends); } } int main() { int A[]={3,4,1,4,0,9,6,5}; Quicksort(A,0,7); for(int i=0;i<8;i++) { cout<<A[i]<<" "; } return 0; }
Some change with before and after show:
#include<iostream> using namespace std; int Partition(int A[],int start,int ends){ int pivot=A[ends]; int pIndex=start; for(int i=start; i<ends; i++){ if(A[i]<=pivot) { //swap(A[i],A[pIndex]); int z=A[i]; A[i]=A[pIndex]; A[pIndex]=z; pIndex=pIndex+1; } } //swap(A[pIndex],A[ends]); int k=A[pIndex]; A[pIndex]=A[ends]; A[ends]=k; return pIndex; } void Quicksort(int A[],int start,int ends) { if(start<ends){ int pIndex=Partition(A,start,ends); Quicksort(A,start,pIndex-1); Quicksort(A,pIndex+1,ends); } } int main() { int A[]={3,4,1,4,0,9,6,5}; int sizes=sizeof(A)/sizeof(A[0]); cout<<"Before Sorting: "; for(int i=0; i<sizes; i++) { cout<<A[i]<<" "; } Quicksort(A,0,7); cout<<endl; cout<<"After Sorting: "; for(int i=0;i<8;i++) { cout<<A[i]<<" "; } return 0; }
Complete Quicksort Implementation and taking user input:
#include<iostream> using namespace std; int Partition(int A[],int start,int ends) { int pivot=A[ends]; int pIndex=start; for(int i=start; i<ends; i++) { if(A[i]<=pivot) { //swap(A[i],A[pIndex]); int z=A[i]; A[i]=A[pIndex]; A[pIndex]=z; pIndex=pIndex+1; } } //swap(A[pIndex],A[ends]); int k=A[pIndex]; A[pIndex]=A[ends]; A[ends]=k; return pIndex; } void Quicksort(int A[],int start,int ends) { if(start<ends) { int pIndex=Partition(A,start,ends); Quicksort(A,start,pIndex-1); Quicksort(A,pIndex+1,ends); } } int main() { int sizes; int A[1000]; cout<<"How many value will you add ? "; cin>>sizes; for(int k=0; k<=sizes-1; k++) { cin>>A[k]; } //int sizes=sizeof(A)/sizeof(A[0]); cout<<"Before Sorting: "; for(int i=0; i<=sizes-1; i++) { cout<<A[i]<<" "; } Quicksort(A,0,sizes-1); cout<<endl; cout<<"After Sorting: "; for(int i=0; i<=sizes-1; i++) { cout<<A[i]<<" "; } return 0; }
Output from the above code:
Geeks for geeks:
http://quiz.geeksforgeeks.org/quick-sort/
http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151
From geeks for geeks but may be there might be some problems there
#include<iostream> using namespace std; //*arr eitype likha mane arrayta sudhu value/content ta send korbe ekhane pointer diye value tene antese void swaps(int *a,int *b){ int z=*a; *b=*a; *a=z; } int partitions(int arr[],int low,int high){ int pivot=arr[high]; int i=(low-1); for(int j=low;j<=high-1;j++){ if(arr[j]<=pivot) { i++; swaps(&arr[i],&arr[j]); } } swaps(&arr[i+1],&arr[high]); return(i+1); } void quicksort(int arr[],int low,int high){ if(low<high){ int pi=partitions(arr,low,high); quicksort(arr,low,pi-1); quicksort(arr,pi+1,high); } } void printArray(int arr[],int n){ for(int i=0;i<n;i++){ cout<<arr[i]<<" "; } } int main() { //int arr[]={10,7,8,9,1,5}; //int sizes=sizeof(arr)/sizeof(arr[0]); //cout<<"Unsorted array: "; //for(int i=0;i<sizes;i++){ //cout<<arr[i]<<" "; //} //cout<<endl; int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr)/sizeof(arr[0]); quicksort(arr, 0, n-1); cout<<"Sorted array: "; printArray(arr, n); return 0; }
Another good one for understanding(I think it’s the best one):
Pseudocode available in the above video:
implemented code:
#include<bits/stdc++.h> using namespace std; int Partition(int A[],int p,int r) { int x=A[r]; int i=p-1; for(int j=p; j<=r-1; j++) { if(A[j]<=x) { i=i+1; //swap(A[i],A[j]); //swapping int z=A[j]; A[j]=A[i]; A[i]=z; } } //swap(A[i+1],A[r]); //swapping int m=A[r]; A[r]=A[i+1]; A[i+1]=m; return (i+1); //sending the pivot value to the actual caller function QuickSort } int QuickSort(int A[],int p,int r) { if(p<r) { int q=Partition(A,p,r); QuickSort(A,p,q-1); QuickSort(A,q+1,r); } } int main() { //int A[]= {2,1,3,4,10,5,8}; int A[]={10,5,8,2,4,3,1}; QuickSort(A,0,6); for(int i=0; i<7; i++) { cout<<A[i]<<" "; } return 0; }
#include<bits/stdc++.h> using namespace std; void swaps(int *p,int *q) { int temp=*q; *q=*p; *p=temp; } int Partition(int A[],int p,int r) { int x=A[r]; int i=p-1; for(int j=p; j<=r-1; j++) { if(A[j]<=x) { i=i+1; //swap(A[i],A[j]); //swapping swaps(&A[i],&A[j]); // int z=A[j]; // A[j]=A[i]; // A[i]=z; } } //swap(A[i+1],A[r]); //swapping // int m=A[r]; // A[r]=A[i+1]; // A[i+1]=m; swaps(&A[i+1],&A[r]); return (i+1); //sending the pivot value to the actual caller function QuickSort } int QuickSort(int A[],int p,int r) { if(p<r) { int q=Partition(A,p,r); QuickSort(A,p,q-1); QuickSort(A,q+1,r); } } int main() { //int A[]= {2,1,3,4,10,5,8}; int A[]={10,5,8,2,4,3,1}; QuickSort(A,0,6); for(int i=0; i<7; i++) { cout<<A[i]<<" "; } return 0; }
Quick Sorting in Process
Time and Space complexity: Best Case : omega(nlogn)
Worst case: O(n^2)
See this video to clear up the skills:
ideone example: http://ideone.com/oWbONR
Others Code:
http://www.cc.gatech.edu/classes/cs3158_98_fall/quicksort.html
Recursive:
http://www.algolist.net/Algorithms/Sorting/Quicksort
CLRS:
http://www.bowdoin.edu/~ltoma/teaching/cs231/fall09/Lectures/5-quicksort/quicksort.pdf
Google Search Terms:
https://www.google.com/webhp?sourceid=chrome-instant&rlz=1C1PRFC_enBD706BD706&ion=1&espv=2&ie=UTF-8#q=quick+sort+pseudocode&*