Quicksort

This download contains a macro library with the Quicksort macro to satisfy all your needs when it comes to sorting Arrays in your Graph!

Installment Instructions

You can download the files HERE.

1. After the download unpack the zip.

2. Navigate to \ARKDevKit\Projects\ShooterGame\Content\Mods and drop the unpacked file in the Mods folder.

2.1. If you like to install to another folder please follow the first step and later move the files with the content browser in the kit. Installing directly to another folder might break the files.

3. The installment is now already completed.

4. Once in the kit you should see a function and a macro library inside the corresponding folder.

The macro library is all you need for the Quicksort algorithm. The function library contains the graph I use in the following examples to compare two strings. You might have a use for this.

Node Usage

Quicksort

Pull up the node by right clicking anywhere in a graph and searching for "Quicksort". You will find the macro under Utilities -> Array.

To call the macro hook up the Exec pin to an execution line and connect an Array.

Getting the sorting working requires you to add your own logic. This part determines if one element is “smaller” than the other and should therefore be at an earlier index in the Array. Attach your logic to the Comparison Body pin and the Element1 and 2 pins as seen in the picture. The result has to be Boolean and goes into the 1<2 pin.

After the sorting has finished the Completed pin will fire and the modified array will be returned.

Warning: The macro modifies the input array directly and does not create a second array!

Compare String

This node is fairly simple and self-explanatory. It compares the letters of a string based on their corresponding ASCII numbers.

The Algorithm

Quicksort is known as one of the best sorting algorithms. You can find an in depth explanation over at Wikipedia.

The common approach is to use recursive function calls to achieve the desired effect. Due to technical limitations in macros and no way to use undetermined / wildcard variable types in functions this implementation goes the iterative approach. As there are already plenty of code examples on the internet it is very useful to base the graph on one working code. I chose the following relatively simple java code : Source

	/* * iterative implementation of quicksort sorting algorithm. */ public static void iterativeQsort(int[] numbers) {
		Stack stack = new Stack();
		stack.push(0);
		stack.push(numbers.length);
		while (!stack.isEmpty()) {
			int end = stack.pop();
			int start = stack.pop();
			if (end - start < 2) {
				continue;
			}
			int p = start + ((end - start) / 2);
			p = partition(numbers, p, start, end);
			stack.push(p + 1);
			stack.push(end);
			stack.push(start);
			stack.push(p);
		}
	}

	/*
	 * * Utility method to partition the array into smaller array, and *
	 * comparing numbers to rearrange them as per quicksort algorithm.
	 */ private static int partition(int[] input, int position, int start, int end) {
		int l = start;
		int h = end - 2;
		int piv = input[position];
		swap(input, position, end - 1);
		while (l < h) {
			if (input[l] < piv) {
				l++;
			} else if (input[h] >= piv) {
				h--;
			} else {
				swap(input, l, h);
			}
		}
		int idx = h;
		if (input[h] < piv) {
			idx++;
		}
		swap(input, end - 1, idx);
		return idx;
	}

	/**
	 * * Utility method to swap two numbers in given array * * @param arr -
	 * array on which swap will happen * @param i * @param j
	 */
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}