stooge

import java.io.*;
import java.io.File;
import java.util.Scanner;

public class Main {
    static int counter=0;

    static void stoogesort(int arr[], int l, int h) {

        if (l >= h)
            return;
        counter++;

        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;

            stoogesort(arr, l, h - t);

            stoogesort(arr, l + t, h);

            stoogesort(arr, l, h - t);

        }
    }

    static void stoogesort_r(int arr[], int f, int h) {

        if (f >= h)
            return;
        counter++;
        if (arr[f] < arr[h]) {
            int t = arr[f];
            arr[f] = arr[h];
            arr[h] = t;

        }


        if (h - f + 1 > 2) {
            int t = (h - f + 1) / 3;

            stoogesort_r(arr, f, h - t);

            stoogesort_r(arr, f + t, h);

            stoogesort_r(arr, f, h - t);
        }
    }

    public static int[] readFiles(String file) {
        try {
            File f = new File(file);
            Scanner s = new Scanner(f);
            int ctr = 0;
            while(s.hasNextInt()){
                ctr++;
                s.nextInt();
            };
            int[] arr = new int[ctr];
            Scanner s1 = new Scanner(f);
            for (int i = 0; i < arr.length; i++)
                arr[i] = s1.nextInt();
            return arr;
        } catch (Exception e) {
            return null;
        }
    }

    static void nedostoogesort(int arr[], int l, int h){


        if (l >= h)
            return;
        counter++;
        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;

            nedostoogesort(arr, l, h - t);

            nedostoogesort(arr, l + t, h);

            int f = arr[0];
            arr[0] = arr[999];
            arr[999] = f;

            nedostoogesort(arr, l, h - t);

        }

    }


    public static void main(String args[]) throws IOException {

        int[] arr = readFiles("1000.txt");

        /////////////////////////////////
        System.out.println("STOOGE");
        long timeStart = System.currentTimeMillis();
        stoogesort(arr,0,arr.length-1);
        long timeSpend = System.currentTimeMillis() - timeStart;

        for (int i = 0; i < arr.length; i++) {
            if (i % 10 == 0)
                System.out.println();
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("Miliseconds: " + timeSpend+"\n"+counter);

        System.out.println();System.out.println();
        /////////////////////////////////
        arr = readFiles("1000.txt");
        System.out.println("STOOGE REV");
        timeSpend = 0;
        stoogesort_r(arr,0,arr.length-1);
        timeSpend = System.currentTimeMillis() - timeStart;
        for (int i = 0; i < arr.length; i++) {
            if (i % 10 == 0)
                System.out.println();
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("Miliseconds: " + timeSpend+"\n"+counter);

        System.out.println();System.out.println();

        /////////////////////////////////
        arr = readFiles("1000.txt");
        System.out.println("STOOGE_100");
        timeSpend = 0;


        for(int i=0;i<arr.length;i+=100){
            stoogesort(arr, i, i+99);
        }
        for (int i = 0; i < arr.length; i++) {
            if (i % 10 == 0)
                System.out.println();
            if (i % 100 == 0)
                System.out.println();
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        timeSpend = System.currentTimeMillis() - timeStart;
        System.out.println("Miliseconds: " + timeSpend+"\n"+counter);

        System.out.println();System.out.println();

        /////////////////////////////////
        arr = readFiles("1000.txt");
        System.out.println("NEDO STOOGE");
        timeSpend = 0;
        nedostoogesort(arr,0,arr.length-1);
        timeSpend = System.currentTimeMillis() - timeStart;
        for (int i = 0; i < arr.length; i++) {
            if (i % 10 == 0)
                System.out.println();
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("Miliseconds: " + timeSpend+"\n"+counter);



    }
}