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.

What you can learn here / tips and tricks

1. If you implement an algorithm that has plenty of code examples, go ahead and use them to speed up the process.
2. Do not use nested macros that require some wildcard parameter. This doesn't work due to an unreal Engine Issue: Official Issue Tracker Entry
3. You cannot save a wildcard variable in a macro. A workaround is to use the wildcard array that you have been given by the first parameter and temporarily add an extra entry to the end of it.
4. If you require dynamic logic like the comparison here you can use a sequence node and a dedicated execution pin out to allow hooking in some graph work to your macro.

The Algorithm

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

Performance

On very short arrays the algorithm might be slower than other simpler ones. In fact this doesn't really matter as calclation times are short anyways. Where Quicksort really shines are long unsorted arrays. The average performance is described as O(n log n), meaning to double the performance cost you will have to square the array length.

Implementation

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;
	}

Due to an issue creating different macros for each function is currently impossible. You would not be able to call the nested macros. In the graph implementation the comment blocks signal what belongs to each function.