#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;
template <class T>
void qswap(T &x, T &y)
{
T temp = x;
x = y;
y = temp;
}
template <class T> void partition(T &data, const int& left, const int& right)
{
int front = left; // Create a copy of left that will be modified
int back = right; // Create a copy of right that will be modified
int pivot = data[(left + right) / 2]; // Select centervalue as pivot
while(front <= back) // While the positions haven't collided(Seen all elements)
{
while(data[front] < pivot) // Skip items less than the pivot
{
front++; // Move front to pivot
}
while(data[back] > pivot) // Skip items greater than the pivot
{
back--; // Move back to pivot
}
if(front <= back) // If a larger front and a smaller back are found swap them and
{
qswap(data[front], data[back]); // Swap front and back values
front++; // Move front to pivot
back--; // move back to pivot
// Adding this removes the need for an extra unnecessary comparison of the already swaped values
}
}
if (left < back) partition(data, left, back); // If the gap between the start and the new end is not 0 quicksort it as a sub array
if (front < right) partition(data, front, right); // If the gap between the end and the new front is not 0 quicksort it as a sub array
}
template <class T> void quicksort(T &data, const int& size) // simpler wrapper for quicksort
{
partition(data, 0, size - 1);
}
int main()
{
srand(time(0));
std::vector<int> data;
for(int i = 0; i < 10; i++)
{
data.push_back(rand() % 10);
}
std::cout << "Unsorted" << std::endl;
for(int i = 0; i < 10; i++)
{
std::cout << data[i] << std::endl;
}
quicksort(data, data.size());
std::cout << "Sorted" << std::endl;
for(int i = 0; i < 10; i++)
{
std::cout << data[i] << std::endl;
}
std::cin.get();
return 0;
}
A quicksort I wrote quite a while ago and I found it buried in a folder so I thought I'd put it here so I don't lose it again.
KYLE EDWARDS
Monday, 2 September 2013
Quicksort for Vectors & Arrays
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment