Introsort implementation by Groovy.

Another groovy homework. this time Introsort.

From Wikipedia :
Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. It is the best of both worlds, with a worst-case O(n log n) runtime and practical performance comparable to quicksort on typical data sets. Since both algorithms it uses are comparison sorts, it too is a comparison sort.

	def introSort(list) {
	// calculate the depth limit.
	def depth = 2 * (int)(Math.log10(list.size()) / Math.log10(2))
	return introLoop(list, depth)
	}
	def introLoop(list, depth) {
	if (list.size() <= 1) {
	return list
	}
	if (depth == 0) {
	return heapSort(list)
	}
	depth--
	//we need to use median of first, last and mid item in the list as pivot.
	def pivot = list[0]
	def partitions = list.groupBy { it <=> list[0] }.withDefault { [] }
	return introLoop(partitions[-1], depth) + partitions[0] + introLoop(partitions[1], depth)
	}
	def heapSort(list) {
	def size = list.size()
	if (size < 2) {
	return list
	}
	/*We need to create a valid binary heap first*/
	heapify(list)
	/*Remove the biggest element in the heap and make sure heap still is valid*/
	(size - 1 .. 1).each {
	/*Remove the biggest element*/
	swap(list, 0, it)
	/*Sift down to make a valid heap*/
	siftDown(list, 0, it - 1)
	}
	return list
	}
	def heapify(list) {
	def size = list.size()
	/*Find the last parent in the heap*/
	def parent = (int)size / 2 - 1
	/*Sift down all parents starting for lowest levels up to root*/
	while (parent != 0) {
	siftDown(list, parent--, size - 1)
	}
	}
	def siftDown(list, start, end) {
	def parent = start
	/*If there is any child for this parent, then check child(s) value to make sure parent is the biggest one*/
	while (parent * 2 + 1 <= end) {
	/*Given p is parent index, left child is in index of p*2 + 1 */
	def leftChild = parent * 2 + 1
	/*Right child is always after left child (if there is any right child)*/
	def rightChild = leftChild + 1
	/*Assume parent is the biggest value*/
	def max = parent
	/*If left child is bigger than parent then left child is a candidate to move up*/
	if (list[leftChild] > list[max]) {
	max = leftChild
	}
	/*If right child is exist its the bigges amoung parent, left and right, then right child needs to move up*/
	if (rightChild <= end && list[rightChild] > list[max]) {
	max = rightChild
	}
	/*If the parent is not the biggest one, swap it with biggest child and continue*/
	if (max != parent) {
	swap(list, parent, max)
	parent = max
	} else {
	break
	}
	}
	}
	def swap(list, i, j) {
	def temp = list[i]
	list[i] = list[j]
	list[j] = temp
	}
	assert [] == introSort([])
	assert [1] == introSort([1])
	assert [1,5] == introSort([5, 1])
	assert [1,2,3,4,5] == introSort([5,1,4,3,2])

view raw gistfile1.groovy hosted with ❤ by GitHub