package teralg;

/**
 * Térinformatikai algoritmusok
 * Rendezések
 * @author Máté Cserép <mcserep@outlook.com>
 */
public class Sorts {
    
    public static void main(String[] args) {
        double[] array = new double[] { 2, 6, 7, 1, 4, 9, 3, 6, 8, 5 };
        System.out.print("Rendezetlen:");
        for(int i = 0; i < array.length; ++i)
            System.out.print(" " + array[i]);
        System.out.println();
        
        array = new double[] { 2, 6, 7, 1, 4, 9, 3, 6, 8, 5 };
        bubbleSort(array);
        System.out.print("Buborék rendezés:");
        for(int i = 0; i < array.length; ++i)
            System.out.print(" " + array[i]);
        System.out.println();
        
        array = new double[] { 2, 6, 7, 1, 4, 9, 3, 6, 8, 5 };
        insertSort(array);
        System.out.print("Beszúró rendezés:");
        for(int i = 0; i < array.length; ++i)
            System.out.print(" " + array[i]);
        System.out.println();
        
        array = new double[] { 2, 6, 7, 1, 4, 9, 3, 6, 8, 5 };
        maxSort(array);
        System.out.print("Maximum kiválasztó rendezés:");
        for(int i = 0; i < array.length; ++i)
            System.out.print(" " + array[i]);
        System.out.println();
        
        array = new double[] { 2, 6, 7, 1, 4, 9, 3, 6, 8, 5 };
        heapSort(array);
        System.out.print("Kupacrendezés:");
        for(int i = 0; i < array.length; ++i)
            System.out.print(" " + array[i]);
        System.out.println();
        
        array = new double[] { 2, 6, 7, 1, 4, 9, 3, 6, 8, 5 };
        quickSort(array);
        System.out.print("Gyorsrendezés:");
        for(int i = 0; i < array.length; ++i)
            System.out.print(" " + array[i]);
        System.out.println();
    }
    
    // Buborék rendezés
    public static void bubbleSort(double[] array) {
        int n = array.length;
        for(int j = n - 1; j > 0; --j)
            for(int i = 0; i < j; ++i)
                if(array[i] > array[i + 1])
                    swap(array, i, i + 1);
    }
    
    // Beszúró rendezés
    public static void insertSort(double[] array) {
        int n = array.length;
        for(int j = 1; j < n; ++j) {
            double w = array[j];
            int i = j - 1;
            while(i >= 0 && array[i] > w) {
                array[i + 1] = array[i];
                --i;
            }
            array[i + 1] = w;
        }
    }
    
    // Maximum kiválasztó rendezés
    public static void maxSort(double[] array) {
        int n = array.length;
        for(int j = n - 1; j > 0; --j) {
            int ind = maxSearch(array, 0, j);
            swap(array, ind, j);
        }
    }
    
    // Segédalgoritmus: maximum kiválasztás
    private static int maxSearch(double[] array, int u, int v) {
        if(array.length == 0 || u < 0 || v >= array.length || u > v)
            return -1;
        
        int ind = u;
        double max = array[u];
        
        for(int i = u + 1; i <= v; ++i)
            if(max < array[i]) {
                ind = i;
                max = array[ind];
            }
        return ind;
    }
    
    // Kupacrendezés
    public static void heapSort(double[] array) {
        int n = array.length;
        makeHeap(array);
        for(int r = n - 1; r > 0; --r) {
            swap(array, 0, r);
            liftDown(array, 0, r - 1);
        }
    }
    
    // Segédalgoritmus: kezdőkupac kialakítása
    private static void makeHeap(double[] array) {
        int n = array.length;
        for(int i = n / 2 - 1; i >= 0; --i)
            liftDown(array, i, n - 1);
    }
    
    // Segédalgoritmus: süllyesztés kupacban
    private static void liftDown(double[] array, int u, int v) {
        boolean l = true;
        while(2 * u <= v && l) {
            int ir;
            if(2 * u + 1 > v || array[2 * u] > array[2 * u + 1])
                ir = 2 * u;
            else
                ir = 2 * u + 1;
            
            if(array[u] < array[ir]) {
                swap(array, u, ir);
                u = ir;
            }
            else
                l = false;
        }
    }
    
    // Gyorsrendezés
    public static void quickSort(double[] array) {
        int n = array.length;
        quickSort(array, 0, n - 1);
    }
    
    // Gyorsrendezés (résztömb)
    private static void quickSort(double[] array, int u, int v) {
        if(u >= v) return;
        
        int k = partition(array, u, v);
        quickSort(array, u, k - 1);
        quickSort(array, k + 1, v);
    }
    
    // Segédalgoritmus: pivot elem helyrevitele (partícionálás)
    private static int partition(double[] array, int u, int v) {
        int i = u + 1;
        int j = v;
        while(i <= j) {
            while(i <= v && array[i] <= array[u])
                ++i;
            while(j >= u + 1 && array[j] >= array[u])
                --j;
            
            if(i < j) {
                swap(array, i , j);
                ++i;
                --j;
            }
        }
        swap(array, u, i - 1);
        return i - 1;
    }
    
    // Segédalgoritmus: elemcsere
    private static void swap(double[] array, int i, int j) {
        double temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}