nested-array-sort.cpp

//Nested array sort

#include <cstring> //memmove

//#define DIAGNOSTICS
#ifdef DIAGNOSTICS
#include <iostream>
#endif


/****************************************************************
NESTED ARRAY SORT************************************************
*****************************************************************
-The idea behind nested array sort is to put elements in order with few move operations. This is accomplished by creating an array, which will be populated
with sorted elements, and only adding additional elements if there are few prior elements that will have to be moved. If too many prior elements would
have to be moved, the element will be placed into a nested array associated with its position in the parent array
-Elements can be moved higher or lower in a sorted array to create space for the new inserted element, so as long as the new element is close to the 
beginning or end of the sorted array, it can be inserted.
-When an additional element is added but does not fit the criteria for including it in the array, it falls down to a nested array. This nested array is 
associated with the smaller of the two elements in the parent array it falls between.

Example:
{2} - First element
{23} - Second element 3 is greater than all elements in the array, put it at the end
{023} - Third element 0 is less than all elements in the array, put it at the beginning
{0!23} 0:{1} - Inserting fourth element 1 would require move operations, so put it in a nested array associated with the smaller of the two elements it falls 
between

When all elements have been sorted, the full, sorted array can be constructed by starting at the first element of the parent array and copying the elements to 
an array. After copying each element, check to see if the element has a nested array associated with it, as that nested array will contain values between it 
and the next element in the parent

This sorting method can get very memory intensive in trade for speed (O(N^2))
*****************************************************************/


//TODO:
//Determine optimized formulas for determining whether to insert an element or send it into a nested array. 
//	Square root of the amount of elements to be sorted seems good. Can also make it a function of how many elements are left to sort 
//	(if there are a lot of elements that remain to be sorted, moving multiple elements may pay dividends in the long run because subsequent searches
//	will be searching through more elements in higher parent array rather than searching through many small nested arrays.)
//Try to consider/formulate ways to cut down on memory cost. Memory use becomes highly fragmented due to the worst-case-scenario memory allocation
//Move binary search to its own function

#include "nested-array-sort.h"

int numElements;//Keep track of how much memory is used
int numContainers;//Keep track of the total amount of arrays


//elementContainer data struct contains values of beginning index and ending index, and an array for all the elements it contains
struct elementContainer{
	element *array;
	int firstElementIndex;
	int lastElementIndex;
};


//Element data struct contains the value of the element and the nested array that may be associated with it (nullptr if none is)
struct element{
	int val;
	elementContainer *nestedContainer;
};


//Returns the maximum number of elements to move when inserting an element. If the number of moves exceeds this, drop the element into a nested array.
int maxElementMoves(){
	return 100;
}


//Insert an element into the elementContainer
void insertElement(int value,elementContainer* destination,const int &remainingUnsortedElements,elementContainer* const allContainers, element* const allElements){
	
	bool isHigherThanMedian;
	int valuePosition; //The index of the greatest value less than or equal to the value to be inserted
	int low;
	int high;
	int mid;
	
	//Loop until the element is inserted
	while(true){
	
	
	low = destination->firstElementIndex;
	high = destination->lastElementIndex;
	mid = (low+high) / 2;
	
	//Check to see if the value to insert is higher or lower than the median, while updating low / high value for binary search
	if(value >= destination->array[mid].val){
		isHigherThanMedian = true;
		low = mid + 1;
	}
	else{
		isHigherThanMedian = false;
		high = mid - 1;
	}
	
	
	//binary search
	while(low < high){
		mid = (low + high) / 2;
		
		if(value >= destination->array[mid].val)
			low = mid + 1;
		else
			high = mid - 1;
	}
	
	
	//use high to compare and assign, (either low or high work, but consistency is needed)
	//This index is either the valuePosition or 1 higher than the valuePosition
	if(value >= destination->array[high].val)
		valuePosition = high;
	else
		valuePosition = high - 1;
	
	
	//if the value to be inserted is higher than the median then inserting it would move all elements greater than it 1 index higher.
	//The opposite is done if the value is lower than the median (all elements less than or equal to the value to be inserted are moved an index lower)
	if(isHigherThanMedian){
		
		//if the value is close enough to the edge of the array, move the elements in the array to insert the element.
		//else insert the element into a nested array
		if(destination->lastElementIndex - valuePosition <= maxElementMoves()){
			//move the elements in the array over, insert the new value, and return
			memmove(destination->array + valuePosition + 2,destination->array + valuePosition + 1,
				sizeof(element) * (destination->lastElementIndex - valuePosition));
			destination->array[valuePosition + 1].val = value;
			destination->array[valuePosition + 1].nestedContainer = nullptr;
			++destination->lastElementIndex;
			return;
		}
		else{
			//if a nested array already exists
			if(destination->array[valuePosition].nestedContainer != nullptr){
				destination = destination->array[valuePosition].nestedContainer;
				continue;
			}
			//else create a nested array and assign it memory
			else{
				destination->array[valuePosition].nestedContainer = allContainers + numContainers;
				++numContainers;
				
				destination->array[valuePosition].nestedContainer->array = allElements + numElements;
				numElements += 2*remainingUnsortedElements;
				destination->array[valuePosition].nestedContainer->firstElementIndex = remainingUnsortedElements;
				destination->array[valuePosition].nestedContainer->lastElementIndex = destination->array[valuePosition].nestedContainer->firstElementIndex;
				destination->array[valuePosition].nestedContainer->array[destination->array[valuePosition].nestedContainer->firstElementIndex].val = value;
				destination->array[valuePosition].nestedContainer->array[destination->array[valuePosition].nestedContainer->firstElementIndex].nestedContainer = nullptr;
				return;
			}
		}
		
	}
	else{
		
		//if the value is close enough to the edge of the array, move the elements in the array to insert the element.
		//else insert the element into a nested elementContainer
		if(valuePosition - destination->firstElementIndex <= maxElementMoves()){
			//move the elements in the array over, insert the new value, and return
			memmove(destination->array + destination->firstElementIndex - 1,destination->array + destination->firstElementIndex,
				sizeof(element) * (valuePosition - destination->firstElementIndex + 1));
			destination->array[valuePosition].val = value;
			destination->array[valuePosition].nestedContainer = nullptr;
			--destination->firstElementIndex;
			return;
		}
		else{
			//if a nested elementContainer already exists
			if(destination->array[valuePosition].nestedContainer != nullptr){
				destination = destination->array[valuePosition].nestedContainer;
				continue;
			}
			//else create a nested elementContainer and assign it memory
			else{
				destination->array[valuePosition].nestedContainer = allContainers + numContainers;
				++numContainers;
				
				destination->array[valuePosition].nestedContainer->array = allElements + numElements;
				numElements += 2*remainingUnsortedElements;
				destination->array[valuePosition].nestedContainer->firstElementIndex = remainingUnsortedElements;
				destination->array[valuePosition].nestedContainer->lastElementIndex = destination->array[valuePosition].nestedContainer->firstElementIndex;
				destination->array[valuePosition].nestedContainer->array[destination->array[valuePosition].nestedContainer->firstElementIndex].val = value;
				destination->array[valuePosition].nestedContainer->array[destination->array[valuePosition].nestedContainer->firstElementIndex].nestedContainer = nullptr;
				return;
			}
		}
	}
	
	

	}//End while loop
}


