public class TowersOfHanoi {
    public static void move(int n, int startPole, int endPole) {
        if (n== 0){
            return;
        }
        int intermediatePole = 6 - startPole - endPole;
        move(n-1, startPole, intermediatePole);
        System.out.println("Move " +n + " from " + startPole + " to " +endPole);
        move(n-1, intermediatePole, endPole);
    }
    public static void main(String[] args) {
        move(5, 1, 3);
    }
}

public class HeapSort
{
    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;
    public static void buildheap(int []a){
        n=a.length-1;
        for(int i=n/2;i>=0;i--){
            maxheap(a,i);
        }
    }
    public static void maxheap(int[] a, int i){
        left=2*i;
        right=2*i+1;
        if(left <= n && a[left] > a[i]){
            largest=left;
        }
        else{
            largest=i;
        }
        if(right <= n && a[right] > a[largest]){
            largest=right;
        }
        if(largest!=i){
            exchange(i,largest);
            maxheap(a, largest);
        }
    }
    public static void exchange(int i, int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    public static void sort(int []a0){
        a=a0;
        buildheap(a);
        for(int i=n;i>0;i--){
            exchange(0, i);
            n=n-1;
            maxheap(a, 0);
        }
    }
    public static void main(String[] args) {
        int []a1={4,1,3,2,16,9,10,14,8,7};
        sort(a1);
        for(int i=0;i<a1.length;i++){
            System.out.print(a1[i] + " ");
        }
    }
}

public class Adicom {
    public static void quickSort(int array[], int start, int end) {
        int i = start;
        int k = end;
        
        if (end - start >= 1) {
            int pivot = array[start];
            
            while (k > i) {
                while (array[i] <= pivot && i <= end && k > i)
                i++;
                while (array[k] > pivot && k >= start && k >= i)
                k--;
                if (k > i)
                swap(array, i, k);
            }
            swap(array, start, k);
            
            quickSort(array, start, k - 1);
            quickSort(array, k + 1, end);
        }
    }
    
    public static void swap(int array[], int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
    
    public static void main(String[] args) {
        int[] arr = {
            5,
            66,
            13,
            87,
            19,
            1,
            94,
            10
        };
        quickSort(arr, 0, arr.length - 1); // از صفر تا اخرین اندیس ارایه
        for (int x: arr) {
            System.out.println(x);
        }
    }
}

public void binarySearch(int[] array, int search) {
    int first,last,middle;
    first  = 0;
    last   = n - 1;
    middle = (first + last)/2;
    while( first <= last ) {
        if ( array[middle] < search ) {
            first = middle + 1;
        } else if ( array[middle] == search ) {
            System.out.println(search + " found at location " + (middle + 1) + ".");
            break;
        } else {
            last = middle - 1;
        }
        middle = (first + last)/2;
    }
    if ( first > last ) {
        System.out.println(search + " is not present in the list.n");
    }
}

public boolean isPalindrome(String str) {
	boolean palindrome = false;
         
        str = str.toLowerCase();

        for (int i = 0, j = str.length() - 1; i < str.length(); i++, j-- ) {
            if (i < j) {
                if (str.charAt(i) != str.charAt(j)) {
                    return false;
                }
            }
            else { return true; }
        }   
		
        return palindrome;
}

public static double sqrt(double number) { 
        double c = number;
        double epsilon = 1e-15;
        double t = c;

        while (Math.abs(t - c/t) > epsilon*t) {
            t = (c/t + t) / 2.0;
        }
        
        return t;
    }

public static void InsertionSort( int [ ] num) {
     int j;
     int key;
     int i;  

     for (j = 1; j < num.length; j++) {
           key = num[ j ];
           for(i = j - 1; (i >= 0) && (num[ i ] < key); i--) {
                 num[ i+1 ] = num[ i ];
          }
         num[ i+1 ] = key;
     }
}

static void bubbleSort(String[] array) {
	for(int i = array.length - 1; i > 0; --i) {
		boolean bSwaped = false;
		for(int j = 0; j < i; ++j) {
			if(array[j].compareTo(array[j + 1]) > 0) {
				swap(array, j, j + 1);
				bSwaped = true;
			}
		}
		if(!bSwaped) {
			break;
		}
	}
}

static void swap(String[] array, int pos1, int pos2) {
	String temp = array[pos1];
	array[pos1] = array[pos2];
	array[pos2] = temp;
}

public static void selection_sort (int[] arr) {
      int i , j;
      int max , temp;
      for (i = arr.length-1 ; i> 0 ; i--) {
        max = 0;
        for (j = 1 ; j <= i ; j++)
          if (arr[max] <arr[j])
            max = j;
        temp = arr[i];
        arr[i] = arr[max];
        arr[max] = temp;
      }
    }