ISourceCode

Make the frequent cases fast and the rare case correct

Category Archives: Sorting

C# – Heapsort implementation with in-place cascade down

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.- Wikipedia

In my previous article i have explained :

1 . BUILD-MAX-HEAP – runs in linear time, resultant max-heap from an unordered input array.
2 . MAX-HEAPIFY – maintains heap property and runs in O(lg n) time.
3 . MAX-HEAP-INSERT – O(lg n)
4 . HEAP-EXTRACT-MAX – O(lg n)
5 . HEAP-INCREASE-DECREASE-KEY – O(lg n) //not needed for heapsort

The function of heapsort is to insert all the unordered items into a heap using the normal Insert() from the previous article and repeatedly using Remove() will then remove the items in sorted order.

The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).

Heapsort competes with Mergesort as both have worst case O(nlg n) however a well implemented quicksort is better than heapsort since the while loop in the CascadeDown() has more operations which drag the performance as compared to few operations in a quicksort.

To improve heapsort performance a little more

For Time efficiency:
we can replace the Insert() and Remove() function which take O(n) by a single function called CascadeDown(). When we build a heap from an unordered array the elements from N/2 – 1 to n correspond to the nodes on the bottom row i.e those with no children and these are already correct heaps, because they are trees with only one node;we don’t need to apply CascadeDown() to these nodes. We can start at node N/2-1, the rightmost node with children to Cascade. Thus, we need only half as many Cascade operations.

This way we save some time.

For space efficiency:
We can use the same unordered array to store the removed elements. As the max node is removed it can be placed into the last position in the array as the elements would have shifted by one index towards the start of the array.

This improvement could make considerable difference on large data and thus heapsort O(nlg n) run time is better than O(n2) of a quicksort.

Implementation : Note getting rid of Insert() and Remove() functions.


using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace HeapSort
{
    class Node
    {
        private int nodeItem;
        public Node(int value)
        { nodeItem = value; }
        public int getvalue()
        { return nodeItem; }
        public void setvalue(int id)
        { nodeItem = id; }
    }

    class Heap
    {
        private Node[] heapArray;
        private int maxSize;
        private int currentSize;
        public Heap(int maxHeapSize)
        {
            maxSize = maxHeapSize;
            currentSize = 0;
            heapArray = new Node[maxSize];
        }
        public bool IsEmpty()
        { return currentSize == 0; }

        public Node Remove() // Remove maximum value node
        {
            Node root = heapArray[0];
            heapArray[0] = heapArray[--currentSize];
            CascadeDown(0);
            return root;
        }
        public void CascadeDown(int index)
        {
            int largerChild;
            Node top = heapArray[index]; 
            while (index < currentSize / 2) 
            {
                int leftChild = 2 * index + 1;
                int rightChild = leftChild + 1;
                if (rightChild < currentSize && heapArray[leftChild].getvalue() < heapArray[rightChild].getvalue())
                    largerChild = rightChild;
                else
                    largerChild = leftChild;
                if (top.getvalue() >= heapArray[largerChild].getvalue())
                    break;
                heapArray[index] = heapArray[largerChild];
                index = largerChild; 
            } 
            heapArray[index] = top; 
        }
        public void displayArray()
        {
            for(int j=0; j<maxSize; j++)
                Console.Write(heapArray[j].getvalue() + " ");
            Console.WriteLine("");
        }
        public void InsertAt(int index, Node newNode)
        { heapArray[index] = newNode; }
        public void setSize()
        { currentSize = 10; } // we have 10 elements
        public void DisplayHeap()
        {
            Console.WriteLine();
            Console.Write("Elements of the Heap Array are : ");
            for (int m = 0; m < currentSize; m++)
                if (heapArray[m] != null)
                    Console.Write(heapArray[m].getvalue() + " ");
                else
                    Console.Write("-- ");
            Console.WriteLine();
            int emptyLeaf = 32;
            int itemsPerRow = 1;
            int column = 0;
            int j = 0;
            String separator = "...............................";
            Console.WriteLine(separator + separator);
            while (currentSize > 0)
            {
                if (column == 0)
                    for (int k = 0; k < emptyLeaf; k++)
                        Console.Write(' ');
                Console.Write(heapArray[j].getvalue());

                if (++j == currentSize)
                    break;
                if (++column == itemsPerRow)
                {
                    emptyLeaf /= 2;
                    itemsPerRow *= 2;
                    column = 0;
                    Console.WriteLine();
                }
                else
                    for (int k = 0; k < emptyLeaf * 2 - 2; k++)
                        Console.Write(' ');
            }
            Console.WriteLine("\n" + separator + separator);
        }
    }
    class Program
    {
        public static void Main(String[] args)
        {
            int size = 10;
            Heap theHeap = new Heap(size);
            theHeap.InsertAt(0,new Node(40));
            theHeap.InsertAt(1,new Node(70));
            theHeap.InsertAt(2,new Node(20));
            theHeap.InsertAt(3,new Node(60));
            theHeap.InsertAt(4,new Node(50));
            theHeap.InsertAt(5,new Node(100));
            theHeap.InsertAt(6,new Node(82));
            theHeap.InsertAt(7,new Node(35));
            theHeap.InsertAt(8,new Node(90));
            theHeap.InsertAt(9,new Node(10));
            theHeap.setSize();

            for(int j=size/2-1; j>=0; j--) 
                theHeap.CascadeDown(j);
            Console.Write("Heap: ");
            theHeap.displayArray();
            theHeap.DisplayHeap();
            for(int j=size-1; j>=0; j--) 
            { // put the max value at end of array and so on ascending sort
                Node biggestNode = theHeap.Remove();
                theHeap.InsertAt(j, biggestNode);
            }
            Console.Write("Sorted array is : ");
            theHeap.displayArray(); 
            
            Console.ReadLine();
        }
    }
}

