QuickSort: any thoughts to improve this?

Post your working scripts, libraries and tools for AHK v1.1 and older
freespacing
Posts: 150
Joined: 28 Sep 2016, 11:14
Contact:

QuickSort: any thoughts to improve this?

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.

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

Re: QuickSort

04 May 2019, 03:25

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

Re: QuickSort

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.
freespacing
Posts: 150
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

04 May 2019, 08:00

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.
User avatar
rommmcek
Posts: 1470
Joined: 15 Aug 2014, 15:18

Re: QuickSort: any thoughts to improve this?

05 May 2019, 13:12

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: 6222
Joined: 11 Jan 2017, 17:59

Re: QuickSort: any thoughts to improve this?

05 May 2019, 13:38

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

Re: QuickSort

06 May 2019, 06:54

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: 4709
Joined: 17 Jul 2016, 01:02
Contact:

Re: QuickSort: any thoughts to improve this?

07 May 2019, 11:56

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

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

Re: QuickSort: any thoughts to improve this?

07 May 2019, 21:33

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.
User avatar
evilC
Posts: 4822
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

08 May 2019, 08:13

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
User avatar
nnnik
Posts: 4500
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: QuickSort: any thoughts to improve this?

08 May 2019, 08:42

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

Re: QuickSort: any thoughts to improve this?

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)?
User avatar
evilC
Posts: 4822
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

08 May 2019, 09:18

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
User avatar
evilC
Posts: 4822
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

08 May 2019, 09:21

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: 150
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

08 May 2019, 09:26

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
User avatar
evilC
Posts: 4822
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

08 May 2019, 09:45

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: 150
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

08 May 2019, 09:53

Oh, thank you for explaining that, I had forgotten about that way of returning multiple values — so used to returning objects.
User avatar
nnnik
Posts: 4500
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: QuickSort: any thoughts to improve this?

09 May 2019, 00:57

Yeah swapping 2 adjacent elements if they are in the wrong order is bubble sort.
Image
https://en.wikipedia.org/wiki/Bubble_sort
Recommends AHK Studio

Return to “Scripts and Functions (v1)”

Who is online

Users browsing this forum: gwarble, IfThenElse, TheNaviator, TOTAL and 136 guests