Category: Algorithms & Design

public class SleepSort {

	public static int counter = 0;
	public static int sortedArr[];
	public static int arr[] =  {21,12,14,1,26,34,67,45,0};
	public static int threadCount=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		System.out.println("printing unsorted array");
		printArray(arr);
		
		sortedArr = new int[arr.length];
		
		for(int i=0;i<arr.length;i++){
		
			SleepThread t = new SleepThread(arr[i],i);
			t.start();
			threadCount++;
		}
		
		

	}

	
	public static void printArray(int arr[]){
		for(int k=0;k<arr.length;k++)
			System.out.print(arr[k]+" ");
	
		System.out.println("");
	}
	
}

class SleepThread extends Thread{
	
	int multiple,position;
	
	public SleepThread(int multiple, int position){
		this.multiple=multiple;
		this.position=position;
	}
	
	public void run(){
		try {
			sleep(1000*this.multiple);
			SleepSort.sortedArr[SleepSort.counter++] = SleepSort.arr[this.position];
			
			SleepSort.threadCount--;

			System.out.println("sorted array after value "+multiple+", position ::"+this.position);
			SleepSort.printArray(SleepSort.sortedArr);
			
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
	}
	
}

public class CocktailSort {

	 void printArray(int a[])
	    {
	        int n = a.length;
	        for (int i = 0; i < n; i++)
	            System.out.print(a[i] + " ");
	        System.out.println();
	    }
	 
	    // Driver code
	    public static void main(String[] args)
	    {
	        CocktailSort ob = new CocktailSort();
	        int a[] = { 5, 1, 4, 2, 8, 0, 2 };
	        cocktailSort(a);
	        System.out.println("Sorted array");
	        ob.printArray(a);
	    }
	    
	    public static void cocktailSort(int [] arr){
	    	
	    	int temp = arr[0];
	    	boolean swapped = true;
	    	int start=0, end = arr.length-1;
	    	int itr=0;
	    	while(swapped){
	    		swapped = false;
	    	
	    		
	    	for(int i=start;i<end;i++){
	    		if(arr[i]>arr[i+1]){
	    			temp = arr[i];
	    			arr[i] =arr[i+1];
	    			arr[i+1]=temp;
	    			swapped = true;
	    		}
	    	}
	    	
	    	end--;
	    	
	    	for(int i=end;i>start;i--){
	    		if(arr[i]<arr[i-1]){
	    			temp = arr[i];
	    			arr[i] =arr[i-1];
	    			arr[i-1]=temp;
	    			swapped = true;
	    		}
	    	}
	    	
	    	start++;
	    	
	    	itr++;
	    	}
	    	
	    	System.out.println("itr::"+itr);
	    }
}

public class CycleSort {

	public static void main(String[] args) {
		
		int arr[] = {1,12,9,14,16,80,33,3,4,7,60,2};
		
		System.out.println("printing an input array ::");
		printArray(arr);
		
		cycleSort(arr,arr.length);
		
		System.out.println("printing an sorted array ::");
		printArray(arr);
	}
	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
	
	static void cycleSort(int arr[], int size){
		
		int writes = 0;
		
		for(int cycle_sort=0;cycle_sort<size;cycle_sort++){
			
			int item = arr[cycle_sort];
			System.out.println("item ::"+item+", cycle_sort::"+cycle_sort);
			int pos = cycle_sort;
			for(int i = cycle_sort+1;i<size;i++){
				if(arr[i]<item)
					pos++;
			}
			
			
			if(pos==cycle_sort)
				continue;
			
			while(item==arr[pos])
				pos++;
			
			if(pos!=cycle_sort){
				int temp = item;
				item = arr[pos];
				arr[pos] = temp;
				writes++;
			}
			
			while(pos!=cycle_sort){
				System.out.println("item ::"+item+", cycle_sort::"+cycle_sort);
				pos = cycle_sort;
				
				for(int i=cycle_sort+1;i<size;i++){
					if(arr[i]<item)
						pos++;
				}
				
				
				while(item==arr[pos])
					pos++;
				
				if(item!=arr[pos]){
					int temp = item;
					item = arr[pos];
					arr[pos]=temp;
					writes++;
				}
			
				System.out.println("cycle_sort ::"+cycle_sort+", pos::"+pos);
				printArray(arr);
			}
		
			System.out.println("cycle_sort ::"+cycle_sort);
			printArray(arr);
			
		}
		
		System.out.println("writes ::"+writes);
	}
}

import java.util.Iterator;
import java.util.Vector;

public class StrandSort {

	public static void main(String[] args) {
		 int a[] = { 5, 1, 4, 2, 8, 0, 2 };
        //int a[]={10, 5, 30, 40, 2, 4, 9};
		 System.out.println("printing the array");
		 printArray(a);
		 
		 a= strandSort(a);
      
		 System.out.println("printing the sorted array");
		 printArray(a);
	}
	