OUTPUT:

C# – Tree Sort – In-order traversal of a binary search tree

A tree sort is a sort algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree (in-order) so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file. Several other sorts would have to load the elements to a temporary data structure, whereas in a tree sort the act of loading the input into a data structure is sorting it.

Adding one item to a binary search tree is on average an O(log(n)) process, so adding n items is an O(n log(n)) process, making Tree Sort a so-called, ‘fast sort’. But adding an item to an unbalanced binary tree needs O(n) time in the worst-case, when the tree resembles a linked list (degenerate tree), causing a worst case of O(n2) for this sorting algorithm. The worst case scenario then is triggered by handing a Tree Sort algorithm an already sorted set. This would make the time needed to insert all elements into the binary tree O(n2). The dominant process in the Tree Sort algorithm is the “insertion” into the binary tree, assuming that the time needed for retrieval is O(n).
The worst-case behaviour can be improved upon by using a self-balancing binary search tree. Using such a tree, the algorithm has an O(n log(n)) worst-case performance, thus being degree-optimal. – Wikipedia


using System;
using System.Collections.Generic;
using System.Text;

namespace TreeSort
{
    class Node
    {
        public int item;
        public Node leftChild;
        public Node rightChild;
        public void displayNode()
        {
            Console.Write("[");
            Console.Write(item);
            Console.Write("]");
        }
    }
    class Tree
    {
        public Node root;
        public Tree()
        { root = null; }
        public Node ReturnRoot()
        {
            return root;
        }
        public void Insert(int id)
        {
            Node newNode = new Node();
            newNode.item = id;
            if (root == null)
                root = newNode;
            else
            {
                Node current = root;
                Node parent;
                while (true)
                {
                    parent = current;
                    if (id < current.item)
                    {
                        current = current.leftChild;
                        if (current == null)
                        {
                            parent.leftChild = newNode;
                            return;
                        }
                    }
                    else
                    {
                        current = current.rightChild;
                        if (current == null)
                        {
                            parent.rightChild = newNode;
                            return;
                        }
                    }
                }
            }
        }
        public void Preorder(Node Root)
        {
            if (Root != null)
            {
                Console.Write(Root.item + " ");
                Preorder(Root.leftChild);
                Preorder(Root.rightChild);
            }
        }
        public void Inorder(Node Root)
        {
            if (Root != null)
            {
                Inorder(Root.leftChild);
                Console.Write(Root.item + " ");
                Inorder(Root.rightChild);
            }
        }
        public void Postorder(Node Root)
        {
            if (Root != null)
            {
                Postorder(Root.leftChild);
                Postorder(Root.rightChild);
                Console.Write(Root.item + " ");
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Tree theTree = new Tree();
            theTree.Insert(42);
            theTree.Insert(25);
            theTree.Insert(65);
            theTree.Insert(12);
            theTree.Insert(37);
            theTree.Insert(13);
            theTree.Insert(30);
            theTree.Insert(43);
            theTree.Insert(87);
            theTree.Insert(99);
            theTree.Insert(9);

            Console.WriteLine("Inorder traversal resulting Tree Sort");
            theTree.Inorder(theTree.ReturnRoot());
            Console.WriteLine(" ");

            Console.WriteLine();
            Console.WriteLine("Preorder traversal");
            theTree.Preorder(theTree.ReturnRoot());
            Console.WriteLine(" ");

            Console.WriteLine();
            Console.WriteLine("Postorder traversal");
            theTree.Postorder(theTree.ReturnRoot());
            Console.WriteLine(" ");

            Console.ReadLine();
        }
    }
}

OUTPUT:

Learning Quick Sort the Hungarian way

I saw this video recently. An absolutely brilliant way to learn quick sort.

MergeSort of a Linked List – Java

In this article you can find code for merge sort implementation using linked lists.

Procedure:

MergeSort(head node)

1) If head is NULL or there is only one element in the Linked List then return the node.
2) Else divide the linked list into two halves a and b.
3) Sort recursively the two halves a and b
4) Merge the sorted a and b
5) append the head to the remaining merged list.

