Sorting Algorithms

When we want to sort a list of numbers we have to use a sorting algorithm. There are few sorting algorithms in use. Here I have listed the major sorting algorithms in use,

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Quick Sort
  • Heap Sort
  • Merge Sort
  • Linear Time Sorting

Each algorithm have its own pros and cons over each other. Let’s have a closer look at each one of them.

Bubble Sort

Bubble sort do the sorting by swapping two numbers. Always it check the i th number and the i+1 th number and swap them if i th number is greater than i+1 th number. For an example,

list = 9,8,7,6,5

  • First Pass : 9,8,7,6,5

9 and 8, 9 > 8 so need to be swapped

after swap : 8,9,7,6,5

9 and 7, 9 > 7 so need to be swapped

after swap : 8,7,9,6,5

9 and 6, 9 > 6 so need to be swapped

after swap : 8,7,6,9,5

9 and 5, 9 > 5 so need to be swapped

after swap : 8,7,6,5,9

new list = 8,7,6,5,9

So for the second swap it will use this new list and go on. This procedure will take place until there is no swaps to be done. This will take 5 passes to sort the list. Always it will get a passes equal to the number of items in the list. So this sorting is not efficient when there is a list with huge number of items. This could be useful when the list is small and also a few sorting to be done in the list. Now let’s see the java code for this sorting algorithm,

import java.util.Arrays;

public class BubbleSort {

    private static int[] list = {9,8,7,6,5,3,4,3,2,1,9};

    public static void main(String[] args) {
        for(int d=0; d < list.length; d++){
            for(int i=0; i < list.length - 1;i++){
                if(list[i+1] < list[i]){
                    int previous = list[i+1];
                    list[i+1] = list[i];
                    list[i] = previous;
                }
            }
        }
        System.out.println(Arrays.toString(list));
    }
}

Selection Sort

Selection sort do the sorting by swapping two numbers. Always it check the i th number and the j th number and swap them if i th number is greater than j th number. For an example,

list = 9,8,7,6,5

  • First Pass : 9,8,7,6,5

9 and 8, 9 > 8 so need to be swapped

after swap : 8,9,7,6,5

8 and 7, 8 > 7 so need to be swapped

after swap : 7,9,8,6,5

7 and 6, 7 > 6 so need to be swapped

after swap : 6,9,8,7,5

6 and 5, 6 > 5 so need to be swapped

after swap : 5,9,8,7,6

new list = 5,9,8,7,6

And then it will go for the second item and so on. Now let’s see the java code for this sorting algorithm,

package Sorting;

import java.util.Arrays;

public class SelectionSort {

    private static int[] list = {9,8,7,6,5,3,4,3,2,1,9};

    public static void main(String[] args) {
        for(int i = 0; i < list.length; i++){
            for(int j = i+1; j < list.length; j++) {
                if (list[i] > list[j]) {
                    int swap = list[i];
                    list[i] = list[j];
                    list[j] = swap;
                }
            }
        }
        System.out.println(Arrays.toString(list));
    }
}

Insertion Sort

Insertion sort do the sorting by swapping numbers. Always it check the j th number and the j-1 th number and swap them if j th number is less than j-1 th number. For an example,

list = 9,8,7,6,5

  • First Pass : 9,8,7,6,5

9 and 8, 9 > 8 so need to be swapped

after swap : 8,9,7,6,5

7 and 7, 9 > 7 and 8 > 7 so need to be swapped

after swap : 7,8,9,6,5

6 and 6, 9 > 6, 8 > 6 and 7 > 6 so need to be swapped

after swap : 6,7,8,9,5

5 and 5, 9 > 5, 8 > 5, 7 > 5, 6 > 5 so need to be swapped

after swap : 5,6,7,8,9

new list = 5,6,7,8,9

Now let’s see the java code for this sorting algorithm,

package Sorting;

import java.util.Arrays;

public class InsertionSort {

    private static int[] list = {6,9,8,7,6,5,3,4,3,2,1,9,3};

    public static void main(String[] args) {
        for(int i = 0; i < list.length; i++){
            int j = i;
            while(j > 0) {
                if (list[j-1] > list[j]) {
                    int swap = list[j-1];
                    list[j-1] = list[j];
                    list[j] = swap;
                }
                j--;
            }
        }
        System.out.println(Arrays.toString(list));
    }
}

Quick Sort

In the Quick Sort technique we are partitioning the array in to sub arrays and again do it recursively until the array is sorted. So in this case we need to get a pivot, which will be used to partition the array in to sub arrays. Based on the selected pivot, array will be sub partitioned. All the values less than the pivot will be on the left side and all the values greater than the pivot will be on the right side of the partition after the 1st cycle. Then two sub partition which are on the left and right sides of the pivot will be again partitioned using another pivot. This will done recursively until the whole array is partitioned. Choosing a good pivot is the main concern here.

list = 9,8,7,6,5

  • First Pass : 9,8,7,6,5

Lets take the middle element of the array as the pivot, 7

9 and 7, 9 should be on the right side

after swap : 8,6,5,7,9

8 and 7, 8 should be on the right side

after swap : 6,5,7,9,8

6 and 7, 6 should be on the left side

after swap : 6,5,7,9,8

5 and 7, 5 should be on the right side

after swap :6,5,7,9,8

new list = 6,5,7,9,8

And then it will go for the second item and so on. Now let’s see the java code for this sorting algorithm,

package Sorting;

public class QuickSort {

    private int array[];
    private int length;
    private static int[] list = {9,8,7,6,5,3,4,3,2,1,9};

    public static void main(String a[]){
        QuickSort sorter = new QuickSort();
        sorter.sort(list);
        for(int i:list){
            System.out.print(i);
            System.out.print(" ");
        }
    }

    public void sort(int[] inputArr) {
        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    }

    private void quickSort(int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(i, j);
                i++;
                j--;
            }
        }
        if (lowerIndex < j) {
            quickSort(lowerIndex, j);
        }
        if (i < higherIndex) {
            quickSort(i, higherIndex);
        }
    }

    private void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Up to now we have talked about four sorting algorithms. I hope that now you have a clear idea about what we have done. I’ll add other sorting algorithms to another post. Keep in touch to get updates. Thank You!

 

 

Advertisements

One thought on “Sorting Algorithms

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s