multikey

Interface

Overview

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)

Mk Qsort

See the group documentation.

Example 1

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See group documentation

Example 2

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See group documentation

Example 3

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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
keyfunc	The functor to get the keys from an object

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Example 4

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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
keyfunc	The function to get keys from each subarray

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See the group documentation.

Example 5

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Example 6

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Note

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

Example 7

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See the group documentation

Example 8

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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
keyfunc	The functor to get key values from the subarrays

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See the group documentation

Note

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

Example 9

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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
keyfunc	The functor to get keys from each subarray

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See the group documentation

Note

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

Example 10

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Example 11

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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
keyfunc	The function to get keys from each subarray

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Note

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

Example 12

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
using namespace std;
using namespace Computing::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
keyfunc	The functor to get keys from the subarrays

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See group documentation

Example 13

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Example 14

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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

Returns

none

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See the group documentation

Example 15

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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
keyfunc	The functor to obtain keys from each subarray

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Example 16

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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
keyfunc	The functor to get objects from each subarray

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See thr group documentation

Example 17

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the group documentation

Example 18

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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 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 0 8 4 4 0 3 3 5 8
1 1 6 8 5 5 2 4 6 6
5 6 5 0 1 4 5 6 5 7
5 1 3 10 6 0 0 6 7 8
7 10 3 5 2 10 9 10 3 10

Parameters

a	The input array
end	The lcoation at the end 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

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

Mk Qsort

See the group documentation

Example 19

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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 functor
     mk_qsort(arrs.begin(), arrs.end(), (std::size_t)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

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 each subarray to start sorting with, starting at zero
term	The object at the end of each subarray
keyfunc	The functor to get keys from each subarray

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

R Mk Qsort

See the goup documentation

Example 20

#include <codecogs\computing\sort\multikey_quicksort.h>
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
using namespace Computing::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 functor
     r_mk_qsort(arrs.begin(), arrs.end(), (std::size_t)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 0 8 4 4 0 3 3 5 8
1 1 6 8 5 5 2 4 6 6
5 6 5 0 1 4 5 6 5 7
5 1 3 10 6 0 0 6 7 8
7 10 3 5 2 10 9 10 3 10

Parameters

a	The input array
end	The location at the end 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
keyfunc	The functor to get key values from each subarray

Returns

none

Authors

Sam Schetterer (June 2007)

Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.