[ACE] Simple Sorts

Simple Sorts

There are a lot of simple sorting algorithm, in this blog article, we’ll be looking at bubble sort, selection sort and insertion sort.

Bubble Sort

Basic Idea: There are two loops, the outer loop repeatedly scans through array and the inner loop do comparison with immediate neighbour.
Implementation:

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int array[] = {23,10,12,5,14,14};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void bubbleSort(int array[]){
        for(int i = array.length-1; i > 0; i--){
            for(int j = 0; j < i; j++){
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

Stability:
For this kind of implementation, it is stable.
Complexity:
For an array of size n, in the worst case, the first passage through the inner loop needs (n-1) comparison and (n-1) swaps.
In the (n-1)st passage, it needs 1 comparison and 1 swaps.
Thus, all together: t( (n-1) + (n-2) + … + 1), where t is the time required to do one comparison and one loop
We also spend constant time k declaring i, j, temp and initialising i. Outer loop is executed n-1 times, suppose the cost of checking the loop condition and decrementing i is t1.

Complexity of bubble sort is
t( (n-1) + (n-2) + … + 1) + k + t1(n-1) —> O(n^2)

Using linked list to implement

Node border = null; // first node in the sorted part
while(border != head){
    Node current = head; //start from the first node
    while(current.next  != border){
        if(current.element > current.next.element){
            Element v = current.element;
            current.element = current.next.element;
            current.next.element = v;
        }
        current = current.next;
    }
    border = current; // sorted part increase by one
}

The complexity of it is also O(n^2)

The sum is also a arithmetic progression

Selection Sort

Basic Idea: On each scan, instead of always try to move the “greatest element so far”, we just remember its location and move it at the end of scan
Implementation

import java.util.Arrays;

public class SelectionSort {
    public static void main(String[] args) {
        int array[] = {23,10,12,5,14,14};
        selectionSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void selectionSort(int array[]){
        int pos_greatest;
        int temp;
        for(int i = array.length-1; i>0; i--){
            pos_greatest = 0;
            for(int j = 0; j <= i; j++){
                if(array[j] >= array[pos_greatest]){
                    pos_greatest = j;
                }
                if(i != pos_greatest){
                    temp = array[i];
                    array[i] = array[pos_greatest];
                    array[pos_greatest] = temp;
                }
            }
        }
    }
}

Stability: The stability of selection sort varies from how you implement it. For the implementation above, it is unstable.
Complexity:
Compared to bubble sort:

• Same number of iterations
• Same number of comparisons in the worst case
• Fewer swaps(one for each outer loop = n -1 )
• Also the complexity is O(n^2)

Insertion Sort

Basic idea: Keep the front of the list sorted, and as we move through the back, elements we insert them into the correct place in the front.
Implementation:

import java.util.Arrays;

public class InsertionSort {
    public static void main(String[] args) {
        int array[] = {23,10,12,5,14,14};
        insertionSort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void insertionSort(int array[]){
        for(int i=1; i< array.length; i++){
            int temp = array[i];
            int j = i;
            while(j > 0 && array[j-1] > temp){
                array[j] = array[j-1];
                j--;
            }
            array[j] = temp;
        }
    }
}

Complexity:
In the worst case, has to make n(n-1)/2 comparisons and shifts to the right
Also O(n^2) worst case complexity
Best case: array already sorted, no shifts
Insertion sort on linked lists:
This is a suitable sorting method for doubly linked lists
Stability: In this implementation, it is stable. However, if we change the comparison ofarray[j-1] > temp to array[j-1] >= temp. It will be unstable.