Group Description

Multikey quicksort is quicksort for arrays where the elements are containers themselves, and uses a method much faster than comparing each element in a loop until a difference is found, as is done by most normal sequential sorting algorithms, such as std::sort, mergesort, heapsort, and quicksort.

They way that it does this is by first comparing the first element of the keys, and then the second, and so forth. It works for variable sized arrays and only examines as many keys as it needs to finish sorting the entire array.

The time complexity to sort N arbitrarily long(the length usually has little effect) is O(2N ln N). This is faster than std::sort by a factor of the average word length on average. In addition, this is designed to avoid worst case without sacrificing performance because of its special partitioning method.

Requirements

The requirements for the all of the multikey quicksort functions is that the collection or iterator passed as an argument must support operator[], and each element returned by that must return an object of type KeyHolds, which must be compareable with operator< and operator==. In addition, at the end of each subarray must be an element that compares low against all other elements, so that multikey quicksort knows where each array ends. For functions where a variable is passed as a parameter, the subarrays need not support operator[], but the functor must take a subarray as its first parameter and an int as its second, and return the element of the subarray specified by the int parameter.

The reverse sorting functions have an r_ appended to the name, the parameters are the same.

References:

Algorithms in C++, Third Edition, by Robert Sedgewick

Authors:

Fred Boginson (June 2007)

Interface

#include <codecogs/array/sort/multikey_quicksort.h>

using namespace Array::Sort::detail;

	template<...> void	mkquicksort (Itit a, int l, int r, int bit, const KeyHolds& term) A file containing multikey quicksort algorithms
	template<...> void	rmkquicksort (Itit a, int l, int r, int bit, const KeyHolds& term) The real sorting function
	template<...> void	mkquicksort (Itit a, int l, int r, int bit, const KeyHolds& term, const func& keyfunc) The real sorting function
	template<...> void	rmkquicksort (Itit a, int l, int r, int bit, const KeyHolds& term, const func& keyfunc) The real sorting function
	template<...> void	mk_qsort (Itit data, int size, const KeyHolds& term)[inline] A multikey quicksort sorting function
	template<...> void	r_mk_qsort (Itit data, int size, const KeyHolds& term)[inline] A reverse multikey quicksort sorting function
	template<...> void	mk_qsort (Itit data, int size, const KeyHolds& term, const func& keyfunc)[inline] A multikey quicksort function
	template<...> void	r_mk_qsort (Itit data, int size, const KeyHolds& term, const func& keyfunc)[inline] A reverse multikey quicksort sorting function
	template<...> void	mk_qsort (Itit a, int size, int startbyte, const KeyHolds& term)[inline] A multikey quicksort sorting function
	template<...> void	r_mk_qsort (Itit a, int size, int startbyte, const KeyHolds& term)[inline] A reverse multikey quicksort function
	template<...> void	r_mk_qsort (Itit a, int start, int size, int startbyte, const KeyHolds& term)[inline] A reverse multikey quicksort function
	template<...> void	mk_qsort (Itit a, int size, int startbyte, const KeyHolds& term, const func& keyfunc)[inline] A multikey quicksort sorting function
	template<...> void	mk_qsort (Itit a, int start, int size, int startbyte, const KeyHolds& term, const func& keyfunc)[inline] A multikey quicksort function
	template<...> void	mk_qsort (Itit a, int start, int size, int startbyte, const KeyHolds& term)[inline] A multikey quicksort function
	template<...> void	r_mk_qsort (Itit a, int size, int startbyte, const KeyHolds& term, const func& keyfunc)[inline] A reverse multikey quicksort sorting function
	template<...> void	r_mk_qsort (Itit a, int start, int size, int startbyte, const KeyHolds& term, const func& keyfunc)[inline] A reverse multikey quicksort function
	template<...> void	mk_qsort (Itit data, Itit end, const KeyHolds& term)[inline] A multikey quicksort function modeling the stl algorithm interface
	template<...> void	r_mk_qsort (Itit data, Itit end, const KeyHolds& term)[inline] A reverse multikey quicksort function modeling the stl algorithm interface
	template<...> void	mk_qsort (Itit data, Itit end, const KeyHolds& term, const func& keyfunc)[inline] A multikey quicksort function modeling the stl algorithm interface
	template<...> void	r_mk_qsort (Itit data, Itit end, const KeyHolds& term, const func& keyfunc)[inline] A reverse multikey quicksort function modeling the stl algorithm interface
	template<...> void	mk_qsort (Itit a, Itit end, std::size_t startbyte, const KeyHolds& term)[inline] A multikey quicksort function modeling the stl algorithm interface
	template<...> void	r_mk_qsort (Itit a, Itit end, std::size_t startbyte, const KeyHolds& term)[inline] A reverse multikey quicksort function modeling the stl algorithm interface
	template<...> void	mk_qsort (Itit a, Itit end, std::size_t startbyte, const KeyHolds& term, const func& keyfunc)[inline] A multikey quicksort function modeling the stl algorithm interface
	template<...> void	r_mk_qsort (Itit a, Itit end, std::size_t startbyte, const KeyHolds& term, const func& keyfunc)[inline] A reverse multikey quicksort function modeling the stl algorithm interface

