Main.java

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        System.out.println("Hello World!");
        int[] s = new int[]{5,4,3,2,2,1, 55, 34,12, 4,66,98, 32, 67,15};
        System.out.println(Arrays.toString(s));
        //selectionSort(s);
        //insertionSort(s);
        bubbleSort(s);
        System.out.println(Arrays.toString(s));
    }


    /*
    divide the array in two, one is sorted, and one not. At each step a number is moved from
    the unsorted portion to the sorted portion
    we build the sorted from left to right, from smallest to largest
    to do that:
    - find the minimum unsorted element, put it at the end of the unsorted list
    the only way to to that is to look at the each element, and find the small item
    we start by look at the first element, and set it as the minimum
    the iterate to each element and compare with the minimum. If we found an element
    that is small that the minimum, we update the minimum and change it to the new value
    After that we need to change the position where the minimum was found with the first position
    On the next iteration, we don't start from the first element, because the first element is sorted
    Again, we found the minimum, store it, and change it
    PSEUDO CODE
    for i = 0 to n
        min = i
        for j = i +1  to n
            if array[j] < array[min]
                min = j
        if min != i
            swap array[min] and array[i]
     */

    public static void selectionSort(int[] input){
        for (int i = 0; i < input.length; i++) {
            int min = i;
            for (int j = i + 1; j < input.length; j++) {
                if (input[j] < input[min]){
                    min = j;
                }
            }
            if (min != i){
                int temp = input[min];
                input[min] = input[i];
                input[i] = temp;
            }
        }
    }

    /*
    TODO write description for this algo
    PSEUDO CODE
    for i = 1 to n
        emement = array[i]
        int j = i
        while(j > 0 and array[j -1] > element)
            array[j] = array[j -1]
            j = j -1

        array[j] = element
     */
    public static void insertionSort(int[] input){
        for (int i = 1; i < input.length; i++) {
            int element = input[i];
            int j = i;
            while (j > 0 && input[j -1] > element){
                input[j] = input[j -1];
                j--;
            }
            input[j] = element;
        }
    }

    /*
    the algorithm start and look and compare two element. The first and second, the third and four and so on
    If the left is first is bigger than the second the change place
    the move to the next, second + third, and repeat the process
    PSEUDO CODE
    for i in n
        for j in n
            if array[j] > array[j+1]
                int temp = array[j]
                array[j] = array[j +1]
                array[j +1] = temp

     */
    public static void bubbleSort(int[] input){
        for (int i = 0; i < input.length-1; i++) {
            for (int j = 0; j < input.length-1; j++) {
                if (input[j] > input[j +1]){
                    int temp = input[j];
                    input[j] = input[j +1];
                    input[j +1 ] = temp;
                }
            }
        }
    }

    public static void quicksort(int[] input){

    }

    public static int binarySearch(int[] input){
        return -1;
    }
    public static int linearSearch(int[] input){
        return -1;
    }



}