
public class Sort {

	public void Counting(int []array){
		int size=findMax(array);
		int []count = new int[size+1];
		int []output = new int[array.length];

		for (int i = 0; i < array.length; i++) {
			count[array[i]] = count[array[i]]+1;
		}

		for (int i = 1; i < count.length; i++) {
			count[i]  = count[i]+count[i-1];
		}

		for (int i = 0; i < output.length; i++) {
			output[count[array[i]]-1] = array[i];
			count[array[i]]=count[array[i]]-1;
		}

		for (int i = 0; i < output.length; i++) {
			array[i]=output[i];
		}
	}

	public void Comb(int []array){
		int gap = array.length;

		while(gap != 1){
			gap = nextGap(gap);

			for (int i = 0; i < array.length-gap; i++) {
				if(array[i] > array[i+gap]){
					int temp=array[i];
					array[i]=array[i+gap];
					array[i+gap]=temp;
				}
			}
		}
	}

	public void gnomeSort(int arr[]){
		int index = 1;
		int n=arr.length;

		while(index < n){

			if (arr[index] >= arr[index-1])
				++index;

			else
			{
				swap(index, index-1,arr);
				if(index > 1)
					--index;
			}
		}
	}

	void oddEvenSort(int arr[])
	{
	    boolean isSorted = false; // Initially array is unsorted
	    int n=arr.length;
	 
	    while (!isSorted)
	    {
	        isSorted = true;
	 
	        // Perform Bubble sort on odd indexed element
	        for (int i=1; i<=n-2; i=i+2)
	        {
	            if (arr[i] > arr[i+1])
	             {
	                swap(i, i+1,arr);
	                isSorted = false;
	              }
	        }
	 
	        // Perform Bubble sort on even indexed element
	        for (int i=0; i<=n-2; i=i+2)
	        {
	            if (arr[i] > arr[i+1])
	            {
	                swap(i, i+1,arr);
	                isSorted = false;
	            }
	        }
	    }
	 
	    return;
	}



	  public void stoogesort(int arr[], int l, int h){
	        if (l >= h)
	           return;
	
	        if (arr[l]>arr[h])
	        {
	            int t = arr[l];
	            arr[l] = arr[h];
	            arr[h] = t;
	        }
	 
	      
	        if (h-l+1 > 2)
	        {
	            int t = (h-l+1)/3;
	 
	            // Recursively sort first 2/3 elements
	            stoogesort(arr, l, h-t);
	 
	            // Recursively sort last 2/3 elements
	            stoogesort(arr, l+t, h);
	 
	            // Recursively sort first 2/3 elements
	            // again to confirm
	            stoogesort(arr, l, h-t);
	        }

	    }




	public void swap(int i, int j,int []arr) {
		int temp=arr[i];
	    arr[i]=arr[j];
		arr[j]=temp;
	}

	public int nextGap(int x){
		int y = (int) (x / 1.3);

		if(y<1)
			return 1;

		return y;
	}
	public int findMax(int[] array) {
		int max=array[0];

		for (int i = 1; i < array.length; i++) {
			if(array[i] > max)
				max=array[i];
		}
		return max;
	}


}