---

Function Documentation

See the group documentation.

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     mk_qsort(arrs, 5, -1);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

2 1 9 10 10 2 4 9 7 5
4 7 5 6 7 0 5 0 5 4
7 7 5 8 6 7 3 7 9 2
7 7 8 10 6 7 8 5 6 7
8 9 9 1 7 5 5 10 1 0

Parameters:

data	The input value
size	The size of the array
term	The terminating object[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     r_mk_qsort(arrs, 5, -1);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

8 9 9 1 7 5 5 10 1 0
7 7 8 10 6 7 8 5 6 7
7 7 5 8 6 7 3 7 9 2
4 7 5 6 7 0 5 0 5 4
2 1 9 10 10 2 4 9 7 5

Parameters:

data	The input array
size	The size of the array
term	The terminating object[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int x) //the funtor
{
     return arr[x];
}
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     mk_qsort(arrs, 5, -1, &getint);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

2 1 9 10 10 2 4 9 7 5
4 7 5 6 7 0 5 0 5 4
7 7 5 8 6 7 3 7 9 2
7 7 8 10 6 7 8 5 6 7
8 9 9 1 7 5 5 10 1 0

Parameters:

data	The input data
size	The size of the array
term	The terminating character[const][reference]
keyfunc	The functor to get the keys from an object[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int x) //the funtor
{
     return arr[x];
}
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     mk_qsort(arrs, 5, -1, &getint);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

8 9 9 1 7 5 5 10 1 0
7 7 8 10 6 7 8 5 6 7
7 7 5 8 6 7 3 7 9 2
4 7 5 6 7 0 5 0 5 4
2 1 9 10 10 2 4 9 7 5

Parameters:

data	The input array
size	The size of the array
term	The character ar the end of each subarray[const][reference]
keyfunc	The function to get keys from each subarray[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation.

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     mk_qsort(arrs, 5, 2, -1); //third byte
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

4 7 5 6 7 0 5 0 5 4
7 7 5 8 6 7 3 7 9 2
7 7 8 10 6 7 8 5 6 7
8 9 9 1 7 5 5 10 1 0
2 1 9 10 10 2 4 9 7 5

Parameters:

a	The input array
size	The size of the array
startbyte	the byte to start examining, with zero being the first byte
term	The terminating object[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     r_mk_qsort(arrs, 5, 2, -1); //third byte
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

2 1 9 10 10 2 4 9 7 5
8 9 9 1 7 5 5 10 1 0
7 7 8 10 6 7 8 5 6 7
7 7 5 8 6 7 3 7 9 2
4 7 5 6 7 0 5 0 5 4

Parameters:

a	The input array
size	The size of the array
startbyte	The byte at which to start examining
term	The character at the end of each subarray[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     r_mk_qsort(arrs, 2, 5, 2, -1);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

7 7 8 10 6 7 8 5 6 7
2 1 9 10 10 2 4 9 7 5
8 9 9 1 7 5 5 10 1 0
7 7 5 8 6 7 3 7 9 2
4 7 5 6 7 0 5 0 5 4

Parameters:

a	The input array
start	The object at which to start examining, starting with zero
size	The size of the array
startbyte	The object of each subarray with which to start examining, starting with zero
term	The object at the end of each subarray[const][reference]

Returns:

none

Note:

size is the size of the complete array, not the distance from the parameter start to the end of the array

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int x) //the funtor
{
     return arr[x];
}
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     mk_qsort(arrs, 5, 2, -1, &getint);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

4 7 5 6 7 0 5 0 5 4
7 7 5 8 6 7 3 7 9 2
7 7 8 10 6 7 8 5 6 7
8 9 9 1 7 5 5 10 1 0
2 1 9 10 10 2 4 9 7 5

Parameters:

a	The input array
size	The size of the array
startbyte	The object of the subarray to start sorting with, starting at zero
term	The object at the end of each subarray[const][reference]
keyfunc	The functor to get key values from the subarrays[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int d)
{
   return arr[d];
}
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     mk_qsort(arrs, 1, 5, 2, -1, &getint); //third byte, second array
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

7 7 8 10 6 7 8 5 6 7
4 7 5 6 7 0 5 0 5 4
7 7 5 8 6 7 3 7 9 2
8 9 9 1 7 5 5 10 1 0
2 1 9 10 10 2 4 9 7 5

Parameters:

a	The input array
start	The element of the array to start sorting with, starting with zero
size	The size of the array
startbyte	The object of each subarray to begin sorting with
term	The object at the end of each array[const][reference]
keyfunc	The functor to get keys from each subarray[const][reference]

Returns:

none

Note:

size is the size of the whole array, not the distance from the start parameter to the end

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     mk_qsort(arrs, 5, 2, -1);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

4 7 5 6 7 0 5 0 5 4
7 7 5 8 6 7 3 7 9 2
7 7 8 10 6 7 8 5 6 7
8 9 9 1 7 5 5 10 1 0
2 1 9 10 10 2 4 9 7 5

Parameters:

a	The input array
start	The object to start sorting at, starting at zero
size	The size of the array
startbyte	The object of each subarray to start sorting with, starting with zeros
term	The object at the end of each array[const][reference]

Returns:

none

Note:

size is the size of the complete array, not the distance from the start parameter to the end of the array

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int x) //the funtor
{
     return arr[x];
}
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11;
          }
          arrs[x][10] = -1; //terminating object
     }
     r_mk_qsort(arrs, 5, 2, -1, &getint);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