//Class to extract the elements from their nested elementContainers and put them in the correct, sorted order into a standard array
class ElementToArrayPlacer {
	static int index;
	static void place(elementContainer *source, int *array){
		for(int i = source->firstElementIndex; i <= source->lastElementIndex; ++i){
			array[index] = source->array[i].val;
			++index;
			if(source->array[i].nestedContainer != nullptr){
				place(source->array[i].nestedContainer, array);
			}
		}
	}
	
	public:
	static void placeElementsInArray(elementContainer *source, int *array){
		index = 0;
		place(source, array);
	}
};
int ElementToArrayPlacer::index;


//Allocates memory for allContainers and allElements based on the array length
void allocateMemory(int arrayLength, elementContainer*& allContainers, element*& allElements){
	allContainers = new elementContainer[5000];
	allElements = new element[70'000'000];
}
//Deallocates memory for allContainers and allElements
void deallocateMemory(elementContainer*& allContainers, element*& allElements){
	delete[] allContainers;
	delete[] allElements;
	allContainers = nullptr;
	allElements = nullptr;
}


void nestedArraySort(int* array, int arrayLength){
	elementContainer* allContainers = nullptr;
	element* allElements = nullptr;
	allocateMemory(arrayLength,allContainers,allElements);
	nestedArraySort(array, arrayLength, allContainers, allElements);
	deallocateMemory(allContainers,allElements);
}


void nestedArraySort(int *array, int arrayLength, elementContainer* const allContainers, element* const allElements){
	if(arrayLength <= 1)
		return;
	
	int numElements = 0;
	int numContainers = 0;
	
	//Assign parent elementContainer
	elementContainer *parent = allContainers;
	++numContainers;
	
	//Assign the parent elementContainer's array
	parent->array = allElements; //2 times the array length, because the starting element is in the middle, and hypothetically the length of the array can span n elements to the end (each element higher than the previous) or n elements to the beginning (each element lower than the previous)
	numElements += 2*arrayLength;	//Subsequent arrays will be assigned at allElements[numElements] so that two arrays never overlap
	//Add the initial element
	parent->firstElementIndex = arrayLength;	//halfway between the beginning and end of parent->array
	parent->lastElementIndex = parent->firstElementIndex;
	parent->array[parent->firstElementIndex].val = array[0];
	parent->array[parent->firstElementIndex].nestedContainer = nullptr;
	
	//For each element
	int remainingUnsortedElements = arrayLength - 1;	//Number of elements minus the initial element
	for(int i = 1;i < arrayLength;++i){
		insertElement(array[i],parent,remainingUnsortedElements,allContainers,allElements);
		--remainingUnsortedElements;
	}
	
	ElementToArrayPlacer::placeElementsInArray(parent, array);
	
	#ifdef DIAGNOSTICS
	std::cout << "Number of elements in memory: " << numElements << "\n";
	std::cout << "Number of elementContainers in memory: " << numContainers << "\n";
	std::cout << "Size of elementContainer: " << sizeof(elementContainer) << ", size of element: " << sizeof(element) << "\nFor a total memory usage of: " << 
	sizeof(elementContainer) * numContainers + sizeof(element) * numElements << "\n";
	#endif
}