You can also check the Formatted code here

class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
	public Node()
	{}
	public void displayNode()
	{
		System.out.println("[" + item + "] ");
	}
}
class LinkedList
{
	private Node first;
	public LinkedList()
	{
		first = null;
	}
	public boolean isEmpty()
	{
		return (first==null);
	}
	public void insert(int val)//inserts at beginning of list
	{
		Node newNode = new Node(val);
		newNode.next = first;
		first = newNode;
	}
	public void append(Node result)
	{
		first = result;
	}
	public void display()
	{
		System.out.println("List items from first to last :");
		Node current = first;
		while(current != null)
		{
			current.displayNode();
			current = current.next;
		}
		System.out.println("");
	}
	public Node extractFirst()
	{
		return first;
	}
	public Node MergeSort(Node headOriginal) 
	{ 
    		if (headOriginal == null || headOriginal.next == null) 
			return headOriginal; 
   		Node a = headOriginal;
		Node b = headOriginal.next; 
    		while ((b != null) && (b.next != null)) 
      		{ 
			headOriginal = headOriginal.next; 
			b = (b.next).next; 
		} 
    		b = headOriginal.next; 
		headOriginal.next = null; 
		return merge(MergeSort(a), MergeSort(b));
		 
	}	 

	public Node merge(Node a, Node b) 
  	{ 
		Node temp = new Node(); 
		Node head = temp;
		Node c = head; 
    		while ((a != null) && (b != null)) 
      		{
			if (a.item <= b.item) 
        		{ 
				c.next = a; 
				c = a; 
				a = a.next; 
			} 
      			else 
        		{ 
				c.next = b; 
				c = b; 
				b = b.next;
			} 
    		}
		c.next = (a == null) ? b : a; 
    		return head.next; 
  	} 
}
class LinkedListBlog
{
	public static void main(String[] args)
	{
		LinkedList object = new LinkedList();
		object.insert(30);
		object.insert(10);
		object.insert(50);
		object.insert(20);
		object.insert(5);
		object.insert(8);
		object.display();
		System.out.println("The list after merge sort O(nlog(n))");
		object.append(object.MergeSort(object.extractFirst()));
		object.display();
	}
}

OUTPUT:

~$ java LinkedListBlog
List items from first to last :
[8]
[5]
[20]
[50]
[10]
[30]

The list after merge sort O(nlog(n))
List items from first to last :
[5]
[8]
[10]
[20]
[30]
[50]

Dutch National Flag Problem – Python

The Dutch national flag problem is a famous computer science related programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors : Red, White and Blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of same color are together and their collective color groups are in the correct order – Wikipedia

The Problem can be reconstructed for a given list consisting 0s, 1s and 2s write a function thats displays 0s first, then 1s and rest of the 2s in last.

0 – Red
1 – White
2 – Blue

def DNF(input,length):
        high = length - 1
        p = 0
        i = 0
        while i <= high:
                if input[i] == 0:
                        input[i],input[p]=input[p],input[i]
                        p = p+1
                        i = i+1
                elif input[i] == 2:
                        input[i],input[high]=input[high],input[i]
                        high = high-1
                else:
                        i = i+1
input = [0,1,2,2,1,0]
print "input: ", input
DNF(input,len(input))
print "output: ", input

OUTPUT:

~/DNF$ python dnf.py
input: [0, 1, 2, 2, 1, 0]
output: [0, 0, 1, 1, 2, 2]

Further reading : Article from Monash

DNF algorithm can be used in Quicksort to partition the elements. DNF algorithm makes O(n) moves and examinations.

Follow

Get every new post delivered to your Inbox.