2 1 9 10 10 2 4 9 7 5
8 9 9 1 7 5 5 10 1 0
7 7 8 10 6 7 8 5 6 7
7 7 5 8 6 7 3 7 9 2
4 7 5 6 7 0 5 0 5 4

Parameters:

a	The input array
size	The size of the array
startbyte	The object of each subarray to start sorting with, starting at zero
term	The object at the end of each subarray[const][reference]
keyfunc	The function to get keys from each subarray[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int d)
{
    return arr[d];
}
int main()
{
     int* arrs[5];
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11; //reverse order
          }
          arrs[x][10] = -1; //terminating object
     }
     r_mk_qsort(arrs, 2, 5, 2, -1, &getint);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

4 7 5 6 7 0 5 0 5 4
7 7 8 10 6 7 8 5 6 7
2 1 9 10 10 2 4 9 7 5
8 9 9 1 7 5 5 10 1 0
7 7 5 8 6 7 3 7 9 2

Parameters:

a	The input array
start	The object of the array to start sorting at, starting with zero
size	The size of the array
startbyte	The object of each subarray to start examining, starting with zero
term	The object at the end of each subarray[const][reference]
keyfunc	The functor to get keys from the subarrays[const][reference]

Returns:

none

Note:

size is the size of the compalte array, not the distance from the paramter start to the end of the array

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Array::Sort;
int main()
{
     vector<int*> arrs(5);
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11;
          }
          arrs[x][10] = -1;
     }
     mk_qsort(arrs.begin(), arrs.end(), -1);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

