Merge pull request AllAlgorithms#10 from underscoreorcus/master

abranhe · web-flow · commit 25f55c22c03f · 2018-10-01T22:58:33.000-04:00
Added quick_sort.cpp
diff --git a/sorting/quick_sort.cpp b/sorting/quick_sort.cpp
@@ -0,0 +1,51 @@
+#include <iostream>
+#include <vector>
+using namespace std;
+
+void quickSort(vector<int>&,int,int);
+int partition(vector<int>&, int,int);
+
+int main()
+{
+    vector<int> A = {10,9,8,7,6,5,4,3,2,1};
+    int start = 0;
+    int end = (int)A.size();
+    cout << "Before:" << endl;
+    for(auto value : A)
+        cout << value <<" ";
+    cout << endl;    
+    quickSort(A, start, end);
+    cout << "After: " << endl;
+    for(auto value : A)
+        cout << value <<" ";
+    cout << endl;   
+}
+
+void quickSort(vector<int>& A, int start,int end)
+{
+    int pivot;
+    if(start < end)
+    {
+        pivot=partition(A, start, end);
+        quickSort(A, start, pivot);  
+        quickSort(A, pivot+1, end);
+    }
+}
+
+
+int partition(vector<int>& A, int start,int end)
+{
+    int x = A[start];
+    int i = start;
+    int j;
+    for(j = start+1; j < end; j++)
+    {
+        if(A[j]<=x) 
+	{
+            i=i+1;
+	    swap(A[i],A[j]);
+        }
+    }
+    swap(A[i],A[start]);
+    return i;
+}