	 static void printArray(int a[])
	    {
	        int n = a.length;
	        for (int i = 0; i < n; i++)
	            System.out.print(a[i] + " ");
	        System.out.println();
	    }

	 static int [] strandSort(int arr[]){
		 
		 Vector<Integer> inputList = new Vector<Integer>();
		 for(int i=0;i<arr.length;i++)
			 inputList.add(arr[i]);
		 
		 int z=0;
		 Vector<Integer> subList = new Vector();
		 int outputArr [] = new int[arr.length];
		 int lastItem;
		 int outputIndex=arr.length-1;
		
		/* lastItem = inputList.get(0);
		 subList.add(lastItem);
		*/ 
		 while(outputIndex>0 && z<5){
		 z++; 
		 boolean swapped = true;
		 lastItem = inputList.get(0);
		 subList.add(lastItem);
		
		 
		 for(int i=0;i<inputList.size();i++){
			
			 if(inputList.get(i)>lastItem){
				// lastItem = inputList.get(i);
				 addInSubList(subList,inputList.get(i));
			 }
		 }
		
		 Iterator itr = subList.iterator();
		 while(itr.hasNext()){
			 inputList.remove(itr.next());
		 }
		 
		 int subListSize = subList.size();
		 for(int j=subListSize-1;outputIndex>=0 && j>=0;outputIndex--,j--){
			 outputArr[outputIndex]=subList.get(j);
		 }
		 
		 System.out.println("inputList::"+inputList);
		 System.out.println("subList::"+subList);
		 printArray(outputArr);
		 
		 subList = new Vector();
		 
		 }
		 
		 return outputArr;
	 }
	 
	 static void  addInSubList(Vector subList,int item){
		 int i=0;
		 for(;i<subList.size() && (int)subList.get(i) < item;i++);
		subList.add(i, item); 
		 
	 }
}

import java.util.Vector;

public class PigeonHoleSort {

	public static void main(String[] args) {

		int arr[] = {1,12,9,14,16,80,33,3,4,7,60,2};
		
		System.out.println("printing the array");
		printArray(arr);

		pigenHoleSort(arr,arr.length);
		
		System.out.println("printint the sorted array");
		printArray(arr);
	}

	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
	
	public static void pigenHoleSort(int arr[], int size){
	
		int min,max;
		min = arr[0];
		max = arr[0];
		for(int i=0;i<size;i++){
			if(arr[i]<min)
				min=arr[i];
			if(arr[i]>max)
				max=arr[i];
		}
		
		
		int range = max-min+1;
		
		Vector <Integer> holes [] = new Vector [range];
		
		for(int i=0;i<range;i++)
			holes[i] = new Vector();
		
		for(int i=0;i<size;i++){
			holes[arr[i]-min].add(arr[i]);
		}
		
		int index=0;
		for(int i=0;i<range;i++){
			for(int j=0;j<holes[i].size();j++){
				arr[index]=holes[i].get(j);
				index++;
			}
		}
	}
	
	
}

public class TreeSort {

	public static void main(String[] args) {

		  int arr[] = {5, 4, 7, 2, 11,14,12,1};
		  System.out.println("printing the array");
		  printArray(arr);
		  
		  Tree tree = new Tree();;
		
		  //Build the Tree
		  for(int i = 0; i<arr.length;i++){
		  tree.insert(arr[i]);
		  }
		  
		  System.out.println("built the binary tree");
		  
		  tree.inOrderTraverse(tree.root);
		  
		 
		  
		  
		  
	}

	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

class Tree {
	
	TreeNode root = null;
	
	public void insert(int item){
		
		if(root == null){
			
			root = new TreeNode(item);
			
		} else {
			insertAsChild(item,root);
		}
	}
	
	public void inOrderTraverse(TreeNode node){
		
		if(node.getLeft()!=null)
			inOrderTraverse(node.getLeft());
		if(node!=null)
			System.out.print(node.getKey()+" ");
		if(node.getRight()!=null)
			inOrderTraverse(node.getRight());
		
		
	}
	
	private void insertAsChild(int item, TreeNode node){
		System.out.println("insertAsChild::"+item);
		  if(node.getKey()>item){
				//insert to left child
			  	if(node.getLeft()==null){
			  		node.setLeft(new TreeNode(item));
			  	} else {
			  		insertAsChild(item, node.getLeft());
			  	}
			} else {
				//insert to right child
				if(node.getRight()==null){
					node.setRight(new TreeNode(item));
			  	} else {
			  		insertAsChild(item, node.getRight());
			  	}
			}
	}
}


class TreeNode {

int key;
TreeNode left, right;

public TreeNode(int item){
	
	key = item;
	left = right = null;
}

public int getKey() {
	return key;
}

public void setKey(int key) {
	this.key = key;
}

public TreeNode getLeft() {
	return left;
}

public void setLeft(TreeNode left) {
	this.left = left;
}

public TreeNode getRight() {
	return right;
}

public void setRight(TreeNode right) {
	this.right = right;
}
	
	
}

import java.util.Collections;
import java.util.Comparator;
import java.util.Vector;

public class BucketSort {

