### QuickSort: any thoughts to improve this?

Posted:

**03 May 2019, 17:46**Howdy all!

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.

Replace if (to_stash < pivot) { with:

The

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

**Sample Use #1**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
*/
```

**Sample Use #2***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
*/
```

**Sample Modification: Sort by Length**Replace if (to_stash < pivot) { with:

Code: Select all

```
if (StrLen(to_stash) < StrLen(pivot)) {
```

**Design Considerations**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.