Sorting recaps

1. Selection Sort

public static void selectionSort(int[] arr){
  if(arr == null || arr.length < 2){
    return;
  }
  for(int i=0; i < arr.length-1; i++){
    int minIndex = i;
    for(int j = i+1; j < arr.length-1; j++){
      minIndex = arr[j] < arr[minIndex]? j : minIndex;
    }
    swap(arr, i, minIndex);
  }
}
public static void swap(int[] arr, int i, int j){
  int temp = arr[i];
  arr[i] = arr[minIndex];
  arr[j] = temp;
}

Time Complexity: O(N^2)
Space Complexity: O(1)

2. Bubble Sort

public static void bubbleSort(int[] arr){
  if(arr == null || arr.length < 2){
    return;
  }
  for(int i = arr.length-1; i > 0; i--){
    for(int j=0; j < i; j++){
      if(arr[j] > arr[j+1]){
        swap(arr, j, j+1);
      }
    }
  }
}
public static void swap(int[] arr, int i, int j){
  arr[i] = arr[i] ^ arr[j];
  arr[j] = arr[i] ^ arr[j];
  arr[i] = arr[i] ^ arr[j];
}

Time Complexity: O(N^2)
Space Complexity: O(1)

3. Insertion Sort

public static void insertionSort(int[] arr){
  if(arr == null || arr.length < 2){
    return;
  }
  for(int i = 1; i < arr.length; i++){
    for(int j = i-1; j >= 0 && arr[j] > arr[j+1]; j--){
      swap(arr, j, j+1);
    }
  }
}
public static void swap(int[] arr, int i, int j){
  arr[i] = arr[i] ^ arr[j];
  arr[j] = arr[i] ^ arr[j];
  arr[i] = arr[i] ^ arr[j];
}

Time Complexity: O(N^2)
Space Complexity: O(1)

4. Quick Sort