Problem
Given an array having 16000 unique integers, each lying within the range 1<x<20000,
how do u sort it. U can load only 1000 numbers at a time in memory.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Sort an array with unique elements
Created Data : 28-07-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
#define SETBIT(value, pos) ((value) |= (1 << (pos)))
#define GETBIT(value, pos) ((value) & (1 << (pos)))
void SetBits(int* arr, int len, unsigned char* signs)
{
int index;
int pos;
for(int i = 0; i < len; ++i){
arr[i] --;
index = arr[i] >> 3;
pos = arr[i] % 8;
SETBIT(signs[index], pos);
}
}
void SortArray(int* arr, int len, int range, int chopLen)
{
size_t signsLen = (range + 7) / 8;
unsigned char* signs = new unsigned char[signsLen];
memset(signs, 0, signsLen);
int i;
int iterCount = len / chopLen * chopLen;
for(i = 0; i < iterCount; i += chopLen){
SetBits(arr + i, chopLen, signs);
}
SetBits(arr + i, len - i, signs);
int k(0);
for(int i = 0; i < signsLen; ++i){
if(k >= len) break;
for(int j = 0; j < 8; j ++){
if(GETBIT(signs[i], j)){
arr[k++] = i * 8 + j + 1;
}
}
}
delete[] signs;
}
void DoTest(int* arr, int len, int range, int chopLen)
{
cout << "The length of array is " << len << endl;
cout << "The range of array is (1, " << range << ")" << endl;
cout << "The chop size is " << chopLen << endl;
cout << "The array before sorting is " << endl;
for(int i = 0; i < len; ++ i){
cout << setw(4) << arr[i];
}
cout << endl;
SortArray(arr, len, range, chopLen);
cout << "The array after sorting is " << endl;
for(int i = 0; i < len; ++ i){
cout << setw(4) << arr[i];
}
cout << endl;
cout << "------------------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {5, 4, 3, 2, 1, 8, 9, 12, 14, 16, 17};
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 20, 8);
int arr1[] = {5, 4, 3, 2, 1, 8, 9, 12, 14, 16, 17};
DoTest(arr1, sizeof(arr1)/sizeof(arr1[0]), 20, 3);
int arr2[] = {5, 4, 3, 2, 1, 8, 9, 12, 14, 16, 17};
DoTest(arr2, sizeof(arr2)/sizeof(arr2[0]), 100, 3);
int arr3[] = {5, 4, 3, 2, 1, 8, 9, 12, 14, 16, 17, 100};
DoTest(arr3, sizeof(arr3)/sizeof(arr3[0]), 100, 3);
int arr4[] = {5, 4, 3, 2, 1, 8, 9, 12, 14, 16, 17, 200};
DoTest(arr4, sizeof(arr4)/sizeof(arr4[0]), 200, 3);
int arr5[] = {200};
DoTest(arr5, sizeof(arr5)/sizeof(arr5[0]), 200, 3);
int arr6[] = {200, 2};
DoTest(arr6, sizeof(arr6)/sizeof(arr6[0]), 200, 3);
return 0;
}
Output
The length of array is 11
The range of array is (1, 20)
The chop size is 8
The array before sorting is
5 4 3 2 1 8 9 12 14 16 17
The array after sorting is
1 2 3 4 5 8 9 12 14 16 17
------------------------------------------
The length of array is 11
The range of array is (1, 20)
The chop size is 3
The array before sorting is
5 4 3 2 1 8 9 12 14 16 17
The array after sorting is
1 2 3 4 5 8 9 12 14 16 17
------------------------------------------
The length of array is 11
The range of array is (1, 100)
The chop size is 3
The array before sorting is
5 4 3 2 1 8 9 12 14 16 17
The array after sorting is
1 2 3 4 5 8 9 12 14 16 17
------------------------------------------
The length of array is 12
The range of array is (1, 100)
The chop size is 3
The array before sorting is
5 4 3 2 1 8 9 12 14 16 17 100
The array after sorting is
1 2 3 4 5 8 9 12 14 16 17 100
------------------------------------------
The length of array is 12
The range of array is (1, 200)
The chop size is 3
The array before sorting is
5 4 3 2 1 8 9 12 14 16 17 200
The array after sorting is
1 2 3 4 5 8 9 12 14 16 17 200
------------------------------------------
The length of array is 1
The range of array is (1, 200)
The chop size is 3
The array before sorting is
200
The array after sorting is
200
------------------------------------------
The length of array is 2
The range of array is (1, 200)
The chop size is 3
The array before sorting is
200 2
The array after sorting is
2 200
------------------------------------------
Press any key to continue . . .