QuickSort: any thoughts to improve this?

Post your working scripts, libraries and tools
User avatar
evilC
Posts: 4740
Joined: 27 Feb 2014, 12:30

Re: QuickSort: any thoughts to improve this?

09 May 2019, 03:17

Mine does not quite work like that, it does it all in one pass
If it swaps, it moves left until it doesn't swap, then resumes where it left off

6 5 3 1 8 7 2 4
5 6
5 3 6
3 5 6
3 5 1 6
3 1 5 6
1 3 5 6
1 3 5 6 8
1 3 5 6 7 8
1 3 5 6 7 2 8
1 3 5 6 2 7 8
1 3 5 2 6 7 8
1 3 2 5 6 7 8
1 2 3 5 6 7 8
1 2 3 5 6 7 4 8
1 2 3 5 6 4 7 8
1 2 3 5 4 6 7 8
1 2 3 4 5 6 7 8
User avatar
nnnik
Posts: 4283
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: QuickSort: any thoughts to improve this?

09 May 2019, 08:14

Then I guess its a mix between insertion sort and bubble sort.
Recommends AHK Studio
freespacing
Posts: 97
Joined: 28 Sep 2016, 11:14
Contact:

Re: QuickSort: any thoughts to improve this?

09 May 2019, 08:30

Either way I believe it's O(n-squared), as opposed to O(n.log(n)) for quick-sort and merge-sort. Can be efficient for small arrays (in fact the hybrid Tim Sort -- Python standard -- uses Insertion Sort at some stage) but you'll feel a large difference as the set grows. Which takes nothing away from the fun of experimenting and thrill of writing something that works. That's a feeling of pure magic. :)

Return to “Scripts and Functions”

Who is online

Users browsing this forum: Delta Pythagorean and 48 guests