Prison Sort

This is an actual sort. The idea of this sort is that it gets itself ready to start providing results quickly. The time to complete the sort is much longer, but the time to start to get values is very quick. It can be thought of as like a Selection Sort. It only takes LogN operation to get each addition value after setup.

This implementation is only useful where you need some result quickly but may not need all of the results.

The initialization is an order of N operation.

The reset after a result is given is a Ln N operation.

Performance

So overall this sort is very very slow compared to a normal quick sort. It is possible that it just has some defect that I have not found yet, or that can be minimized. This is a major drawback to this idea.

On the other hand it is very very fast at becoming available and then in theory you only have to pay in time for the number of values that you need.

Development

This sort is like a heap sort in that it uses the same tree structure but uses an index to avoid having to re-arrange any elements. The heap creation took noticeably longer and so was abandoned.

The table is an additional burden and with it's N entries and does take up additional space.

This is experimental.

The stand alone version of the sort has two main parts.

Initialization: Used to builds a Index that is stored in the "table" array
Rescore: Stabilizes the table after removal of items

The second implementation is used to just provide a proof of concept of the "Lazy" feature. It also uses a three part design

A class to keep track of how much of the original Vector has been sorted
Rescore: Helps stabilize the table after items have been removed
The Initialization. Creates table and prepares first number.

The second implementation uses an Iterator like design.

Implementation

/*

C++ program for implementation of Tournament Sort with lazy completion

This was written by Karl Kendall

This program is free software; you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation; version 2

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License along

with this program; if not, write to the Free Software Foundation, Inc.,

51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

*/

#include <iostream>

#include <vector>

#include<algorithm>

using namespace std;

//Prison Sort.

// in this version the winner makes a "trail" that reaches to the top.

// The main and maybe only advantage of this particular sort is that it has the selection sort like property of moving

// Each piece a minimal number of times. Without the painful n^2 property.

const int SIZE = 4000000;

//const int SIZE = 10;

void initialize( int arr[], int table[], int n)

{

for (int i = n - 1; i >= 0; i--)

{

table[i] = i;

int largest = i; // Initialize largest as current

int l = 2*i + 1; // left = 2*i + 1

int r = 2*i + 2; // right = 2*i + 2

//int p = (i-1)/2;

// If left child is larger than root

if (l < n && arr[table[l]] < arr[largest])

largest = table[l];

// If right child is larger than largest so far

if (r < n && arr[table[r]] < arr[largest])

largest = table[r];

// set current to largest

table[i] = largest;

}

//for (int i=0; i<n; ++i)

//cout << table[i] << " ";

//cout << "\n";

}

// To rescore a path leading to the root use this

void rescore( int arr[], int table[], int n, int i)

{

table[i] = i; // We want to remove the old record.

bool done = false;

while(!done)

{

int largest = i; // Initialize largest as current

int l = 2*i + 1; // left = 2*i + 1

int r = 2*i + 2; // right = 2*i + 2

int p = (i-1)/2;

// If left child is larger than root

if (l < n && arr[table[l]] < arr[largest])

largest = table[l];

// If right child is larger than largest so far

if (r < n && arr[table[r]] < arr[largest])

largest = table[r];

table[i] = largest;

if(i == 0)

done = true;

i = p;

}

// stand alone function to do the heap sort

void heapPrisonSort( std::vector<int> & arr)

{

std::vector<int> & arr2 = arr;

int n = arr.size();

int * table = new int [n];

// Build heap

initialize( &arr[0], table, n);

// One by one extract an element from heap

for (int i=n-1; i>=0; i--)

{

// Move current root to end

swap(arr[table[0]], arr[i]);

// call rescore where we introduced a weakness.

rescore(&arr[0], table, i, table[0]);

rescore(&arr[0], table, i, i);

//for (int j=0; j<i; ++j)

// cout << table[j] << " ";

//cout << "\n";

}

std::reverse(arr.begin(),arr.end());

delete[] table;

}

// A utility function to print array of size n

void printArray(int arr[], int n)

{

for (int i=0; i<n; ++i)

cout << arr[i] << " ";

cout << "\n";

}

// Class that allows for lazy way of doing sort

// Sort only takes place as fast as needed.

class Prison {

private:

int base; // our acting iterator

//int j; // our current state

int * table;

int n; // full size of array

std::vector<int> & arr;

bool done;

public:

Prison( std::vector<int> & input) : arr(input)

{

n = arr.size();

base = -1;

table = new int [n];

initialize( &arr[0], table, n);

increment();

done = false;

}

operator int(void)

{

int temp;

temp = base - 1;

return temp;

}

int dereference()

{

return arr[0];

}

void increment()

{

base++;

int i = n - 1 - base ;

if(0 < i)

{

swap(arr[table[0]], arr[ i]);

// call rescore where we introduced a weakness.

rescore(&arr[0], table, i, table[0]);

rescore(&arr[0], table, i, i);

}

int end()

{

return arr.size();

}

};

// Driver program

int main()

{

std::vector<int> arr;

for(int i = 0; i < SIZE; i++)

{

int temp = i;

arr.push_back(temp);

}

std::random_shuffle ( arr.begin(), arr.end());

clock_t normal_start, normal_end;

clock_t mysort_start, mysort_end;

clock_t initalize_start, initalize_end;

clock_t lazy_start, lazy_end;

std::vector<int> arr_normal = arr;

std::vector<int> arr_initalize = arr;

std::vector<int> arr_mysort = arr;

std::vector<int> arr_lazy = arr;

std::vector<int> result;

//This is my custom sort.

mysort_start = clock();

heapPrisonSort( arr_mysort);

mysort_end = clock();

//This is a time test of just the initalize phase

int n = arr.size();

int * table = new int [n];

initalize_start = clock();

initialize( &arr_initalize[0], table, n);

initalize_end = clock();

normal_start = clock();

std::sort (arr_normal.begin(), arr_normal.end());

normal_end = clock();

//This is the test of the lazy sort.

lazy_start = clock();

Prison prison( arr_lazy);

for(int i = 0; i < arr_lazy.size(); i++)

{

result.push_back(prison.dereference());

prison.increment();

}

lazy_end = clock();

cout << "Time taken by normal sort is : " << fixed

<< double(normal_end - normal_start) / double(CLOCKS_PER_SEC)

<< " sec " << endl;

cout << "Time taken by mysort is : " << fixed

<< double(mysort_end - mysort_start) / double(CLOCKS_PER_SEC)

<< " sec " << endl;

cout << "Time taken by initalize is : " << fixed

<< double(initalize_end - initalize_start) / double(CLOCKS_PER_SEC)

<< " sec " << endl;

cout << "Time taken by lazy sort is : " << fixed

<< double(lazy_end - lazy_start) / double(CLOCKS_PER_SEC)

<< " sec " << endl;

system("pause");

}