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

Log base 2 of an N-bit integer

Another Groovy training post. This time, three different method to find log base 2 of an N-bit integer.

Note: All algorithms and code credits goes to Bit Twiddling Hacks.

	def log2First(v) {
	def r = 0
	while ((v >>= 1) != 0) r++
	return r
	}
	def log2Second(v) {
	def buffer = java.nio.ByteBuffer.allocate(8)
	double d = buffer.putInt(0x43300000).putInt(v).getDouble(0) - 4503599627370496.0
	return (buffer.putDouble(0, d).getInt(0) >> 20) - 0x3FF
	}
	def log2Third(v) {
	def multiplyDeBruijnBitPosition = [
	0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
	8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
	]
	[1,2,4,8,16].each { v |= v >> it }
	return multiplyDeBruijnBitPosition[ (v * 0x07C4ACDD) >> 27 ]
	}
	(1..100).each {
	assert log2First(it) == log2Second(it)
	assert log2Second(it) == log2Third(it)
	}

view raw gistfile1.groovy hosted with ❤ by GitHub

Note: All algorithms and code credits goes to Bit Twiddling Hacks.

Priority Queue - Groovy Implementation

Here it is :), Another data structure, implemented by me in Groovy as part of my Groovy learning practices. Priority Queue.

	class PriorityQueue {
	/*a list to contains the queue elments in a binary heap format*/
	def list = []
	/*Add new item to the queue*/
	def add(item) {
	list.add(item)
	/*After adding new item, we need to re-validate the heap*/
	siftUp(list, 0, list.size() - 1)
	}
	def pop() {
	if (list.isEmpty()) {
	return null
	}
	def size = list.size()
	/*if there are maximum two items in the queue, we just return the first (root) item in the heap*/
	if (size < 3) {
	return list.remove(0)
	}
	/*Remove the first (root) item and move the last item to first place (root) in the list*/
	def item = list[0]
	list[0] = list.remove(size - 1)
	/*Revalidate the heap*/
	siftDown(list, 0, size - 2)
	return item
	}
	def peek() {
	if (list.isEmpty()) {
	return null
	}
	return list[0]
	}
	def isEmpty() {
	return list.isEmpty()
	}
	def size() {
	return list.size()
	}
	private siftDown(list, start, end) {
	def p = start
	while (p * 2 + 1 <= end) {
	/*Find the left side child*/
	def l = p * 2 + 1
	/*Find the right side child*/
	def r = l + 1
	/*Assume parent is the maximum value.*/
	def max = p
	/*If left child is bigger than parrent then keep it as max value*/
	if (list[max] < list[l]) {
	max = l
	}
	/*If right child exist and its bigger than others (parent and left child) then keep it as max value*/
	if (r <= end && list[max] < list[r]) {
	max = r
	}
	/*If parent is the the biggest value, then swap it with the biggest value*/
	if (p != max) {
	def t = list[p]
	list[p] = list[max]
	list[max] = t
	p = max
	} else {
	break
	}
	}
	}
	private siftUp(list, start, end) {
	def c = end
	while (c > start) {
	/*Find the parent node*/
	def p = (int)((end - 1) / 2)
	/*if the parent is less than child, then swap them*/
	if (list[p] < list[c]) {
	def t = list[p]
	list[p] = list[c]
	list[c] = t
	c = p
	} else {
	break
	}
	}
	}
	}
	/****** Test ******/
	def pq = new PriorityQueue()
	assert true == pq.isEmpty(), 'the queue is empty'
	assert 0 == pq.size(), 'the queue size should be 0'
	assert null == pq.peek(), 'the queue is empty, so there should be nothing to peek'
	assert null == pq.pop(), 'the queue is empty, so there should be nothing to pop'
	pq.add(20)
	assert false == pq.isEmpty(), 'quese is not empty anymore, there is one item (20) in the queue'
	assert 1 == pq.size(), 'queue size must be 1'
	assert 20 == pq.peek(), 'highest value in the queue is the 20'
	assert 20 == pq.pop(), 'removing the highest value which is 20'
	assert true == pq.isEmpty(), 'the queue is empty'
	assert 0 == pq.size(), 'the queue size should be 0'
	pq.add(20)
	pq.add(30)
	pq.add(50)
	assert 50 == pq.peek(), 'the highest value must be 50'
	assert 50 == pq.pop(), 'the highest value must be 50'
	pq.add(10)
	assert 30 == pq.peek(), 'the highest value must be 30'
	assert 30 == pq.pop(), 'the highest value must be 30'

view raw gistfile1.groovy hosted with ❤ by GitHub

Quick Sort, My Groovy Implementation

My Groovy Implementation for QuickSort:

	def quickSort(list) {
	/*Make sure there are at least 2 elements in the list*/
	if (list == null || list.size() < 2) {
	return list
	}
	/*break the list to three different groups
	group 1: with elements less than pivot
	group 2: with elements equal to pivot
	group 3: with elements greater than pivot */
	def partitions = list.groupBy { it <=> list[0] }.withDefault { [] }
	/* sort group 1 and 3 and merge them with group 3 */
	return quickSort(partitions[-1]) + partitions[0] + quickSort(partitions[1])
	}
	assert [] == quickSort([])
	assert [1] == quickSort([1])
	assert [1,5] == quickSort([5, 1])
	assert [1,2,3,4,5] == quickSort([5,1,4,3,2])

view raw gistfile1.groovy hosted with ❤ by GitHub

Heap Sort Implementation in Groovy

My Heap Sort Implementation in Groovy :

	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 [] == heapSort([])
	assert [1] == heapSort([1])
	assert [1,5] == heapSort([5, 1])
	assert [1,2,3,4,5] == heapSort([5,1,4,3,2])

view raw gistfile1.groovy hosted with ❤ by GitHub

My Merge Sort in Groovy

I'm Learning Groovy :) and This is my groovy implementation of Merge Sort.

	def mergeSort(list) {
	def size = list.size()
	if (size < 2) {
	return list
	} else {
	def m = (int)(size / 2)
	def left = list[0..<m]
	def right = list[m..<size]
	return merge(mergeSort(left), mergeSort(right))
	}
	}
	def merge(left, right) {
	def result = []
	def l = 0
	def r = 0
	def lsize = left.size()
	def rsize = right.size()
	while (l < lsize && r < rsize){
	result.add((left[l] <= right[r]) ? left[l++] : right[r++])
	}
	if (l < lsize) {
	result += left[l..-1]
	}
	if (r < rsize) {
	result += right[r..-1]
	}
	return result
	}
	assert [1,2,3,4,5] == mergeSort([1,5,3,2,4])

view raw gistfile1.groovy hosted with ❤ by GitHub