FastQuickSort

This code has been declared by its author to be Public Domain code.

FastQuickSort by TaskMaster

2009

If you view this website, http://people.cs.ubc.ca/~harrison/Java/sorting-demo.html , you will see that the FastQuickSort at the bottom is the fastest one.

This is the java code of that sort routine converted to BlitzMax.

SuperStrict

Function FastQuickSortString(array:String[])
	QuickSort(array, 0, array.Length - 1)
	InsertionSort(array, 0, array.Length - 1)

	Function QuickSort(a:String[], l:Int, r:Int)
		If (r - l) > 4
			Local tmp:String
			Local i:Int, j:Int, v:String
			i = (r + l) / 2
			If (a[l] > a[i]) 'swap(a, l, i)
				tmp = a[l]
				a[l] = a[i]
				a[i] = tmp
			End If
			If (a[l] > a[r]) 'swap(a, l, r)
				tmp = a[l]
				a[l] = a[r]
				a[r] = tmp
			End If
			If (a[i] > a[r]) 'swap(a, i, r)
				tmp = a[i]
				a[i] = a[r]
				a[r] = tmp
			End If
			j = r - 1
			'swap(a, i, j)
			tmp = a[i]
			a[i] = a[j]
			a[j] = tmp
			i = l
			v = a[j]
			Repeat
				i:+1
				While a[i] < v ; i:+1; Wend
				j:-1
				While a[j] > v ; j:-1;Wend
				If (j < i) Exit
				'swap (a, i, j)
				tmp = a[i]
				a[i] = a[j]
				a[j] = tmp
			Forever
			'swap(a, i, r - 1)
			tmp = a[i]
			a[i] = a[r - 1]
			a[r - 1] = tmp
			QuickSort(a, l, j)
			QuickSort(a, i + 1, r)
		End If
	End Function

	Function InsertionSort(a:String[], lo0:Int, hi0:Int)
		Local i:Int, j:Int, v:String
		For i = lo0 + 1 To hi0
			v = a[i]
			j = i
			While (j > lo0) And (a[j - 1] > v)
				a[j] = a[j - 1]
				j:-1
			Wend
			a[j] = v
		Next
	End Function

End Function

Comments

TaskMaster

2009

Here is a very basic example using it.

SuperStrict

Import "sort.bmx"

Local s:String[] = ["z", "y", "x", "w", "c", "b", "a"]

FastQuickSortString(s)

For Local i:Int = 0 To 6
	DebugLog s[i]
Next

Brucey

2009

Is this faster than BlitzMax's built-in quicksort for arrays?

plash

2009

Seems to be!

SuperStrict

Framework brl.blitz
Import brl.random

Const array_size:Int = 100000
Const rnd_max:Int = 10000000

Local array:Int[array_size], array2:Int[array_size]
Local index:Int, time:Int
For index = 0 To array_size - 1
	SeedRnd(MilliSecs())
	array[index] = Rand(1, rnd_max)
	array2[index] = Rand(1, rnd_max)
Next

time = MilliSecs()
FastQuickSortInt(array)
PrintDistanceInTime(time)

time = MilliSecs()
array2.Sort()
PrintDistanceInTime(time)


Function FastQuickSortInt(array:Int[])
	QuickSort(array, 0, array.Length - 1)
	InsertionSort(array, 0, array.Length - 1)

	Function QuickSort(a:Int[], l:Int, r:Int)
		If (r - l) > 4
			Local tmp:Int
			Local i:Int, j:Int, v:Int
			i = (r + l) / 2
			If (a[l] > a[i]) 'swap(a, l, i)
				tmp = a[l]
				a[l] = a[i]
				a[i] = tmp
			End If
			If (a[l] > a[r]) 'swap(a, l, r)
				tmp = a[l]
				a[l] = a[r]
				a[r] = tmp
			End If
			If (a[i] > a[r]) 'swap(a, i, r)
				tmp = a[i]
				a[i] = a[r]
				a[r] = tmp
			End If
			j = r - 1
			'swap(a, i, j)
			tmp = a[i]
			a[i] = a[j]
			a[j] = tmp
			i = l
			v = a[j]
			Repeat
				i:+1
				While a[i] < v ; i:+1; Wend
				j:-1
				While a[j] > v ; j:-1;Wend
				If (j < i) Exit
				'swap (a, i, j)
				tmp = a[i]
				a[i] = a[j]
				a[j] = tmp
			Forever
			'swap(a, i, r - 1)
			tmp = a[i]
			a[i] = a[r - 1]
			a[r - 1] = tmp
			QuickSort(a, l, j)
			QuickSort(a, i + 1, r)
		End If
	End Function

	Function InsertionSort(a:Int[], lo0:Int, hi0:Int)
		Local i:Int, j:Int, v:Int
		For i = lo0 + 1 To hi0
			v = a[i]
			j = i
			While (j > lo0) And (a[j - 1] > v)
				a[j] = a[j - 1]
				j:-1
			Wend
			a[j] = v
		Next
	End Function

