Bubble Sort - O(n2)

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Example:

First Pass:

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

// Java program for implementation of Bubble Sort

class BubbleSort{

    void bubbleSort(int arr[]){

        int n = arr.length;

        for (int i = 0; i < n-1; i++)

            for (int j = 0; j < n-i-1; j++)

                if (arr[j] > arr[j+1]){

                    // swap temp and arr[i]

                    int temp = arr[j];

                    arr[j] = arr[j+1];

                    arr[j+1] = temp;

                }

            }

        }

     }

    /* Prints the array */

    void printArray(int arr[]){

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

    // main method to test above

    public static void main(String args[]){

        BubbleSort ob = new BubbleSort();

        int arr[] = {64, 34, 25, 12, 22, 11, 90};

        ob.bubbleSort(arr);

        System.out.println("Sorted array");

        ob.printArray(arr);

    }

}

/* This code is written by Rajat Mishra */

Your task

Research on a Bubble sort algorithm that sorts a data set in descending order

Selection sort - O(n2)

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1. The subarray which is already sorted.

2. Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

Following example explains the above steps:

arr[] = 64 25 12 22 11  

// Find the minimum element in arr[0...4] 

// and place it at beginning 11 25 12 22 64  

// Find the minimum element in arr[1...4] 

// and place it at beginning of arr[1...4] 11 12 25 22 64  

// Find the minimum element in arr[2...4] 

// and place it at beginning of arr[2...4] 11 12 22 25 64  

// Find the minimum element in arr[3...4] 

// and place it at beginning of arr[3...4] 11 12 22 25 64 

public class SelectionSort {

    //time complexity = O(n2)

    public int[] selectionSortAscending(int[] nums) {

        for (int i = 0; i < nums.length - 1; i++) {

            int index = i;

            int smallest = nums[index];

            for (int j = i + 1; j < nums.length; j++) {

                if (nums[j] < smallest) {

                    index = j;

                    smallest = nums[j];

                }

            }

            //you can call the swap method

            if (index != i) {

                nums[index] = nums[i];

                nums[i] = smallest;

            }

        }

        return nums;

    }

    public int[] selectionSortDescending(int[] nums) {

        int i, j, first, temp;

        for (i = nums.length - 1; i > 0; i--) {

            first = 0;

            for (j = 1; j <= i; j++) {

                if (nums[j] < nums[first]) {

                    first = j;

                }

            }

            temp = nums[first];

            nums[first] = nums[i];

            nums[i] = temp;

        }

        return nums;

    }

}

class TestSelectionSort {

    public static void main(String[] args) {

        SelectionSort ss = new SelectionSort();

        int[] num = {5, 1, 7, 3, 2, 9, 4, 7};

        ss.selectionSortAscending(num);

        for (int i = 0; i < num.length; i++) {

            System.out.print(num[i] + " ");

        }

        System.out.println("");

        ss.selectionSortDescending(num);

        for (int i = 0; i < num.length; i++) {

            System.out.print(num[i]+ " ");

        }

    }

}

Your task

Research on a Selection sort algorithm that sorts a data set in descending order

Insertion sort - O(n2)

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Example: 

Another Example: 

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 5 (Size of input array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12

11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13

11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.

5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.

5, 6, 11, 12, 13

public class InsertionSort {

    public int[] insertionSort(int[] arr) {

        int i = 1;

        while (i < arr.length) {

            int x = arr[i];

            int j = i - 1;

            while (j >= 0 && arr[j] > x) {

                arr[j + 1] = arr[j];

                j = j - 1;

            }

            arr[j + 1] = x;

            i = i + 1;

        }

        return arr;

    }

    //recursive variant

    public int[] insertionSort(int[] arr, int n){

        if(n > 0){

            insertionSort(arr, n-1);

            int x = arr[n];

            int j = n - 1;

            while(j >=0 && arr[j] > x){

                arr[j+1] = arr[j];

                j = j-1;

            }

            arr[j+1] = x;

        }

        return arr;

    }

}

class TestClass {

    public static void main(String[] args) {

        InsertionSort is = new InsertionSort();

        int[] num1 = {2, 3, 4, 2, 1, 5, 6, 3};

        is.insertionSort(num1);

        for (int i = 0; i < num1.length; i++) {

            System.out.println(num1[i]);

        }

        int[] num2 = {10, 100, 20, 30, 40, 21, 30, 10};

        is.insertionSort(num2, 7);

        for (int i = 0; i < num2.length; i++) {

            System.out.println(num2[i]);

        }   

    }

}

Your task

Research on a Insertion sort algorithm that sorts a data set in descending order

Merge sort - O(n log n)

Like QuickSort, Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves. 

The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. 

See following C implementation for details.

MergeSort(arr[], l,  r) 

If r > l      

1. Find the middle point to divide the array into two halves:                

     middle m = (l+r)/2      

2. Call mergeSort for first half:                 

     Call mergeSort(arr, l, m)      

3. Call mergeSort for second half:              

     Call mergeSort(arr, m+1, r)      

4. Merge the two halves sorted in step 2 and 3:              

     Call merge(arr, l, m, r)

The following diagram from wikipedia shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}. 

If we take a closer look at the diagram, we can see that the array is recursively divided in two halves till the size becomes 

1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.

public class MergeSort {

    // Merges two subarrays of arr[].

    // First subarray is arr[l..m]

    // Second subarray is arr[m+1..r]

    void merge(int arr[], int l, int m, int r) {

        // Find sizes of two subarrays to be merged

        int n1 = m - l + 1;

        int n2 = r - m;

        /* Create temp arrays */

        int L[] = new int[n1];

        int R[] = new int[n2];

        /*Copy data to temp arrays*/

        for (int i = 0; i < n1; ++i) {

            L[i] = arr[l + i];

        }

        for (int j = 0; j < n2; ++j) {

            R[j] = arr[m + 1 + j];

        }

        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays

        int i = 0, j = 0;

        // Initial index of merged subarry array

        int k = l;

        while (i < n1 && j < n2) {

            if (L[i] <= R[j]) {

                arr[k] = L[i];

                i++;

            } else {

                arr[k] = R[j];

                j++;

            }

            k++;

        }

        /* Copy remaining elements of L[] if any */

        while (i < n1) {

            arr[k] = L[i];

            i++;

            k++;

        }

        /* Copy remaining elements of R[] if any */

        while (j < n2) {

            arr[k] = R[j];

            j++;

            k++;

        }

    }

    // Main function that sorts arr[l..r] using

    // merge()

    void sort(int arr[], int l, int r) {

        if (l < r) {

            // Find the middle point

            int m = (l + r) / 2;

            // Sort first and second halves

            sort(arr, l, m);

            sort(arr, m + 1, r);

            // Merge the sorted halves

            merge(arr, l, m, r);

        }

    }

}

class TestClass2 {

    public static void main(String[] args) {

        MergeSort ms = new MergeSort();

        int[] num = {6, 1, 5, 3, 7, 9, 2, 3, 4};

        ms.sort(num, 0, 8);

        for (int i = 0; i < num.length; i++) {

            System.out.println(num[i]);

        }

    }

}

Your task

Research on a Merge sort algorithm that sorts a data set in descending order

REFERENCES:

1. “Sorting Algorithm.” Wikipedia, Wikimedia Foundation, 9 May 2018, en.wikipedia.org/wiki/Sorting_algorithm.

2. “Sorting Algorithms.” GeeksforGeeks, www.geeksforgeeks.org/sorting-algorithms/.