Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* C implementation QuickSort */
- #include<stdio.h>
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const int MAX_SIZE = 1000;
- int arr[MAX_SIZE];
- /* This function takes last element as pivot, places
- the pivot element at its correct position in sorted
- array, and places all smaller (smaller than pivot)
- to left of pivot and all greater elements to right
- of pivot */
- int partition_arr( int lft, int rgt )
- {
- int mid = (lft + rgt)/2;
- swap( arr[lft], arr[rgt] );
- int pivot = arr[lft];
- int lo = lft + 1;
- int hi = rgt;
- while( lo <= hi ){
- while( arr[hi] > pivot ) hi--;
- while( lo <= hi && arr[lo] <= pivot ) lo++;
- if( lo <= hi ){
- swap( arr[lo], arr[hi] );
- lo++;
- hi--;
- }
- }
- swap( arr[lft], arr[hi] );
- return hi; // Return the index of the pivot
- }
- /* The main function that implements QuickSort
- arr[] --> Array to be sorted,
- low --> Starting index,
- high --> Ending index */
- void quickSort( int low, int high)
- {
- if (low < high)
- {
- /* pi is partitioning index, arr[p] is now
- at right place */
- int pi = parti( low, high );
- // Separately sort elements before
- // partition and after partition
- quickSort(low, pi - 1);
- quickSort( pi + 1, high);
- }
- }
- /* Function to print an array */
- void print_arr( int n )
- {
- for( int i = 0; i < n; i++ )
- cout << arr[i] << " ";
- cout << endl;
- }
- // Driver program to test above functions
- int main()
- {
- int n;
- cin>>n;
- for(int i=0;i<n;i++)
- cin>>arr[i];
- quickSort( 0, n-1);
- printf("Sorted array: ");
- print_arr(n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement