QuickSort: any thoughts to improve this?

Post your working scripts, libraries and tools
freespacing
Posts: 97
Joined: 28 Sep 2016, 11:14
Contact:

QuickSort: any thoughts to improve this?

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.

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) {
}

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.
Last edited by freespacing on 04 May 2019, 08:12, edited 12 times in total.
carno
Posts: 200
Joined: 20 Jun 2014, 16:48

Re: QuickSort

Could you provide a concrete example and how this function is implemented?
freespacing
Posts: 97
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort

carno wrote:
04 May 2019, 03:25
Could you provide a concrete example and how this function is implemented?
Great idea. Edited the original post, adding examples and musings. Looking forward to your thoughts.
freespacing
Posts: 97
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

EDIT

Indexes no longer need to be contiguous, i.e. will work with:

Code: Select all

``a := {1: "carrots", 4: "bananas", 212: 24, 256: "apples", "test": "bananas"}``
Instead of looping with an index, the new version clones the original array and pops elements.
rommmcek
Posts: 648
Joined: 15 Aug 2014, 15:18

Re: QuickSort: any thoughts to improve this?

Hi!
Quick sort is a nice algorithm. However I have truble with your version/translation for big files.
Crash for files above ca. 200k lines (alphanumerical), and above ca. 6k lines (by length).
swagfag
Posts: 2838
Joined: 11 Jan 2017, 17:59

Re: QuickSort: any thoughts to improve this?

the only way to not have it crash is rewriting the algorithm w/o the recursion
carno
Posts: 200
Joined: 20 Jun 2014, 16:48

Re: QuickSort

freespacing wrote:
04 May 2019, 03:53
carno wrote:
04 May 2019, 03:25
Could you provide a concrete example and how this function is implemented?
Great idea. Edited the original post, adding examples and musings. Looking forward to your thoughts.
Thanks! I'm going to test it now.
Helgef
Posts: 3892
Joined: 17 Jul 2016, 01:02
Contact:

Re: QuickSort: any thoughts to improve this?

More on quick sort here. My snippet in the above thread isn't recursive on the ahk side.

Cheers, and thank for sharing.
Sam_
Posts: 106
Joined: 20 Mar 2014, 20:24

Re: QuickSort: any thoughts to improve this?

swagfag wrote:
05 May 2019, 13:38
the only way to not have it crash is rewriting the algorithm w/o the recursion
FWIW, the version of quicksort without recursions that I use can be found here.
evilC
Posts: 4726
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

Just for fun, I had a stab at a sort algorithm - it completes the sort in 9 iterations

Code: Select all

``````#SingleInstance force
OutputDebug DBGVIEWCLEAR

a := {1: "carrots", 4: "bananas", 212: 24, 256: "apples", "test": "bananas"}
expected := ["24", "apples", "bananas", "bananas", "carrots"]
iteration := 0
out := DoSort(a, iteration)

for k, v in expected {
if (out[k] != v){
throw "Expecting item " k " to be " v ", but got " out[k]
}
}

OutputDebug % "AHK| Done in " iteration " iterations"
return

DoSort(arr, byRef iteration){
out := []
for k, v in arr {
out.Push(v)
}
max := out.Length()
i := 1
iteration := 0
resumeAt := 0
while (i < max){
iteration++
i1 := out[i]
i2 := out[i + 1]
OutputDebug % "AHK| Iteration " iteration ". Pos = " i ", Comparing " i1 " and " i2 ", List = " Join(",", out*)
if (i1 > i2){
ri := out.RemoveAt(i)
out.InsertAt(i + 1, ri)
i --
OutputDebug % "AHK| switching " i1 " and " i2 ", going back to pos " i
} else {
i := NextI(i, resumeAt)
}
if (i < 1){
i := NextI(i, resumeAt)
}
if (i > resumeAt){
resumeAt := i
OutputDebug % "AHK| setting resumeAt to " resumeAt
}
}
return out
}

NextI(i, resumeAt){
if (resumeAt){
i := resumeAt + 1
resumeAt := 0
OutputDebug % "AHK| resuming at pos " i
} else {
i++
OutputDebug % "AHK| advancing to pos " i
}
return i
}

Join(sep, params*) {
for index,param in params
str .= sep . param
return SubStr(str, StrLen(sep)+1)
}

^Esc::
ExitApp
``````

Code: Select all

``````[6736] AHK| Iteration 1. Pos = 1, Comparing carrots and bananas, List = carrots,bananas,24,apples,bananas
[6736] AHK| switching carrots and bananas, going back to pos 0
[6736] AHK| advancing to pos 1
[6736] AHK| setting resumeAt to 1
[6736] AHK| Iteration 2. Pos = 1, Comparing bananas and carrots, List = bananas,carrots,24,apples,bananas
[6736] AHK| resuming at pos 2
[6736] AHK| setting resumeAt to 2
[6736] AHK| Iteration 3. Pos = 2, Comparing carrots and 24, List = bananas,carrots,24,apples,bananas
[6736] AHK| switching carrots and 24, going back to pos 1
[6736] AHK| Iteration 4. Pos = 1, Comparing bananas and 24, List = bananas,24,carrots,apples,bananas
[6736] AHK| switching bananas and 24, going back to pos 0
[6736] AHK| resuming at pos 3
[6736] AHK| setting resumeAt to 3
[6736] AHK| Iteration 5. Pos = 3, Comparing carrots and apples, List = 24,bananas,carrots,apples,bananas
[6736] AHK| switching carrots and apples, going back to pos 2
[6736] AHK| Iteration 6. Pos = 2, Comparing bananas and apples, List = 24,bananas,apples,carrots,bananas
[6736] AHK| switching bananas and apples, going back to pos 1
[6736] AHK| Iteration 7. Pos = 1, Comparing 24 and apples, List = 24,apples,bananas,carrots,bananas
[6736] AHK| resuming at pos 4
[6736] AHK| setting resumeAt to 4
[6736] AHK| Iteration 8. Pos = 4, Comparing carrots and bananas, List = 24,apples,bananas,carrots,bananas
[6736] AHK| switching carrots and bananas, going back to pos 3
[6736] AHK| Iteration 9. Pos = 3, Comparing bananas and bananas, List = 24,apples,bananas,bananas,carrots
[6736] AHK| resuming at pos 5
[6736] AHK| setting resumeAt to 5
[6736] AHK| Done in 9 iterations
``````
nnnik
Posts: 4242
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: QuickSort: any thoughts to improve this?

Is that bubble sort?
Recommends AHK Studio
freespacing
Posts: 97
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

@evilC Cool, sorting is fun! At a glance, it looks like badly sorted items are bubbling up, would you say that it is in fact a bubble sort? Didn't try to fully trace the logic. But did notice that at the beginning of DoSort(arr, byRef iteration) you initialize iteration with iteration := 0, am I missing something or is the iteration arg redundant (leftover from previous version)?
evilC
Posts: 4726
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

I have no idea what it is called, I did not draw upon anything, I just worked it out myself
Yeah, it needs work
Doing it on paper, I think it should take 7 iterations
evilC
Posts: 4726
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

This seems better, does it in 8

Code: Select all

``````#SingleInstance force
OutputDebug DBGVIEWCLEAR

a := {1: "carrots", 4: "bananas", 212: 24, 256: "apples", "test": "bananas"}
expected := ["24", "apples", "bananas", "bananas", "carrots"]
iteration := 0
out := DoSort(a, iteration)

for k, v in expected {
if (out[k] != v){
throw "Expecting item " k " to be " v ", but got " out[k]
}
}

OutputDebug % "AHK| Done in " iteration " iterations"
return

DoSort(arr, byRef iteration){
out := []
for k, v in arr {
out.Push(v)
}
max := out.Length()
i := 1
iteration := 0
resumeAt := 0
while (i < max){
iteration++
i1 := out[i]
i2 := out[i + 1]
OutputDebug % "AHK| Iteration " iteration ". Pos = " i ", ResumeAt = " resumeAt ", Comparing " i1 " and " i2 ", List = " Join(",", out*)
didSwap := 0
if (i1 > i2){
ri := out.RemoveAt(i)
out.InsertAt(i + 1, ri)
didSwap := 1
} else {
didSwap := 0
}
if (didSwap){
if (i > resumeAt)
resumeAt := i
i--
}
if (!didSwap || i == 0) {
if (resumeAt){
i := resumeAt
resumeAt := 0
}
i++
}
}
return out
}
``````

Code: Select all

``````[11404] AHK| Iteration 1. Pos = 1, ResumeAt = 0, Comparing carrots and bananas, List = carrots,bananas,24,apples,bananas
[11404] AHK| Iteration 2. Pos = 2, ResumeAt = 0, Comparing carrots and 24, List = bananas,carrots,24,apples,bananas
[11404] AHK| Iteration 3. Pos = 1, ResumeAt = 2, Comparing bananas and 24, List = bananas,24,carrots,apples,bananas
[11404] AHK| Iteration 4. Pos = 3, ResumeAt = 0, Comparing carrots and apples, List = 24,bananas,carrots,apples,bananas
[11404] AHK| Iteration 5. Pos = 2, ResumeAt = 3, Comparing bananas and apples, List = 24,bananas,apples,carrots,bananas
[11404] AHK| Iteration 6. Pos = 1, ResumeAt = 3, Comparing 24 and apples, List = 24,apples,bananas,carrots,bananas
[11404] AHK| Iteration 7. Pos = 4, ResumeAt = 0, Comparing carrots and bananas, List = 24,apples,bananas,carrots,bananas
[11404] AHK| Iteration 8. Pos = 3, ResumeAt = 4, Comparing bananas and bananas, List = 24,apples,bananas,bananas,carrots
[11404] AHK| Done in 8 iterations
``````
evilC
Posts: 4726
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

