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