LAZR.PW
Stuff I'm working on.

Monday, 2 September 2013

Quicksort for Vectors & Arrays

#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.

No comments:

Post a Comment