freespacing wrote:
08 May 2019, 08:51
@evilC Cool, sorting is fun! At a glance, it looks like badly sorted items are bubbling up, would you say that it is in fact a bubble sort? Didn't try to fully trace the logic. But did notice that at the beginning of DoSort(arr, byRef iteration) you initialize iteration with iteration := 0, am I missing something or is the iteration arg redundant (leftover from previous version)?

Code: Select all

``````	iteration := 0
resumeAt := 0
while (i < max){
iteration++
``````
the iteration var counts how many times it went through the while loop - each iteration will be potentially swapping two adjacent elements
freespacing
Posts: 97
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

evilC wrote:
08 May 2019, 09:21
the iteration var counts how many times
Yes, that was clear to me. What I'm not grokking is why it's an argument to the DoSort function, when it's immediately set to zero.
Sorry if my question wasn't clear.

Code: Select all

``````DoSort(arr, byRef iteration){ ; <<<=== iteration is an argument
(...)
iteration := 0 ; <<<=== but it is immediately set to zero
``````
evilC
Posts: 4726
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

Because it's byref (So if i alter the value inside the function, it's altered outside) - the return value of the function is the sorted array
I could have just used a global

This implementation is a bit simpler, and yields the same result:

Code: Select all

``````#SingleInstance force
OutputDebug DBGVIEWCLEAR

a := {1: "carrots", 4: "bananas", 212: 24, 256: "apples", "test": "bananas"}
expected := ["24", "apples", "bananas", "bananas", "carrots"]
iteration := 0
;~ out := DoSort(a, iteration)
out := NewSort(a, iteration)

for k, v in expected {
if (out[k] != v){
throw "Expecting item " k " to be " v ", but got " out[k]
}
}

OutputDebug % "AHK| Done in " iteration " iterations"
return

NewSort(arr, byRef iteration){
out := []
for k, v in arr {
out.Push(v)
}
max := out.Length()
Loop % max - 1 {
_NewSort(out, A_Index + 1, iteration)
}

return out
}

_NewSort(arr, start, byRef iteration){
Loop % start - 1 {
iteration++
i := start - A_Index
i1 := arr[i]
i2 := arr[i + 1]
str := "AHK| Iteration " iteration ". Pos = " i ", Comparing " i1 " and " i2 ", List = " Join(",", arr*) " - "
if (i1 > i2){
ri := arr.RemoveAt(i)
arr.InsertAt(i + 1, ri)
str .= "SWAP"
OutputDebug % str
} else {
str .= "NOSWAP"
OutputDebug % str
break
}
}
return arr
}

Join(sep, params*) {
for index,param in params
str .= sep . param
return SubStr(str, StrLen(sep)+1)
}
``````

Code: Select all

``````[6244] AHK| Iteration 1. Pos = 1, Comparing carrots and bananas, List = carrots,bananas,24,apples,bananas - SWAP
[6244] AHK| Iteration 2. Pos = 2, Comparing carrots and 24, List = bananas,carrots,24,apples,bananas - SWAP
[6244] AHK| Iteration 3. Pos = 1, Comparing bananas and 24, List = bananas,24,carrots,apples,bananas - SWAP
[6244] AHK| Iteration 4. Pos = 3, Comparing carrots and apples, List = 24,bananas,carrots,apples,bananas - SWAP
[6244] AHK| Iteration 5. Pos = 2, Comparing bananas and apples, List = 24,bananas,apples,carrots,bananas - SWAP
[6244] AHK| Iteration 6. Pos = 1, Comparing 24 and apples, List = 24,apples,bananas,carrots,bananas - NOSWAP
[6244] AHK| Iteration 7. Pos = 4, Comparing carrots and bananas, List = 24,apples,bananas,carrots,bananas - SWAP
[6244] AHK| Iteration 8. Pos = 3, Comparing bananas and bananas, List = 24,apples,bananas,bananas,carrots - NOSWAP
[6244] AHK| Done in 8 iterations
``````
Last edited by evilC on 08 May 2019, 09:53, edited 1 time in total.
freespacing
Posts: 97
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

Oh, thank you for explaining that, I had forgotten about that way of returning multiple values — so used to returning objects.
evilC
Posts: 4726
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

Yeah, i very very rarely use it myself
nnnik
Posts: 4242
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: QuickSort: any thoughts to improve this?

Yeah swapping 2 adjacent elements if they are in the wrong order is bubble sort.

https://en.wikipedia.org/wiki/Bubble_sort
Recommends AHK Studio