	public static void main(String[] args) {
		  float arr[] = { (float)0.897, (float)0.565,
                  (float)0.656, (float)0.1234,
                  (float)0.665, (float)0.3434 };

		  int size = arr.length;
		  System.out.println("printing the array");
		  printArray(arr);

		  bucketSort(arr,size);
		  
		  System.out.println("printing the sorted array");
		  printArray(arr);

	}
	
	static void printArray(float arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
	
	static void bucketSort(float [] arr, int size){
		
		Vector<Float>[] buckets = new Vector[10];
		
		for(int i = 0; i<10 ; i++){
			buckets[i] = new Vector<Float>();
		}
		
		
		//segregating elements into buckets
		for(int i=0;i<size;i++){
			float idx = arr[i]*10;
			System.out.println("((int)idx)-1>>"+(((int)idx))+",　arr[i]"+arr[i]);
			Vector vector = buckets[((int)idx)];
			vector.add(new Float(arr[i]));
		}
		
		
		for(int i=0;i<10;i++){
			
			Collections.sort(buckets[i]);
			System.out.println("buckets[i]"+buckets[i]);
			
		}
		System.out.println("sorted buckets..");
		
		int index=0;
		for(int i=0;i<10;i++){
			for(int j=0;j<buckets[i].size();j++){
				arr[index]=buckets[i].get(j);
				index++;
			}
			
		}
		
	}

}

public class ShellSort {

	public static void main(String[] args) {
		 int arr[] = {12, 34, 54, 2, 3,16,18,1};

		 System.out.println("printing the array..");
		 printArray(arr);
		 
		 int size = arr.length;
		 shellSort(arr,size);
		
		 
		 System.out.println("printing the sorted array..");
		 printArray(arr);
		 
		 
		 
	}

	public static void shellSort(int arr[], int size){
		
		for(int i=size/2;i>0;i/=2){
			
			for(int j=i;j<size;j++){
				int temp = arr[j];
				for(int k=j;k>=i && arr[k-i]>temp;k=k-i){
					arr[k]=arr[k-i];
					arr[k-i] = temp;
					temp = arr[k-i];
				}
			}
		}
	}
	public static void printArray(int arr[]){
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	
}

public class CountSort {

	public static void main(String[] args) {
		int arr[] = {0,9,20,13,15,3,7,8,15};
		
		
		System.out.println("printing an array ::");
		printArray(arr);
		
		System.out.println("Sorting for a range 0 to 20");
		arr = countSort(arr);
		
		System.out.println("Sorted array by count sort");
		printArray(arr);

	}

	static int [] countSort(int [] arr){
		
		int count [] = new int[21];
		int sortOutput [] = new int[arr.length];
		
		//initialize the count array to 0
		for(int i=0;i<count.length;i++)
			count[i]=0;
		
		//calculate count
		for(int i=0;i<arr.length;i++)
			count[arr[i]]++;
		
		//calculate incremental count
		for(int i=1;i<count.length;i++)
			count[i]=count[i-1]+count[i];
		
		//fill output array as per count
		for(int i=arr.length-1;i>=0;i--){
			sortOutput[count[arr[i]]-1] = arr[i];
			--count[arr[i]];
		}
		
		return sortOutput;
		
	}
	
	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

public class HeapSort {

	public static void main(String[] args) {
		int arr[] = {1,12,9,14,16,80,33,3,4,7,60,2};
		
		System.out.println("printing an input array ::");
		printArray(arr);
		
		heapSort(arr);
		
		System.out.println("printing the sorted array::");
		printArray(arr);
	}

	static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
	
	static void heapSort(int arr[]){
		
		int n = arr.length;
		
		for(int i = n/2-1;i>=0;i--){
			heapify(arr,n,i);
		}
		
		System.out.println("printing the heapified array ::");
		printArray(arr);
		
		for(int i =n-1;i>0;i--){
			
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			
			heapify(arr,i,0);
		}
	}
	
	static void heapify(int arr[],int n	, int i){
		int largest =i;
		int left = 2*i+1;
		int right = 2*i+2;
		
		if(left<n && arr[left]>arr[largest])
			largest = left;
		if(right<n && arr[right]>arr[largest])
			largest = right;
		
		if(largest != i){
			int swap = arr[i];
			arr[i] = arr[largest];
			arr[largest] = swap;
			
			heapify(arr,n,largest);
		}
		
	}
}