Sorting Algorithms

Selection Sort

Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.

public class SelectionSort{
      public static void main(String[] args){
          int[] arr = {13, 46, 24, 52, 20, 9};
          sort(arr);

          for(int i = 0; i < arr.length; i++){
               System.out.print(arr[i] + " ");
          }
      }

      public static void sort(int[] arr){
          int n = arr.length;

          for(int i = 0; i < n; i++){
              int mini = i;

              for(int j = i + 1; j < n; j++){
                   if(arr[j] < arr[mini]){
                          mini = j;
                   }
              }

              int temp = arr[mini];
              arr[mini] = arr[i];
              arr[i] = temp;
          }
      }
}

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order.

public class BubbleSort{
    public static void main(String[] args){
        int[] arr = {13, 46, 24, 52, 20, 9};
        sort(arr);

        for(int i = 0; i < arr.length; i++){
             System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr){
        int n = arr.length;

        for(int i = n - 1; i >= 0; i --){
            for(int j = 0; j <= i - 1; j ++){
                 if(arr[j] > arr[j + 1]){
                     int temp = arr[j + 1];
                     arr[j] = arr[j + 1];
                     arr[j + 1] = temp;
                 }
            }
        }
    }
}

Insertion Sort

Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list.

public class InsertionSort{
    public static void main(String[] args){
       int[] arr = {13, 46, 24, 52, 20, 9};
       sort(arr);

       for(int i = 0; i < arr.length; i++){
           System.out.print(arr[i] + " ");
       }
    }

    public static void sort(int[] arr){
        int n = arr.length;

        for(int i = 0; i < n; i ++){
            int j = i;

            while( j > 0 && arr[j] < arr[j - 1]){
                 int temp = arr[j];
                 arr[j] = arr[j - 1];
                 arr[j - 1] = temp;
                 j --;
            }
        }
    }

}

Merge Sort

Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It works by recursively dividing the input array into smaller subarrays and sorting those subarrays then merging them back together to obtain the sorted array.

public class MergeSort{
    public static void main(String[] args){
        int[] arr = {10, 7, 8, 9, 1, 5};
        sort(arr, 0, arr.length - 1);

        for(int i = 0; i < arr.length; i++){
             System.out.print(arr[i] + " ");
        }
    }

    public static void sort(int[] arr, int low, int high){
        if(low >= high){
            return;
        }

        int mid = (low + high) / 2;
        sort(arr, low, mid);
        sort(arr, mid + 1, high);
        merge(arr, low, mid, high);
    }

    public static void merge(int[] arr, int low,  int mid, int high){
        ArrayList<Integer> list =new ArrayList<>();

        int left = low;
        int right = mid + 1;

        while(left <= mid && right <= high){
             if(arr[left] <= arr[right]){
                  temp.add(arr[left]);
                  left ++;
             }else{
                  temp.add(arr[right]);
                  right ++;
             }
        }

        while(left <= mid){
             temp.add(arr[left]);
             left ++;
        }

        while(right <= high){
             temp.add(arr[right]);
             right ++;
        }

        for(int i = 0; i <= temp.size(); i++){
             arr[low + i] = temp.get(i);
        }
    }
}

Quick Sort

QuickSort is a sorting algorithm based on the Divide and Conquer algorithm that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array.

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        sort(arr);

        for (int j : arr) {
            System.out.print(j + " ");
        }
    }

    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = pivot(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int pivot(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low;
        int j = high;

        while (i < j) {
            while (arr[i] <= pivot && i < high) {
                i++;
            }
            while (arr[j] > pivot && j > low) {
                j--;
            }
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp = arr[low];
        arr[low] = arr[j];
        arr[j] = temp;
        return j;
    }
}