SortingAlgorithms

import java.util.Arrays;
import java.util.Scanner;

public class SortingAlgorithms {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] nums = Arrays.stream(scanner.nextLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        int n = nums.length;

        //selectionSort(nums, n);
        //bubbleSort(nums, n);
        //insertionSort(nums, n);
        //mergeSplit(nums,0, n - 1);
        //quickSort(nums, 0, n - 1);

        System.out.println(Arrays.toString(Arrays.stream(nums).toArray()));
    }

    public static void selectionSort(int[] nums, int n) {
        for (int i = n - 1; i >= 1; i--) {
            int maxIndex = i;

            for (int j = 0; j < i; j++) {
                if(nums[j] >= nums[maxIndex]) {
                    maxIndex = j;
                }
            }

            int temp = nums[i];
            nums[i] = nums[maxIndex];
            nums[maxIndex] = temp;
        }
    }

    public static void bubbleSort(int[] nums, int n) {
        for (int i = n - 1; i >= 1; i--) {
            for (int j = 1; j <= i; j++) {
                if(nums[j - 1] > nums[j]) {
                    int temp = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

    public static void insertionSort(int[] nums, int n) {
        for (int i = 1; i < n; i++) {
            int next = nums[i];
            int j;

            for (j = i - 1; j >= 0 && nums[j] > next ; j--) {
                nums[j + 1] = nums[j];
            }

            nums[j + 1] = next;
        }
    }

    public static void mergeSplit(int[] nums, int low, int high) {
        if(low < high) {
            int mid = (low + high) / 2;

            mergeSplit(nums, low, mid);
            mergeSplit(nums, mid + 1, high);

            mergeSort(nums, low, mid, high);
        }
    }

    public static void mergeSort(int[] nums, int low, int mid, int high) {
        int n = high - low + 1;
        int[] temp = new int[n];
        int left = low, right = mid + 1, tempindex = 0;

        while (left <= mid && right <= high) {
            if(nums[left] <= nums[right]) {
                temp[tempindex++] = nums[left++];
            } else {
                temp[tempindex++] = nums[right++];
            }
        }

        while (left <= mid) {
            temp[tempindex++] = nums[left++];
        }
        while (right <= high) {
            temp[tempindex++] = nums[right++];
        }

        for (int i = 0; i < n; i++) {
            nums[low + i] = temp[i];
        }
    }

    public static void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            int partitionIndex = partition(nums, low, high);

            quickSort(nums, low, partitionIndex - 1);
            quickSort(nums, partitionIndex + 1, high);
        }
    }

    private static int partition(int[] nums, int low, int high) {
        int pivot = nums[high];
        int index = (low - 1);

        for (int j = low; j <= high - 1; j++) {
            if(nums[j] < pivot) {
                index++;

                int temp = nums[index];
                nums[index] = nums[j];
                nums[j] = temp;
            }
        }

        index++;

        int temp = nums[index];
        nums[index] = nums[high];
        nums[high] = temp;

        return index;
    }
}