Sort function for DynamicArray

[tbone]

The function:

Code: Select all

/**
 * Sort for DynamicArray (Gnome sort. [Best: O(n), Worst: O(n^2), Mem: O(1)])
 **/
void DynamicArraySort(DynamicArray *v, int (*cmpfn)(void *a, void *b)) {
	int i = 1;
	int j = 2;
	void *tmp;
	
	// maybe add null pointer detection here?
	// if we did, we can't store ints in the void *
	// so I guess leave it for the cmp function?
	while (i < v->cur_size) {
		if (cmpfn(v->data[i-1], v->data[i]) < 1) {
			i = j;
			j++;
		} else {
			tmp = v->data[i-1];
			v->data[i-1] = v->data[i];
			v->data[i] = tmp;
			i--;
			if (i == 0) i = 1;
		}
	}
}

Example Usage:

Code: Select all

int cmp1(void *a, void *b) {
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
}

/**
 * Main
 **/
int main(void) {
	PrintConsole topScreen;
	PrintConsole bottomScreen;
	int i;
	
	videoSetMode(MODE_0_2D);
	vramSetBankA(VRAM_A_MAIN_BG);
	consoleInit(&topScreen, 3,BgType_Text4bpp, BgSize_T_256x256, 31, 0, true, true);
	
	videoSetModeSub(MODE_0_2D);
	vramSetBankC(VRAM_C_SUB_BG);
	consoleInit(&bottomScreen, 3,BgType_Text4bpp, BgSize_T_256x256, 31, 0, false, true);
	
/* sort test */

	// create array
	DynamicArray a;
	DynamicArrayInit(&a, 20);
	
	// put some random numbers into it
	srand((unsigned)time(NULL));
	for (i = 0; i < 20; i++)
		DynamicArraySet(&a, i, (void *)rand());

	consoleSelect(&topScreen);
	consoleClear();
	iprintf("Unsorted Random Data\n");
	for (i = 0; i < 20; i++)
		iprintf("[%2.2i] [%11.11i]\n", i, (int)DynamicArrayGet(&a, i));

	swiWaitForVBlank(); // we put this here so we know at least the top will
						// display incase below locks up for some reason.

	consoleSelect(&bottomScreen);
	consoleClear();
	iprintf("Sorted Random Data\n");
	DynamicArraySort(&a, &cmp1);
	for (i = 0; i < 20; i++)
		iprintf("[%2.2i] [%11.11i]\n", i, (int)DynamicArrayGet(&a, i));

	wh29 swi1) swiWaitForVBlank();
/* end sort test */

Not sure how to handle the dynamic growing, where some of the pointers might be null. The test above uses ints inside of the pointers, so 0 != NULL. Also, iterating it based in array->cur_size might not be too great if memory is allocated in chunks. I haven't looked at the libnds code much itself yet.