1 1 6 8 5 5 2 4 6 6
4 0 8 4 4 0 3 3 5 8
5 1 3 10 6 0 0 6 7 8
5 6 5 0 1 4 5 6 5 7
7 10 3 5 2 10 9 10 3 10

Parameters:

data	The input array
end	The location of the end of the input array
term	The object at the end of each array[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Array::Sort;
int main()
{
     vector<int*> arrs(5);
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11;
          }
          arrs[x][10] = -1;
     }
     r_mk_qsort(arrs.begin(), arrs.end(), -1);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

7 10 3 5 2 10 9 10 3 10
5 6 5 0 1 4 5 6 5 7
5 1 3 10 6 0 0 6 7 8
4 0 8 4 4 0 3 3 5 8
1 1 6 8 5 5 2 4 6 6

Parameters:

data	The input array
end	The location at the end of the array
term	The object at the end of each subarray[const][reference]

Returns:

none

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int d)
{
    return arr[d];
}
int main()
{
     vector<int*> arrs(5);
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11;
          }
          arrs[x][10] = -1;
     }
     //cast to make sure that -1 is interpreted as the 
     //terminating character, not the startbyte
     mk_qsort(arrs.begin(), arrs.end(), (int)-1, &getint);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

1 1 6 8 5 5 2 4 6 6
4 0 8 4 4 0 3 3 5 8
5 1 3 10 6 0 0 6 7 8
5 6 5 0 1 4 5 6 5 7
7 10 3 5 2 10 9 10 3 10

Parameters:

data	The input array
end	The location at the end of the array
term	The object at the end of each subarray[const][reference]
keyfunc	The functor to obtain keys from each subarray[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Array::Sort;
int getint(int* arr, int d)
{
    return arr[d];
}
int main()
{
     vector<int*> arrs(5);
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11;
          }
          arrs[x][10] = -1;
     }
     //cast to make sure that -1 is interpreted as the 
     //terminating character, not the startbyte
     r_mk_qsort(arrs.begin(), arrs.end(), (int)-1, &getint);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

7 10 3 5 2 10 9 10 3 10
5 6 5 0 1 4 5 6 5 7
5 1 3 10 6 0 0 6 7 8
4 0 8 4 4 0 3 3 5 8
1 1 6 8 5 5 2 4 6 6

Parameters:

data	The input array
end	The location at the end of the array
term	The object at the end of each subarray[const][reference]
keyfunc	The functor to get objects from each subarray[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See thr group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Array::Sort;
int main()
{
     vector<int*> arrs(5);
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11;
          }
          arrs[x][10] = -1;
     }
     //cast to make sure that -1 is interpreted as the 
     //terminating character, not the functor
     mk_qsort(arrs.begin(), arrs.end(), (std::size_t)2, -1);
     for(int x = 0; x < 5; x++)
     {
          for(int y = 0; y < 10; y++)
          {
               cout << arrs[x][y] << " ";
          }
          cout << endl;
          delete arrs[x];
     }
     return 0;
}

Output:

7 10 3 5 2 10 9 10 3 10
5 1 3 10 6 0 0 6 7 8
5 6 5 0 1 4 5 6 5 7
1 1 6 8 5 5 2 4 6 6
4 0 8 4 4 0 3 3 5 8

Parameters:

a	The input array
end	The location at the end of the array
startbyte	The object of the subarrays to start sorting with, starting at zero
term	The object at the end of each array[const][reference]

Returns:

none

Authors:

Sam Schetterer (June 2007)

Source Code:

- To get code register with CodeCogs. Already a Member, then Login.

See the group documentation

Example:

#include <codecogs\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Array::Sort;
int main()
{
     vector<int*> arrs(5);
     for(int x = 0; x < 5; x++)
     {
          arrs[x] = new int[11];
          for(int y = 0; y < 10; y++)
          {
               arrs[x][y] = rand() % 11;
          }
          arrs[x][10] = -1;
     }
     //cast to make sure that -1 is interpreted as the 
     //terminating character, not the functor
     r_mk_qsort(arrs.begin(), arrs.end(), (std::size_t)2, -1);
     for(int