Quick sort Using C++
#include<iostream>
using namespace std;
void quickSort(int array[], int start, int end)
{
int i = start; // index of left-to-right scan
int k = end; // index of right-to-left scan
if (end - start >= 1) // check that there are at least two elements to sort
{
int pivot = array[start]; // set the pivot as the first element in the partition
while (k > i) // while the scan indices from left and right have not met,
{
while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first
i++; // element greater than the pivot
while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
k--; // element not greater than the pivot
if (k > i) // if the left seekindex is still smaller than
swap(array[i], array[k]); // the right index,
// swap the corresponding elements
}
swap(array[start], array[k]); // after the indices have crossed,
// swap the last element in
// the left partition with the pivot
quickSort(array,start, k - 1); // quicksort the left partition
quickSort(array,k + 1, end); // quicksort the right partition
}
else // if there is only one element in the partition, do not do any sorting
{
return; // the array is sorted, so exit
}
}
int main()
{
int a[10];
int n;
cout<<"how many elements you want? : \n";
cin>>n;
cout<<endl<<"enter your elements : "<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
quickSort(a,0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment