Inviting comment on this QuickSort implementation, adapted from a Python repo.
Thinking it would be fun to translate a few useful algorithms.
One sensitive part is the number of times data is copied, particularly interested in knowing if there are more efficient ways than the Pushes below.
This is for an alpha-numeric sort. I realize it would be simple to generalize and pass a comparison function, but I'm thinking it's faster that way, and easy enough to make a dedicated QuickSort for other comparisons (three lines to change!)
Thanks in advance for any thoughts.
Code: Select all
QuickSort_Alnum(original_object) {
; Index values do NOT need to be contiguous
; For quasi-sorted arrays, performance degrades as we always pop
; IMPORTANT: Custom Sorts (e.g. by length of string, by third subarray element etc.)
; Rather than passing a sort function, to speed things up, it's easy enough
; to make a different QuickSort function for each kind of sort
; => TO MAKE A NEW QUICKSORT, COPY AND EDIT THE THREE LINES COMMENTED BELOW
to_sort := original_object.Clone() ; popping will deplete the original array
if (to_sort.Count() <= 1) {
return to_sort
}
pivot := to_sort.Pop()
less_than_pivot := []
more_than_pivot := []
for i, to_stash in to_sort {
; LINE-TO-EDIT #1 for Custom Sort (only the comparison condition)
if (to_stash < pivot) {
less_than_pivot.Push(to_stash)
}
else {
more_than_pivot.Push(to_stash)
}
}
; LINE-TO-EDIT #2 for Custom Sort (just the function name: we recurse)
sort_builder := QuickSort_Alnum(less_than_pivot)
sort_builder.Push(pivot)
; LINE-TO-EDIT #3 for Custom Sort (just the function name: we recurse)
sorted_above := QuickSort_Alnum(more_than_pivot)
sort_builder.Push(sorted_above*)
return sort_builder
}
Code: Select all
a := [5,22,77,4,1,55,4]
b := QuickSort_Alnum(a)
/*
1 : 1
2 : 4
3 : 4
4 : 5
5 : 22
6 : 55
7 : 77
*/
Note that the keys are not contiguous, nor are they all integer.
Code: Select all
a := {1: "carrots", 4: "bananas", 212: 24, 256: "apples", "test": "bananas"}
b := QuickSort_Alnum(a)
/*
1 : 24
2 : apples
3 : bananas
4 : bananas
5 : carrots
*/
Replace if (to_stash < pivot) { with:
Code: Select all
if (StrLen(to_stash) < StrLen(pivot)) {
The pivot is the first popped element of the array. This works in randomly organized arrays, but in quasi-sorted arrays this causes performance to degrade towards O(n-square). For arrays with contiguous index values starting with 1, another common approach would be to pick a value in the middle of the array: pivot := arr[length//2] then loop in two sections on either sides of the pivot.