Sorting algorithm

In this post, it includes the following sorting algorithms. The code is self explained.

• selection sort

• insert sort

• bubble sort

• quick sort

• merge sort

  import java.util.Arrays;

  public class Sort {
  public static void selection_sort(int[] arr) {
  for (int i = 0; i < arr.length - 1; i++) {
  int min_idx = i;
  
  // find the minimum value from right of arr[i] and swap with arr[i]
  for (int j = i + 1; j < arr.length; j++) {
  if (arr[j] < arr[min_idx]) {
  min_idx = j;
  }
  }
  
  // move the min value to the beginning of array
  int temp = arr[i];
  arr[i] = arr[min_idx];
  arr[min_idx] = temp;
  }
  }
  
  public static void insert_sort(int[] arr) {
  // sort from the second element since the first one is already sorted for itself
  for (int i = 1; i < arr.length; i++) {
  int curr = arr[i];
  int j = i - 1;
  
  // move all the greater values(than curr) to one position right
  while (j >= 0 && arr[j] > curr) {
  arr[j + 1] = arr[j];
  j–;
  }
  
  arr[j + 1] = curr;
  }
  }
  
  public static void bubble_sort(int[] arr) {
  // bubble sort for n - 1 rounds
  for (int i = 0; i < arr.length - 1; i++) {
  boolean swapped = false;
  // For each round, bubble up the maximum element to the right
  for (int j = 0; j < arr.length - i - 1; j++) {
  if (arr[j] > arr[j + 1]) {
  int temp = arr[j];
  arr[j] = arr[j + 1];
  arr[j + 1] = temp;
  swapped = true;
  }
  }
  
  if (!swapped)
  break;
  }
  }
  
  public static void quick_sort(int[] arr, int left, int right) {
  if (left < right) {
  int pivot = partition(arr, left, right);
  quick_sort(arr, left, pivot - 1);
  quick_sort(arr, pivot + 1, right);
  }
  }
  
  private static int partition(int[] arr, int left, int right) {
  int pivot = arr[right];
  int curr = left - 1;
  
  for (int i = left; i < right; i++) {
  if (arr[i] <= pivot) {
  curr++;
  int temp = arr[curr];
  arr[curr] = arr[i];
  arr[i] = temp;
  }
  }
  
  curr++;
  int temp = arr[curr];
  arr[curr] = pivot;
  arr[right] = temp;
  return curr;
  }
  
  public static void merge_sort(int[] arr, int left, int right) {
  if (left < right) {
  //int mid = (left + right) / 2;
  int mid = left + (right - left) / 2; // avoid overflow
  merge_sort(arr, left, mid);
  merge_sort(arr, mid + 1, right);
  merge(arr, left, mid, right);
  }
  }
  
  private static void merge(int[] arr, int left, int mid, int right) {
  int l1 = mid - left + 1;
  int l2 = right - mid;
  
  // copy left and right to the temporary array
  int[] a1 = new int[l1];
  int[] a2 = new int[l2];
  
  
  for (int i = 0; i < l1; i++) {
  a1[i] = arr[left + i];
  }
  
  for (int i = 0; i < l2; i++) {
  a2[i] = arr[mid + 1 + i];
  }
  
  // merge back to the original array
  int i = 0, j = 0, k = left;
  while (i < l1 && j < l2) {
  if (a1[i] <= a2[j]) {
  arr[k++] = a1[i++];
  } else {
  arr[k++] = a2[j++];
  }
  }
  
  while (i < l1) {
  arr[k++] = a1[i++];
  }
  while (j < l2) {
  arr[k++] = a2[j++];
  }
  }
  
  public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[] arr = { 11, 25, 12, 22, 64 };
  selection_sort(arr);
  System.out.println(Arrays.toString(arr));
  
  int[] arr1 = { 11, 25, 12, 22, 64 };
  insert_sort(arr1);
  System.out.println(Arrays.toString(arr1));
  
  int[] arr2 = { 11, 25, 12, 22, 64 };
  bubble_sort(arr2);
  System.out.println(Arrays.toString(arr2));
  
  int[] arr3 = { 11, 25, 12, 22, 64 };
  quick_sort(arr3, 0, arr3.length - 1);
  System.out.println(Arrays.toString(arr3));
  
  int[] arr4 = { 11, 25, 12, 22, 64 };
  merge_sort(arr4, 0, arr4.length - 1);
  System.out.println(Arrays.toString(arr4));
  }
  }