Tag Archives: Comparison Sort

Merge Sort Program and Complexity (Big-O)


Mergesort is a comparison sort, same as quicksort and based on divide and conquer algorithm. It divides the original data set into smaller pieces of data set to solve the problem and then finally merge these small data sets.

How Merge Sort Works

Merge sort works in the following way:

  1. Merge sort, take middle index in data set and split into two collections : one collection for items left of middle index and second for right values of middle index.
  2. Repeat step 1 as long as these collections size reach to one item only.
  3. Now merge sort picks the items from smaller collections, sort them and merge to create new collection.
  4. Repeat this sort and merge process until all small colection sort and merge not completed.
  5. Finally will get single collection with sorted result.

Points to Remember

  • Data Structure: Array
  • Best Time Complexity: Ω(n log(n))
  • Average Time Complexity: Θ(n log(n))
  • Worst Time Complexity: O(n log(n))
  • Worst Space Complexity: O(n)

Merge Sort

Merge Sort Program

public class MergeSort {

    public int[] sort(int [] array){
     mergeSort(array, 0, array.length-1);
     return array;

    }

    private void mergeSort(int[] array, int first, int last) {

     // Get mid position to divide problem into smaller size collections
     int mid = (first + last) / 2;

     //If first < last the array must be recursively sorted
     if (first < last) {
      mergeSort(array, first, mid);
      mergeSort(array, mid + 1, last);
     }

     //merge solved collections to get solution to original problem
     int a = 0, f = first, l = mid + 1;
     int[] temp = new int[last - first + 1];

   //decide the swapping of items
     while (f <= mid && l <= last) {
      temp[a++] = array[f] < array[l] ? array[f++] : array[l++];
     }

     while (f <= mid) {
      temp[a++] = array[f++];
     }

     while (l <= last) {
      temp[a++] = array[l++];
     }

     a = 0;
     while (first <= last) {
      array[first++] = temp[a++];
     }
    }

    public static void printArray(int[] array) {
     for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
     }

    }

    public static void main(String[] args) {

     System.out.println("Original array before Merge sort");
     int[] items = {12, 24, 45, 56, 10, 9, 49, 30, 5, 15};
     printArray(items);

     System.out.println("\n\nAfter Mergesort");
     MergeSort merge = new MergeSort();
     merge.sort(items);
     printArray(items);

    }
}

Output


Original array before Merge sort
12 24 45 56 10 9 49 30 5 15 

After Mergesort
5 9 10 12 15 24 30 45 49 56 

 

Bubble Sort/ Sinking Sort Java Program


Bubble Sort also called Sinking Sort is a comparison sort algorithm where smaller or larger “bubble” elements move to top.

Complexity

Complexity of bubble sort is O(n2) in both average and worst case while O(n) in best case when elements are already sorted. Where n is number of elements.

Drawback

It will not be efficient in the case of a reverse-ordered collection or number of elements are high.

import java.util.Scanner;

public class BubbleSort {
	public static void main(String []args) {
	    int n, c, d, swap;
	    //For User Input
	    Scanner in = new Scanner(System.in);

	    System.out.println("Input number of integers to sort");
	    n = in.nextInt();

	    int array[] = new int[n];

	    System.out.println("Enter " + n + " integers");

	    for (c = 0; c < n; c++)
	      array[c] = in.nextInt();

	    for (c = 0; c < ( n - 1 ); c++) {
	      for (d = 0; d < n - c - 1; d++) {
/* In case of descending order use < */ if (array[d] > array[d+1])
	        {
	          swap       = array[d];
	          array[d]   = array[d+1];
	          array[d+1] = swap;
	        }
	      }
	    }
	    System.out.println("Sorted list of numbers");

	    for (c = 0; c < n; c++)
	      System.out.println(array[c]);
	  }
	}

 

More

For more Algorithms and Java Programing Test questions and sample code follow below links