01 Snippet

# Source URL: https://dev.epicgames.com/community/snippets/90Da/fortnite-quicksort
# Local doc:  epic-docs/community/snippets/90Da/fortnite-quicksort.md
  # A divide-and-conquer sorting algorithm that divides an array into subarrays by selecting a pivot element.
  # Elements less than the pivot are sorted to left of the pivot, and elements greater than the pivot are sorted to the right.
  # The algorithm then divides into subarrays on either side of the pivot, and continues the process, selecting a new pivot each time.
  # At the end each of the sorted subarrays is merged together to get a fully sorted array.
  # This is a recursive implementation, where the function calls itself to quick sort the divided arrays.
  # The base case (the condition to stop the recursion) is the array has only one element.
  # This implementation always selects for the rightmost element as the initial pivot.
  # This is a generic implementation using parametric types, so you can provide your own type and your own comparison function as arguments.
  QuickSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
  QuickSortAtPivot(Array, 0, Array.Length - 1, Compare)
  QuickSortAtPivot<public>(Array:[]t, LowIndex:int, HighIndex:int, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
  if:
  # Check if the length of the array is greater than one. If not we've
  # reached the base case and should stop recursion.
  LowIndex < HighIndex
  # Sort the elements in the array by using the HighIndex (rightmost) element
  # as the Pivot. Return the index of the Pivot after sorting along with the sorted array.
  PartitionTuple := Partition(Array, LowIndex, HighIndex, Compare)
  PivotIndex := PartitionTuple(0)
  SortedArray := PartitionTuple(1)
  # Split the array into subarrays left and right of the pivot value.
  LeftHalf := SortedArray.Slice[LowIndex, PivotIndex]
  PivotVal := array{SortedArray[PivotIndex]}
  RightHalf := SortedArray.Slice[PivotIndex + 1]
  then:
  # Recursively sort the Left and Right subarrays.
  LeftArray := QuickSortAtPivot(LeftHalf, LowIndex, PivotIndex - 1, Compare)
  RightArray := QuickSortAtPivot(RightHalf, 0, RightHalf.Length - 1, Compare)