Elementary Sort

These are most basic sort methods with time complexity.

Bubble Sort

Think

• Swap when the two adjacent elements is not in order
• Do a while loop until swap not happened in previous element order check

Solution

public void bubbleSort(int[] arr){
    boolean swap;
    do{
        swap = false;
        for(int i = 0; i < arr.length - 1; i++){
            if(arr[i] > arr[i + 1]){
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swap = true;
            }
        }
    }while(swap);
}

Insertion Sort

Think

• Get the target value from head of array
• Find its suitable position from 0 to its position

Solution

public void insertionSort(int[] arr){
    for(int i = 1; i < arr.length; i++){
        for(int j = 0; j < i; j++) {
            if(arr[j] > arr[i]) {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }
    }
}

Selection Sort

Think

• Get the target value from head of array
• Find the minimum element on the right of target, swap them if minimum less then target

Solution

public void selectionSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){
        int min = i;
        for(int j = i + 1; j < arr.length; j++) {
            if(arr[min] > arr[j])
                min = j;
        }
        if(i!=min) {
            int tmp = arr[min];
            arr[min] = arr[i];
            arr[i] = tmp;
        }
    }
}