End Function

Function PrintDistanceInTime(time:Int)
	WriteStdout(String(MilliSecs() - time) + "ms~n")
End Function

EDIT: But not with strings!

SuperStrict

Framework brl.blitz
Import brl.random

Const array_size:Int = 100000
Const rnd_max:Int = 65535

Local array:String[array_size], array2:String[array_size]
Local index:Int, time:Int
For index = 0 To array_size - 1
	SeedRnd(MilliSecs())
	array[index] = Chr(Rand(1, rnd_max))
	array2[index] = Chr(Rand(1, rnd_max))
Next

time = MilliSecs()
FastQuickSortString(array)
PrintDistanceInTime(time)

time = MilliSecs()
array2.Sort()
PrintDistanceInTime(time)

Function FastQuickSortString(array:String[])
	QuickSort(array, 0, array.Length - 1)
	InsertionSort(array, 0, array.Length - 1)

	Function QuickSort(a:String[], l:Int, r:Int)
		If (r - l) > 4
			Local tmp:String
			Local i:Int, j:Int, v:String
			i = (r + l) / 2
			If (a[l] > a[i]) 'swap(a, l, i)
				tmp = a[l]
				a[l] = a[i]
				a[i] = tmp
			End If
			If (a[l] > a[r]) 'swap(a, l, r)
				tmp = a[l]
				a[l] = a[r]
				a[r] = tmp
			End If
			If (a[i] > a[r]) 'swap(a, i, r)
				tmp = a[i]
				a[i] = a[r]
				a[r] = tmp
			End If
			j = r - 1
			'swap(a, i, j)
			tmp = a[i]
			a[i] = a[j]
			a[j] = tmp
			i = l
			v = a[j]
			Repeat
				i:+1
				While a[i] < v ; i:+1; Wend
				j:-1
				While a[j] > v ; j:-1;Wend
				If (j < i) Exit
				'swap (a, i, j)
				tmp = a[i]
				a[i] = a[j]
				a[j] = tmp
			Forever
			'swap(a, i, r - 1)
			tmp = a[i]
			a[i] = a[r - 1]
			a[r - 1] = tmp
			QuickSort(a, l, j)
			QuickSort(a, i + 1, r)
		End If
	End Function

	Function InsertionSort(a:String[], lo0:Int, hi0:Int)
		Local i:Int, j:Int, v:String
		For i = lo0 + 1 To hi0
			v = a[i]
			j = i
			While (j > lo0) And (a[j - 1] > v)
				a[j] = a[j - 1]
				j:-1
			Wend
			a[j] = v
		Next
	End Function

End Function

Function PrintDistanceInTime(time:Int)
	WriteStdout(String(MilliSecs() - time) + "ms~n")
End Function

plash

2009

I bet it would be massively faster using any datatype if it were re-written in C++.

TaskMaster

2009

For me it wasn't about whether it was faster, I can't just use the built-in version, that is why I did it. I need to sort a bunch of arrays, based off of one of them, for my Multi-Column Listbox in ifsoGUI.

If the user wants to sort using column 2, I need to change the other columns so that the rows continue to lineup. So, I needed a sort routine that I could modify to change more than one array as it went. I can just build from this...

Code Archives Forum