Category Archives: sorting

Java 8: Arrays Parallel Processing


Java 8 added lots of new methods to allow parallel processing for arrays. The most frequently used one is parallelSort() which may speed up the arrays sorting on multicore machines.

Java 8 new methods for Arrays

  • Arrays.parallelSetAll(): Set all elements of the specified array, in parallel, using the provided generator function to compute each element.
  • Arrays.parallelSort(): Sorts the specified array into ascending numerical order.
  • Arrays.parallelPrefix(): Cumulates, in parallel, each element of the given array in place, using the supplied function.

Example: Arrays Parallel Processing

In this example uses method parallelSetAll() to fill up arrays with 25000 random values.
After that, the apply parallelSort() on these arrays values. Here you can see the output of the initial 10 values before and after sorting.

public class ParallelArrays {

	public static void main(String[] args) {
		    long[] arrayOfLong = new long [ 25000 ];
            //Fill long array with random numbers parallelly
	        Arrays.parallelSetAll( arrayOfLong,index -> ThreadLocalRandom.current().nextInt( 1000000 ) );
			//Print initial 10 values of array
            System.out.println("Before Sorting:Print initial 10 values of array");
	        Arrays.stream( arrayOfLong ).limit( 10 ).forEach(i -> System.out.print( i + " " ) );
	        System.out.println();
			//Parallel Sort Array Values
	        Arrays.parallelSort( arrayOfLong );
			//Print initial 10 values of array
			System.out.println("After Sorting:Print initial 10 values of array");
	        Arrays.stream( arrayOfLong ).limit( 10 ).forEach(i -> System.out.print( i + " " ) );
	        System.out.println();
	}

}

Output


Before Sorting:Print initial 10 values of array
164965 546280 269106 800751 338598 862392 358814 206345 611726 788465 
After Sorting: Print initial 10 values of array
4 13 87 93 94 145 203 281 319 397

References

Advertisements

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 

 

Quicksort Program and Complexity (Big-O)


Quicksort is a comparison sort based on divide and conquer algorithm. Quick sort is more fast in comparison to Merge Sort ot Heap Sort. It’s not required additional space for sorting.

How Quick Sort Works

The idea to implement Quicksort is first divides a large array into two smaller sub-arrays as the low elements and the high elements then recursively sort the sub-arrays.

The above process follow below steps:

  1. If array having 0 or 1 item then it’s already sorted.
  2. Pick an item from the array that is called as pivot.
  3. Partition this array as items less than pivot will come before pivot while items greater than pivot will come after it (equals values can either way). Now Pivot get it’s exact position.
  4. Now repeat step 2 and 3 for both left and right side values of Pivot and continue same as long as no left or right items remaining.
  5. Finally, as result of array will sorted items.

Quicksort

Points to remember

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

Quick Sort Program

public class QuickSort {

	public void quicksort(int[] array) {
		quicksort(array, 0, array.length - 1);
	}

	private void quicksort(int[] array, int first, int last) {
		if (first < last) {
			int pivot = partition(array, first, last);

			// Recursive call
			quicksort(array, first, pivot - 1);
			quicksort(array, pivot + 1, last);
		}
	}

	private int partition(int[] input, int first, int last) {

		//choose pivot as last item
		int pivot = last;

		swap(input, pivot, last);
		for (int i = first; i < last; i++) {
			if (input[i] <= input[last]) {
				swap(input, i, first);
				first++;
			}
		}

		swap(input, first, last);
		return first;
	}

	private void swap(int[] input, int a, int b) {
		int temp = input[a];
		input[a] = input[b];
		input[b] = temp;
	}

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

	public static void main(String[] args) {

		int[] items = {12, 24, 45, 56, 10, 9, 49, 30, 5, 15};
		System.out.println("Original Array Before Quick Sort");
		printArray(items);

		System.out.println("\n\nAfter QuickSort");

		QuickSort sort = new QuickSort();
		sort.quicksort(items);
		printArray(items);

	}
}

Output


Original Array Before Quick Sort
12 24 45 56 10 9 49 30 5 15 

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

Radix Sort Program and Complexity (Big-O)


Radixsort sorts numeric data (integers or float) by considering a string of numbers where digit by digit sort starting from least significant digit position to most significant digit position. To sort these specific positions data counting sort as a subroutine.

Counting sort is a linear time sorting algorithm that sort in O(n+k) but that will worst in case of items range from 1 to n2 that sort in O(n^2). Where K is items range from 1 to k.

Note :

  • LSD : Least Significant Digit
  • MSD : Most Significant Digit

Steps to Radixsort

  1. Check for the max length item in input values and check for length.
  2. For each digit position i where i varies from LSD to the MSD.
  3. Perform counting sort based on considering key as i position digits.
  4. Finally, you will get a sorting array for input items.

Points to Remember

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

Radix sort Example


Input Numbers:

        170, 45, 75, 90, 02, 802, 2, 66 
Step 1 : Find the max item length in input i.e 3.

Step 2: Repeat the below process for position i from LSD to MSD
        Perform count sort on numbers, after considering digits as key on 
        particular i.
        
        0 Position :
        170, 90, 02, 802, 2, 45, 75, 66
        
        1 Position :
        02, 2, 802, 45, 66, 170, 75, 90
        
        2 Position :
        02, 2, 45, 66, 75, 90, 170, 802 
        
Step 3: Final Redix Sort result

        02, 2, 45, 66, 75, 90, 170, 802    
 

Radix Sort Program

public class RadixSort {

	public static void main(String[] args) {

		// Assuming our key values are with in range 0 - 9
		int[] items = { 170, 45, 75, 90, 02, 802, 2, 66 };
		System.out.println("Before Radix Sorting :");
		printArray(items);

		// Perform counting sort sort
		radixsort(items);

		System.out.println("After Radix Sorting :");
		printArray(items);
	}

	// radix sort method to sort values of array items
	static void radixsort(int items[]) {
		// find max number to know max number of digits
		int m = getMax(items);

		// Perform counting sort for every digit. Note that instead
		// of passing digit number, exp is passed. exp is 10^i
		// where i is current digit number
		for (int exp = 1; m / exp > 0; exp *= 10)
			countingsort(items, exp);
	}

	// A utility method to get maximum value in items[]
	static int getMax(int items[]) {
		int max = items[0];
		for (int i = 1; i  max)
				max = items[i];
		return max;
	}

	private static void countingsort(int[] items, int exp) {
		// create array of size 10 that will have index value as 0-9
		// it will create array of size 10 and initialize
		// each element with value 0
		int[] counts = new int[10];
		int[] output = new int[items.length];
		for (int key : items) {
			// for each match key, index position element
			// increase count as 1
			counts[(key / exp) % 10] += 1;
		}

		// Change count[i] so that count[i] now contains
		// actual position of this digit in output[]
		for (int i = 1; i = 0; i--) {
			output[counts[(items[i] / exp) % 10] - 1] = items[i];
			counts[(items[i] / exp) % 10] -= 1;
		}

		// Copy the output array to items[] to return
		// sorted array according to index position
		for (int i = 0; i < items.length; i++)
			items[i] = output[i];

	}

	static void printArray(int items[]) {
		for (int item : items) {
			System.out.print(item + " ");
		}
		System.out.println();
	}

}

Output


Before Radix Sorting :
170 45 75 90 2 802 2 66 
After Radix Sorting :
2 2 45 66 75 90 170 802 

Bucket Sort Program and Complexity (Big-O)


Bucket sort/Bin sort is a distribution sort as a generalization of pigeonhole sort. It’s useful when input values are uniformly distributed over a range then divide this range in some interval and put values in a bucket which lies within these intervals.Finally, sort values in each bucket by any sorting technique and then print by sequence by iterating intervals.

Bucket Sort Steps

  1. Set up an array of empty “buckets” initially.
  2. Go over the original array, putting each item in its interval bucket.
  3. Sort all non-empty bucket.
  4. Visit each interval buckets in order and put all elements back into the original array.

Points to Remember

  • Data structure: Array
  • Best Time Complexity: Ω(n+k)
  • Average Time Complexity: Θ(n+k)
  • Worst Time Complexity: O(n^2)
  • Worst Space Complexity: O(n)

Bucket Sort Java Program

public class BucketSort {

		public static void main(String[] args) {

			//Assuming our key values are with in range 0 - 1
			double[] items = { 0.23, 0.67, 0.32, 0.25, 0.88, 0.45, 0.86, 0.16, 0.59, 0.38, 0.19, 0.43,  0.02 };
	        System.out.println("Before Bucket Sorting :");
	        printArray(items);

	        //Perform counting sort sort
	        bucketsort(items);

	        System.out.println("After Bucket Sorting :");
	        printArray(items);
		}

		private static void bucketsort(double []items)
		{
			//create array of size 10 that will have index value as 0-9
			//Initially will keep empty bucket
			java.util.List []numbers=new ArrayList[10];
			for(double key:items)
			{
				//To equally distribute input values , multiply key with array size.
				int index=(int)(key*numbers.length);
				//index position is not having any value yet create blank bucket
				if(numbers[index]==null)
				{
					numbers[index]=new ArrayList();

				}
				//add items based on index position
				numbers[index].add(key);
			}

			//Now sort values in each bucket by any sorting method
			// and add in initial array
			int i=0;
			for(int index=0; index<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;">&#65279;</span>&lt;numbers.length; index++)
			{

				if(numbers[index]!=null)
				{
					//Here i am using Collections utility method but
					//you use any sorting algorithm.
					Collections.sort(numbers[index]);
					//iterate each value in sorted bucket
					//add it in original array position
					for(double  item:numbers[index])
					{
						items[i++]=item;
					}
				}

			}
		}

		static void printArray(double items[])
		{
	        for (double item:items)
	        {
	            System.out.print(item + &quot; &quot;);
	        }
	        System.out.println();
		}

}

Output


Before Bucket Sorting :
0.23 0.67 0.32 0.25 0.88 0.45 0.86 0.16 0.59 0.38 0.19 0.43 0.02 
After Bucket Sorting :
0.02 0.16 0.19 0.23 0.25 0.32 0.38 0.43 0.45 0.59 0.67 0.86 0.88 

Shell Sort Program and Complexity (Big-O)


Shellsort is an in-place comparison sort, also known as Shell sort or Shell’s method. It’s mainly variation of insertion sort or bubble sort . There was one drawback with insertion sort, we move elements only one position ahead but when an elements are too far then lots of movements are involved. To reduce these movements Shell sort come with idea of allow exchange of far items.

Shell Sort Steps

  • Pick some far location h and make sorted array for values index[h…n-1] by insertion sort.
  • Reduce the value of h until it becomes 1.
  • Repeat the steps 1 and 2
  • Finally you will get sorted items list.

Points to Remember

  • Data structure: Array
  • Worst-case performance: O(n2) (worst known worst case gap sequence) O(n log2n) (best known worst case gap sequence)
  • Best-case performance: O(n log n) (most gap sequences) O(n log2n)  (best known worst case gap sequence)
  • Average performance: depends on gap sequence
  • Worst-case space complexity : О(n) total, O(1) auxiliary

Sell Sort Java Program

public class ShellSort {
 public static void main(String[] args)
 {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Shell Sorting :");
        printArray(items);

        //Perform shell sort
        shellsort(items);

        System.out.println("After Shell Sorting :");
        printArray(items);
 }
 static void shellsort(int items[])
 {
     int n = items.length; 

     // Start with a big gap, then reduce the gap until 1
     for (int gap = n/2; gap > 0; gap /= 2)
     {
    	 //perform insertion sort for these gap size
    	 //The first gap elements a[0..gap-1] are already
    	 //in gapped order keep adding one more element
    	 //until the entire array is gap sorted 

         for (int i = gap; i = gap && items[j - gap] > temp; j -= gap)
            	 items[j] = items[j - gap]; 

             // put temp in its correct  location
             items[j] = temp;
         }
     } 

 } 

 static void printArray(int items[])
	{
     for (int item:items)
     {
         System.out.print(item + " ");
     }
     System.out.println();
	}
}

Output

 


Before Shell Sorting :
2 6 3 8 4 1 5 0 
After Shell Sorting :
0 1 2 3 4 5 6 8 

Counting Sort program & Complexity (Big-O)


Counting sort also called an integer sorting algorithm. Counting sort algorithm is based on keys in a specific range. It counts the number of items for distinct key value, use these keys to determine position or indexing on the array and store respective counts for each key. Finally, sort values based on keys and make sequences the repetition of key based on counts.

Counting sort is suitable where variation in keys are is not significantly greater than the number of items. Its running time is linear as numbers of items(n)+difference between max and min key values.

Points to Remember

  • Data structure: Array
  • Worst-case performance: O(n+k), where k is the range of the non-negative key values.
  • Worst-case space complexity: O(n+k)

Advantage

  • Counting sort is a stable sort, where if two items have the same key, they should have the same relative position in the sorted output as they did in the input.

Disadvantage

  • Data range should be predefined, if not then addition loops required to get min and max value to get range.
  • Not much variation on key values otherwise will occupy unnecessary space in the array.

Steps for Counting Sort


For easily understand, consider the data in the range 0 to 9 for below example:
Input data: 2, 6, 3, 2, 8, 4, 8, 1, 5, 3, 1, 4, 0
1) Create an array of size 10 (index values 0-9) and store the count of each 
   unique item.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     1  2  2  2  2  1  1  0  2  0

2) Execute loop for each index for array and check counts are more than zero. 
   repeat the index/key value until count reach to zero. Store these values in 
   previous array and increase index position by one. Now sorted array
 
  Index:     0  1  2  3  4  5  6  7  8  9 10   11 12
  Count:     0  1  1  2  2  3  3  4  4  5  6   8  8

Counting Sort Program

public class CountingSort {

	public static void main(String[] args) {

		//Assuming our key values are with in range 0 - 9
		int[] items = { 2, 6, 3, 2, 8, 4, 8, 1, 5, 3, 1, 4, 0};
        System.out.println("Before Counting Sorting :");
        printArray(items);

        //Perform counting sort sort
        countingsort(items);

        System.out.println("After Count Sorting :");
        printArray(items);
	}

	private static void countingsort(int []items)
	{
		//create array of size 10 that will have index value as 0-9
		//it will create array of size 10 and initialize
		//each element with value 0
		int []numbers=new int[10];
		for(int key:items)
		{
			//for each match key, index position element
			//increase count as 1
			numbers[key]+=1;
		}

		//Now sort values based on keys and repeat
		//this key value as per count
		int i=0;
		for(int key=0; key0)
			{
				for(int count=1;count<=numbers[key];count++)
				{
					items[i++]=key;
				}
			}

		}
	}

	static void printArray(int items[])
	{
        for (int item:items)
        {
            System.out.print(item + " ");
        }
        System.out.println();
	}

}

Output


Before Counting Sorting :
2 6 3 2 8 4 8 1 5 3 1 4 0 
After Count Sorting :
0 1 1 2 2 3 3 4 4 5 6 8 8 

Heapsort Program and Complexity (Big-O)


Heapsort is a sorting algorithm based on a Binary Heap data structure. It’s a comparison-based sorting similar to Selection Sort where first find maximum item and place that maximum item at the end. Repeat the same steps for remaining items until all items sorted.

Points to Remember

  • Data structure: Array
  • Worst-case performance: O(n\log n)
  • Best-case performance : O(n\log n) (distinct keys) O(n) (equal keys)
  • Average performance: O(n\log n)
  • Worst-case space complexity: O(n) total O(1) auxiliary

See Also: Data Structure and Algorithms Complexity (Big-O)

Advantage

  • Heapsort is a more favorable in worst-case O(n log n) runtime.

Disadvantage

  • Heapsort slower in practice on most machines than a well-implemented quicksort.
  • Heapsort is not a stable sort but in-place algorithm.

Binary Heap Data Structure

Binary Heap is a type of Complete Binary Tree where items stored such a way like a parent node value is greater than the values of its child nodes. That is also called as Max heap. it can be represented in the form of a binary tree or array.

Binary Tree Representation in Array

To represent binary tree structure in the array, consider each array index as a node, where these index of nodes for a parent, left the child and right child follow these expression. In Binary tree for zero-based array ,the root node is stored at index 0; if i is the index of the current node, then

  • parent(i) = floor((i-1) / 2) , where floor map a real number to the smallest leading integer.
  • LeftChild(i) = 2*i + 1
  • RightChild(i) = 2*i + 2

Steps for Heap Sort

  1. Call the heapify() function on the array to make as Max Heap Binary Tree array where Maximum item on the first position.
  2. Swap the first item of the array with the final item. Consider the size of the array by decrease one. Call heapify() on the root of a binary tree.
  3. Repeat the above steps until the size of the unsorted heap is 1.

Note: The heapify() operation is run once, and is O(n) in performance. The swapping() function is O(log n) and is called n times. Therefore, the total performance of this heap sort algorithm is O(n + n log n) = O(n log n).

<h2>Heapsort Java Program</h2>
public class HeapSort {

 public static void main(String []args)
 {
	int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Heap Sorting :");
        printArray(items);

        //Perform heap sort
        heapsort(items);

        System.out.println("After Heap Sorting :");
        printArray(items);
 }

 public static void heapsort(int items[])
 {
     int itemCount = items.length; 

     // Build heap (rearrange array)
     for (int i = itemCount / 2 - 1; i &gt;= 0; i--)
         heapify(items, itemCount, i); 

     // One by one extract an element from heap
     for (int i=itemCount-1; i&gt;=0; i--)
     {
         // Move max root item to end
         int temp = items[0];
         items[0] = items[i];
         items[i] = temp; 

         // call max heapify on the reduced heap
         heapify(items, i, 0);
     }
 } 

 /**
  * Call the heapify() function on the array of decrease size to make as Max Heap Binary
  * Tree array where Maximum item on first position or root.
  */
 static void heapify(int items[], int itemCount, int i)
 {
     int largest = i; // Initialize largest as root
     int l = 2*i + 1; // left = 2*i + 1
     int r = 2*i + 2; // right = 2*i + 2 

     // If left child is larger than root
     if (l  items[largest])
         largest = l; 

     // If right child is larger than largest so far
     if (r  items[largest])
         largest = r; 

     // If largest is not root
     if (largest != i)
     {
         int swap = items[i];
         items[i] = items[largest];
         items[largest] = swap; 

         // Recursively heapify the affected sub tree
         heapify(items, itemCount, largest);
     }
 } 

 static void printArray(int items[])
	{
     for (int item:items)
     {
         System.out.print(item + " ");
     }
     System.out.println();
	}
}

Output


Before Heap Sorting :
2 6 3 8 4 1 5 0 
After Heap Sorting :
0 1 2 3 4 5 6 8 

Data Structure and Algorithms Complexity (Big-O)


Big-O notation is a mathematical representation used to describe the complexity of a data structure and algorithm. There are two types of Complexity :

  1. Time Complexity: Its measure based on steps need to follow for an algorithm.
  2. Space Complexity: It measures the space required to perform an algorithm and data structure.

Data Structure and Algorithm Decision

Data structure and algorithm decisions are based on the complexity of size and operations need to perform on data. Some algorithms perform better on a small set of data while others perform better for big data sets for certain operations.

These days Space Complexity is not big concerns but the main performance of an algorithm measures based on time complexity. We can make the decision to choose an algorithm based on below performance criteria with respect to Complexity.

Complexity Performance
O(1) Excellent
O(log(n)) Good
O(n) Fair
O(n log(n)) Bad
O(n^2) Horrible
O(2^n) Horrible
O(n!) Horrible

This post almost covers data structure and algorithms space and time Big-O complexities. Here you can also see time complexities for types of operations like access, search, insertion, and deletion.

See also: 

Data Structure Space and Time Complexity

Data Structure Time Complexity Space Complexity
Average Worst
Access Search Insertion Deletion
Array Θ(1) Θ(n) Θ(n) Θ(n) O(n)
Stack Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Queue Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Singly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Doubly-Linked List Θ(n) Θ(n) Θ(1) Θ(1) O(n)
Skip List Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n log(n))
Hash Table N/A Θ(1) Θ(1) Θ(1) O(n)
Binary Search Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Cartesian Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
B-Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Red-Black Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Splay Tree N/A Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
AVL Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
KD Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)

Sorting Algorithms Space and Time Complexity

Algorithm Time Complexity Space Complexity
Best Average Worst Worst
Quick Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n))
Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Tim Sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)
Heap Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1)
Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1)
Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n)
Shell Sort Ω(n log(n)) Θ(n(log(n))^2) O(n(log(n))^2) O(1)
Bucket Sort Ω(n+k) Θ(n+k) O(n^2) O(n)
Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k)
Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k)
Cube Sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

 

Selection Sort Program and Complexity (Big-O)


Selection sort is a simple sorting algorithm, it’s also known as in-place comparison sort. In selection sort algorithm, sorts an array of items by repeatedly finding the minimum item from unsorted part of array and move it at the beginning. This algorithm considers two sub arrays in a given array.

  1. The sub array of already sorted items.
  2. Remaining sub array unsorted items.

Points to remember

  • Data structure: Array
  • Worst-case performance : О(n2) comparisons and O(n)swaps
  • Best-case performance : O(n2) comparisons and O(n) Swaps
  • Average performance: О(n2) comparisons and O(n) Swaps
  • Worst-case space complexity :О(n) total, O(1) auxiliary

See Also : Data Structure and Algorithms Complexity (Big-O)

Advantage

  • Simple Implementation and efficient for small data set.
  • Efficient in  comparison to other Quadratic Sort (i.e O(n2)) like Bubble Sort or  Insertion Sort.
  • Efficient for data set that are already sorted. Time Complexity ( i.e O(n))
  • Not change relative order of elements which are already sorted. Space Complexity (i.e O(1))

Disadvantage

  • Selection sort is much less efficient on large lists in compare to algorithms such as quicksort, heapsort, or merge sort.

Selection Sort Steps

Here * marks the value set on particular iteration.

2 6 3 8 4 1 5 0
0* 6 3 8 4 1 5 2
0 1* 3 8 4 6 5 2
0 1 2* 8 4 6 5 3
0 1 2 3* 4 6 5 8
0 1 2 3 4* 6 5 8
0 1 2 3 4 5* 6 8
0 1 2 3 4 5 6* 8

Selection Sort with Loop

public class SelectionSort {
	public static void main(String[] args) {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
		System.out.println("Before Selection Sorting :");
		printArray(items);

		// Perform selection sort
		selectionSort(items);

		System.out.println("After Selection Sorting :");
		printArray(items);
	}

	static void selectionSort(int items[]) {

		// select item one by one based on index
		for (int i = 0; i < items.length - 1; i++) {
			// Find the minimum item in unsorted array
			int min_idx = i;
			for (int j = i + 1; j < items.length; j++)
				if (items[j] < items[min_idx])
					min_idx = j;

			// Swap the found minimum selected item with
			// the first selected item
			int temp = items[min_idx];
			items[min_idx] = items[i];
			items[i] = temp;
		}
	}

	static void printArray(int items[]) {
		for (int item : items) {
			System.out.print(item + " ");
		}
		System.out.println();
	}
}

Output


Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8 

Insertion Sort Program and Complexity (Big-O)


Insertion sort is a simple sorting algorithm, which consumes one input item for each repetition, and grow a sorted output list. In every iteration, removes one item from input data, find the exact location in the sorted list and inserts it there. This process will repeat as long as no input items remain.

Points to remember

  • Data structure :  Array
  • Worst-case performance : О(n2) comparisons and swaps
  • Best-case performance : O(n) comparisons, O(1) swaps
  • Average performance: О(n2) comparisons and swaps
  • Worst-case space complexity : О(n) total, O(1) auxiliary

See Also: Data Structure and Algorithms Complexity (Big-O)

Advantage

  • Simple Implementation and efficient for small data set.
  • Not change relative order of elements which are already sorted
  • Efficient in comparison to other Quadratic Sort (i.e O(n2)) like Bubble Sort or Selection Sort.
  • Efficient for data set that are already sorted. Time Complexity( i.e O(n)).
  • Only required constant amount of memory space , as size of data set. Space
    Complexity (i.e O(1))

Disadvantage

  • Insertion sort is much less efficient on large lists in compare to algorithms such as quicksort, heapsort, or merge sort.

Insertion Sort Steps

Here * marks the value set on particular iteration.

2 6 3 8 4 1 5 0
2 6* 3 8 4 1 5 0
2 3* 6 8 4 1 5 0
2 3 6 8* 4 1 5 0
2 3 4* 6 8 1 5 0
1* 2 3 4 6 8 5 0
1 2 3 4 5* 6 8 0
0* 1 2 3 4 5 6 8

In following programs you will learn both the ways to implement Insertion Sort by For Loop and Recursion.

Insertion Sort with Loop

public class InsertionSort {
	public static void main(String[] args) {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Sorting :");
        printArrayTR(items);

        //Perform insertion sort
        insertionSort(items);

        System.out.println("After Sorting :");
        printArray(items);
	}

	static void insertionSort(int items[])
    {
        int n = items.length;
        for (int i = 1; i = 0 && items[j] > key) {
            	items[j + 1] = items[j];
                j = j - 1;
            }
            items[j + 1] = key;
            printArrayTR(items);
        }

    }
	static void printArray(int items[])
	{
        for (int item:items)
        {
            System.out.print(item + " ");
        }
        System.out.println();
	}
}

Output


Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8 

Insertion Sort with Recursion

public class InsertionSortRecursion {
	public static void main(String[] args) {
		int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
        System.out.println("Before Insertion Sorting :");
        printArray(items);

        //Perform insertion sort
        insertionSort(items,items.length);

        System.out.println("After Insertion Sorting :");
        printArray(items);
	}

	static void insertionSort(int items[],int n)
	{
		//base case or termination condition
		if(n= 0 && items[j] > last)
        {
        	items[j+1] = items[j];
            j--;
        }
        items[j+1] = last;
	}

	static void printArray(int items[])
	{
        for (int item:items)
        {
            System.out.print(item + " ");
        }
        System.out.println();
	}
}

Output


Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8 

Java : How to remove duplicate objects from List


In this below example list having duplicate object of AccountTransaction which need to remove from list. Here I am using HashSet because it always keep unique records. Now question comes how to decide uniqueness of object. As you know contract between hashcode() and equals() method deciding uniqueness and equality of object.

Here used Comparable interface to sort values based on transaction date.

hashcode() and equals() contract :

“If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result. If you only override equals() and not hashCode() your class violates this contract.”

Example


import java.math.BigDecimal;
import java.util.Date;

public class AccountTransaction implements Comparable{
	private Date date;
	String transactionType;
	private String reference;
	private BigDecimal amount;

	public AccountTransaction(Date date, String transactionType, String reference, BigDecimal amount) {
		super();
		this.date = date;
		this.transactionType = transactionType;
		this.reference = reference;
		this.amount = amount;
	}
//Overriding toString() method to print object
	@Override
	public String toString() {
		return "AccountTransactions [date=" + date + ", transactionType=" + transactionType + ", reference=" + reference
				+ ", amount=" + amount + "]";
	}
//Overriding hashcode() and equals() method to check equality and uniqueness
//of objects
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((amount == null) ? 0 : amount.hashCode());
		result = prime * result + ((date == null) ? 0 : date.hashCode());
		result = prime * result + ((reference == null) ? 0 : reference.hashCode());
		result = prime * result + ((transactionType == null) ? 0 : transactionType.hashCode());
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		AccountTransaction other = (AccountTransaction) obj;
		if (amount == null) {
			if (other.amount != null)
				return false;
		} else if (!amount.equals(other.amount))
			return false;
		if (date == null) {
			if (other.date != null)
				return false;
		} else if (!date.equals(other.date))
			return false;
		if (reference == null) {
			if (other.reference != null)
				return false;
		} else if (!reference.equals(other.reference))
			return false;
		if (transactionType == null) {
			if (other.transactionType != null)
				return false;
		} else if (!transactionType.equals(other.transactionType))
			return false;
		return true;
	}
	//Sort object by date
	@Override
	public int compareTo(AccountTransaction o) {

		return this.getDate().compareTo(o.getDate());
	}

	//use getter and setter of properties
}

Here is the class having sample data which is having duplicate objects in list. calling removeDuplicate() method which is converting list to hashSet() to remove duplicate and then again converting to list then sorting by date.


import java.math.BigDecimal;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RemoveDuplicateObjects {

	public static void main(String[] args) {
		List transactionList = new ArrayList();
		try {
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:50 AM"), "Account Debits", "Pizza hut",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:52 AM"), "Account Debits", "Pizza hut",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:48 AM"), "Account Debits", "Burger king",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:38 AM"), "Account Debits", "Burger king",new BigDecimal("1.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:55 AM"), "Account Debits", "Papa Johns",new BigDecimal("2.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:35 AM"), "Account Debits", "Pizza hut",new BigDecimal("1.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:35 AM"), "Account Credits", "Chase Bank",new BigDecimal("200")));
			//Duplicate record
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:52 AM"), "Account Debits", "Pizza hut",new BigDecimal("0.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:38 AM"), "Account Debits", "Burger king",new BigDecimal("1.56")));
			transactionList.add(new AccountTransaction(getDate("2018-10-15 10:35 AM"), "Account Credits", "Chase Bank",new BigDecimal("200")));

		   System.out.println("Transactions before removing duplicate=============");
		   for(AccountTransaction transaction:transactionList)
		   System.out.println(transaction);
		   System.out.println("Transactions after removing duplicate=============");
		   transactionList=removeDuplicate(transactionList);
		   for(AccountTransaction transaction:transactionList)
			   System.out.println(transaction);

		} catch (Exception ex) {
			ex.printStackTrace();
		}
	}

	private static List removeDuplicate(List transactionList)
	{
		//Convert List to Set
		Set transactionSet=new HashSet(transactionList);
		//Convert Set to Array List
		transactionList=new ArrayList(transactionSet);

		//Sort object by transaction date and time
		Collections.sort(transactionList);

		return transactionList;
	}

	private static Date getDate(String dateStr) throws ParseException {
		return new SimpleDateFormat("yyyy-MM-dd HH:mm a").parse(dateStr);
	}
}

Output


Transactions before removing duplicate=============
AccountTransactions [date=Mon Oct 15 10:50:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:52:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:48:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:38:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:55:00 IST 2018, transactionType=Account Debits, reference=Papa Johns, amount=2.56]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Credits, reference=Chase Bank, amount=200]
AccountTransactions [date=Mon Oct 15 10:52:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:38:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Credits, reference=Chase Bank, amount=200]
Transactions after removing duplicate=============
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Credits, reference=Chase Bank, amount=200]
AccountTransactions [date=Mon Oct 15 10:35:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:38:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=1.56]
AccountTransactions [date=Mon Oct 15 10:48:00 IST 2018, transactionType=Account Debits, reference=Burger king, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:50:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:52:00 IST 2018, transactionType=Account Debits, reference=Pizza hut, amount=0.56]
AccountTransactions [date=Mon Oct 15 10:55:00 IST 2018, transactionType=Account Debits, reference=Papa Johns, amount=2.56]

See Also:

Java : Sort Date Time Object and Text Format


In Java classes java.util.Date, java.util.Calendar, java.time.LocalDateTime, java.time.LocalDate and java.time.LocalTime  implements comparable interface for natural ordering. We can sort these objects implements comparable interface as below


Collections.sort(List <Date> list);
Collections.sort(List <Calendar> list);
Collections.sort(List <LocalDateTime> list);
Collections.sort(List <LocalDate> list);
Collections.sort(List <LocalTime> list);

Problem occurred when date in String format and following different format pattern as MM/dd/yyyy ‘@’hh:mm a or some more patterns then you have to implement Comparator to sort this date text patterns as below


Collections.sort(dateStrList, new Comparator() {
DateFormat f = new SimpleDateFormat("MM/dd/yyyy '@'hh:mm a"); 

@Override public int compare(String o1, String o2) {
 try { 
   return f.parse(o1).compareTo(f.parse(o2)); 
} catch (ParseException e) { 
throw new IllegalArgumentException(e); 
} 
} }); 

To learn Comparator and Comparable check below link.

Java : Comparable Vs Comparator

In below example you will see sorting of date  in text format and objects also.

Example

package com.date;

import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SortingDateTime {
public static void main(String[] args) {
//java 8
sortDateTimeObject();
sortDateTimeText();
}

private static void sortDateTimeObject() {
List<LocalDateTime>dateTimeList=new ArrayList<LocalDateTime>();
dateTimeList.add(LocalDateTime.of(2012, 05, 12, 5, 16));
dateTimeList.add(LocalDateTime.of(2014, 03, 23, 11, 26));
dateTimeList.add(LocalDateTime.of(2011, 02, 13, 9, 36));
dateTimeList.add(LocalDateTime.of(2013, 11, 12, 5, 16));
dateTimeList.add(LocalDateTime.of(2017, 8, 11, 21, 26));
dateTimeList.add(LocalDateTime.of(2016, 9, 05, 19, 36));

DateTimeFormatter dateTimeFormatter = DateTimeFormatter
				.ofPattern("MM/dd/yyyy '@'hh:mm a");
System.out.println("---> Date & Time Object List Before Sort (MM/dd/yyyy '@'hh:mm a)");
for(LocalDateTime dateTime:dateTimeList)
{
System.out.println(dateTime.format(dateTimeFormatter));
}
// LocalDateTime  internally having Comparable interface no need additional Comparator
Collections.sort(dateTimeList);

System.out.println("---> Date & Time Object List After Sort (MM/dd/yyyy '@'hh:mm a)");
for(LocalDateTime dateTime:dateTimeList)
{
System.out.println(dateTime.format(dateTimeFormatter));
}

}

private static void sortDateTimeText()
{
List<String>dateStrList=new ArrayList<String>();
// MM/dd/yyyy '@'hh:mm a
dateStrList.add("01/21/2014 @03:13 PM");
dateStrList.add("01/21/2011 @04:37 PM");
dateStrList.add("01/21/2012 @10:41 AM");
dateStrList.add("01/21/2013 @10:48 AM");
dateStrList.add("01/22/2015 @06:16 AM");
dateStrList.add("01/22/2013 @06:19 AM");
dateStrList.add("01/21/2018 @05:19 PM");
dateStrList.add("01/21/2013 @05:19 PM");

System.out.println("---> Date & Time List Before Sort (MM/dd/yyyy '@'hh:mm a)");
for(String dateStr:dateStrList)
System.out.println(dateStr);

//Sort String Date
Collections.sort(dateStrList, new Comparator<String>() {
DateFormat f = new SimpleDateFormat("MM/dd/yyyy '@'hh:mm a");
@Override
public int compare(String o1, String o2) {
try {
  return f.parse(o1).compareTo(f.parse(o2));
    } catch (ParseException e) {
      throw new IllegalArgumentException(e);
    }
}
});

System.out.println("---> Date & Time List After Sort (MM/dd/yyyy '@'hh:mm a)");
for(String dateStr:dateStrList)
System.out.println(dateStr);
 }
}

Output


---> Date & Time Object List Before Sort (MM/dd/yyyy '@'hh:mm a)
05/12/2012 @05:16 AM
03/23/2014 @11:26 AM
02/13/2011 @09:36 AM
11/12/2013 @05:16 AM
08/11/2017 @09:26 PM
09/05/2016 @07:36 PM
---> Date & Time Object List After Sort (MM/dd/yyyy '@'hh:mm a)
02/13/2011 @09:36 AM
05/12/2012 @05:16 AM
11/12/2013 @05:16 AM
03/23/2014 @11:26 AM
09/05/2016 @07:36 PM
08/11/2017 @09:26 PM
---> Date & Time List Before Sort (MM/dd/yyyy '@'hh:mm a)
01/21/2014 @03:13 PM
01/21/2011 @04:37 PM
01/21/2012 @10:41 AM
01/21/2013 @10:48 AM
01/22/2015 @06:16 AM
01/22/2013 @06:19 AM
01/21/2018 @05:19 PM
01/21/2013 @05:19 PM
---> Date & Time List After Sort (MM/dd/yyyy '@'hh:mm a)
01/21/2011 @04:37 PM
01/21/2012 @10:41 AM
01/21/2013 @10:48 AM
01/21/2013 @05:19 PM
01/22/2013 @06:19 AM
01/21/2014 @03:13 PM
01/22/2015 @06:16 AM
01/21/2018 @05:19 PM

Java : Sort Date Object and Text Format


In Java classes java.util.Date, java.util.Calendar, java.time.LocalDateTime, java.time.LocalDate and java.time.LocalTime  implements comparable interface for natural ordering. We can sort these objects implements comparable interface as below


Collections.sort(List <Date> list);
Collections.sort(List <Calendar> list);
Collections.sort(List <LocalDateTime> list);
Collections.sort(List <LocalDate> list);
Collections.sort(List <LocalTime> list);

Problem occurred when date in String format and following different format pattern as dd/MM/yyyy or some more patterns then you have to implement Comparator to sort this date text patterns as below


Collections.sort(dateStrList, new Comparator() {
DateFormat f = new SimpleDateFormat("dd/MM/yyyy"); 

@Override public int compare(String o1, String o2) {
 try { 
   return f.parse(o1).compareTo(f.parse(o2)); 
} catch (ParseException e) { 
throw new IllegalArgumentException(e); 
} 
} }); 

To learn Comparator and Comparable check below link.

Java : Comparable Vs Comparator

In below example you will see sorting of date  in text format and objects also.

Example

package com.date;

import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.time.LocalDate;
import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class SortingDate {

public static void main(String[] args) {
 //java 8
sortDateObject();
sortDateText();
}

private static void sortDateText() {
List<String>dateStrList=new ArrayList<String>();
// Date format dd/MM/YYYY
dateStrList.add("03/04/2016");
dateStrList.add("03/01/2016");
dateStrList.add("02/06/2016");
dateStrList.add("02/09/2016");
dateStrList.add("22/09/2016");
dateStrList.add("16/09/2016");
dateStrList.add("03/04/2016");
dateStrList.add("01/08/2017");
dateStrList.add("02/06/2017");
dateStrList.add("02/09/2014");
dateStrList.add("22/09/2018");
dateStrList.add("16/09/2015");

System.out.println("---> Date List Before Sort (dd/MM/yyyy)");
for(String dateStr:dateStrList)
System.out.println(dateStr);

//Sort String Date
Collections.sort(dateStrList, new Comparator<String>() {
DateFormat f = new SimpleDateFormat("dd/MM/yyyy");
    @Override
    public int compare(String o1, String o2) {
    try {
	 return f.parse(o1).compareTo(f.parse(o2));
	} catch (ParseException e) {
	       throw new IllegalArgumentException(e);
	   }
	   }
	});

    System.out.println("---> Date List After Sort (dd/MM/yyyy)");
    for(String dateStr:dateStrList)
    System.out.println(dateStr);

	}

private static void sortDateObject() {
List<LocalDate>dateList=new ArrayList<LocalDate>();
dateList.add(LocalDate.of(2012, 05, 12));
dateList.add(LocalDate.of(2014, 03, 23));
dateList.add(LocalDate.of(2011, 02, 13));
dateList.add(LocalDate.of(2013, 11, 12));
dateList.add(LocalDate.of(2017, 8, 11));
dateList.add(LocalDate.of(2016, 9, 05));

DateTimeFormatter dateTimeFormatter = DateTimeFormatter
				.ofPattern("MM/dd/yyyy");
System.out.println("---> Date  Object List Before Sort (MM/dd/yyyy)");
for(LocalDate localDate:dateList)
{
  System.out.println(localDate.format(dateTimeFormatter));
}
// LocalDate  internally having Comparable interface no need additional Comparator
Collections.sort(dateList);

System.out.println("---> Date Object List After Sort (MM/dd/yyyy)");
for(LocalDate localDate:dateList)
{
System.out.println(localDate.format(dateTimeFormatter));
}

}

}

Output


---> Date  Object List Before Sort (MM/dd/yyyy)
05/12/2012
03/23/2014
02/13/2011
11/12/2013
08/11/2017
09/05/2016
---> Date Object List After Sort (MM/dd/yyyy)
02/13/2011
05/12/2012
11/12/2013
03/23/2014
09/05/2016
08/11/2017
---> Date List Before Sort (dd/MM/yyyy)
03/04/2016
03/01/2016
02/06/2016
02/09/2016
22/09/2016
16/09/2016
03/04/2016
01/08/2017
02/06/2017
02/09/2014
22/09/2018
16/09/2015
---> Date List After Sort (dd/MM/yyyy)
02/09/2014
16/09/2015
03/01/2016
03/04/2016
03/04/2016
02/06/2016
02/09/2016
16/09/2016
22/09/2016
02/06/2017
01/08/2017
22/09/2018

How to sort object by Comparator interface in ascending and descending order : JAVA


As in previous posts shown like wrapper of primitive type , String and Date classes having  implements in-built comparable interface and also sort user-defined classes by implements  Comparable interface which provide natural or chronological or alphabetical sorting of elements.

Sort ArrayList in Ascending or Descending Order or Natural or Chronological Order

How to Sort By Comparable Interface in Ascending and Descending Order : Java

Java : Comparable Vs Comparator

What is Comparator Interface?

java.util.Comparator  interface imposes user define sorting on different class fields  based on comparing values from different objects.  It provide compare() method which compares two objects  and returns a negative integer, 0, or a positive integer depending on whether the receiving object is less than, equal to, or greater than the specified object. If the specified object cannot be compared to the receiving object, the method throws a ClassCastException.

How to use Comparator Interface?

Below is syntax of compare method:

public interface Comparator {
    public int compare(T o1, T o2);

}

compare() method compare two objects  fields values and return negative integer, 0 or a positive integer and Collections.sort() method will sort based on this return value.

Lists (and arrays) of objects that implement this comparator interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this comparator  interface can be used as keys in a sorted map or as elements in a sorted set, without the need to specify a comparable.

Note :  Below example is base on List of Employee objects it cannot be used to order a sorted collection, such as TreeSet because it generates an ordering that is not compatible with equals. It means that Comparator equates objects that the equals method does not.

In particular, any two employees who were joined on the same date will compare as equal. When you’re sorting a List this doesn’t matter; but when you’re using the Comparator to order a sorted collection, it’s fatal. If you use this Comparator to insert multiple employees joined on the same date into a TreeSet only the first one will be added to the set; the second will be seen as a duplicate element and will be ignored.

Example :

Below is simple Employee class which is having fields and getter/setter methods and also constructor to create object.

package sorting
public class Employee {
private int id;
private String firtsName;
private String lastName;
private String designation;
private double salary;
private int age;

//Default Constructor
public Employee()
{
}
//Parametrize Constructor
public Employee(int id, String firtsName, String lastName, String designation, double salary, int age) {
	super();
	this.id = id;
	this.firtsName = firtsName;
	this.lastName = lastName;
	this.designation = designation;
	this.salary = salary;
	this.age = age;
}

public int getId() {
	return id;
}
public void setId(int id) {
	this.id = id;
}
public String getFirtsName() {
	return firtsName;
}
public void setFirtsName(String firtsName) {
	this.firtsName = firtsName;
}
public String getLastName() {
	return lastName;
}
public void setLastName(String lastName) {
	this.lastName = lastName;
}
public String getDesignation() {
	return designation;
}
public void setDesignation(String designation) {
	this.designation = designation;
}
public double getSalary() {
	return salary;
}
public void setSalary(double salary) {
	this.salary = salary;
}
public int getAge() {
	return age;
}
public void setAge(int age) {
	this.age = age;
}

@Override
public String toString() {
	return "Employee [id=" + id + ", firtsName=" + firtsName + ", lastName=" + lastName + ", designation=" + designation
			+ ", salary=" + salary + ", age=" + age + "]";
}
}

Here we have created EmpComparator class and implements compare() method  of java.util.Comparator interface which will compare object fields values based on selected fields on time of sorting. ex: sortingField value.

For example : sortingField value as firstName then compare() method of  java.util.Comparator  interface will compare firstName value of passing two object on compare() method and return a integer value like (negative integer, 0 or positive integer) depend on compare result.

package sorting;
import java.util.Comparator;

public class EmpComparator implements Comparator {
	public static final String ID = "id";
	public static final String FIRST_NAME = "firstName";
	public static final String LAST_NAME = "lastName";
	public static final String DESIGNATION = "designation";
	public static final String SALARY = "salary";
	public static final String AGE = "age";
	private String sortingField;

	@Override
	public int compare(Employee emp1, Employee emp2) {
		int diff = 0;
		switch (sortingField) {
		case ID:
			diff=emp1.getId()-emp2.getId();
			break;
		case FIRST_NAME:
			diff=emp1.getFirtsName().compareTo(emp2.getFirtsName());
			break;
		case LAST_NAME:
			diff=emp1.getLastName().compareTo(emp2.getLastName());
			break;
		case DESIGNATION:
			diff=emp1.getDesignation().compareTo(emp2.getDesignation());
			break;
		case SALARY:
			diff=(int)(emp1.getSalary()-emp2.getSalary());
			break;
		case AGE:
			diff=emp1.getAge()-emp2.getAge();
			break;

		}
		return diff;
	}

	public String getSortingField() {
		return sortingField;
	}

	public void setSortingField(String sortingField) {
		this.sortingField = sortingField;
	}
}

Here in below example creating List of Employee objects for sorting in ascending and descending order.

For sorting by firstName assigning value of sortingField as “firstName” in empComparator object. First we are using Collections.sort(List, Comparator) sorting method to sort list in ascending order by firstName because current value of sortingField is firstName. For descending order we will just reverse order of objects by Collections.resverse() method. Similarly using for lastName and also try with other fields of Employee class.

package sorting;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortComparator {

	public static void main(String[] args) {
		Employee[] empArr = {
				new Employee(1, "Saurabh", "Gupta", "Sr Project Lead", 60000, 35),
				new Employee(2, "Gaurav", "Gupta", "Developer", 50000, 32),
				new Employee(3, "Shailesh", "Nagar", "Manager", 100000, 36),
				new Employee(4, "Ankur", "Mehrotra", "Lead", 55000, 30),
				new Employee(5, "Ranjith", "Ranjan", "Tester", 35000, 45),
				new Employee(6, "Ramesh", "Bhardwaj", "Support", 25000, 35)
				};
		// Convert Array to LIst
		List empList = Arrays.asList(empArr);
		// Print Assigned Values Before Sort;
		System.out.println("********Print Employee List Before Sort********");
		printArrayList(empList);

		// Sort List in Ascending order by first Name
		EmpComparator empComparator = new EmpComparator();
		empComparator.setSortingField("firstName");
		Collections.sort(empList, empComparator);
		System.out.println("\n********Print Employee List in Ascending Order********");
		printArrayList(empList);

		// Sort List in Descending order by FirtName
		Collections.reverse(empList);
		System.out.println("\n********Print Employee List in Descending Order********");
		printArrayList(empList);

		// Sort List in Ascending order by lastName

		empComparator.setSortingField("lastName");
		Collections.sort(empList, empComparator);
		System.out.println("\n********Print Employee List in Ascending Order********");
		printArrayList(empList);

		// Sort List in Descending order by last Name
		Collections.reverse(empList);
		System.out.println("\n********Print Employee List in Descending Order********");
		printArrayList(empList);

	}

	private static void printArrayList(List empList) {
		for (Employee emp : empList) {
			System.out.println(emp);<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>
		}
	}
}

Output :

********Print Employee List Before Sort********
Employee [id=1, firtsName=Saurabh, lastName=Gupta, designation=Sr Project Lead, salary=60000.0, age=35]
Employee [id=2, firtsName=Gaurav, lastName=Gupta, designation=Developer, salary=50000.0, age=32]
Employee [id=3, firtsName=Shailesh, lastName=Nagar, designation=Manager, salary=100000.0, age=36]
Employee [id=4, firtsName=Ankur, lastName=Mehrotra, designation=Lead, salary=55000.0, age=30]
Employee [id=5, firtsName=Ranjith, lastName=Ranjan, designation=Tester, salary=35000.0, age=45]
Employee [id=6, firtsName=Ramesh, lastName=Bhardwaj, designation=Support, salary=25000.0, age=35]

********Print Employee List in Ascending Order********
Employee [id=4, firtsName=Ankur, lastName=Mehrotra, designation=Lead, salary=55000.0, age=30]
Employee [id=2, firtsName=Gaurav, lastName=Gupta, designation=Developer, salary=50000.0, age=32]
Employee [id=6, firtsName=Ramesh, lastName=Bhardwaj, designation=Support, salary=25000.0, age=35]
Employee [id=5, firtsName=Ranjith, lastName=Ranjan, designation=Tester, salary=35000.0, age=45]
Employee [id=1, firtsName=Saurabh, lastName=Gupta, designation=Sr Project Lead, salary=60000.0, age=35]
Employee [id=3, firtsName=Shailesh, lastName=Nagar, designation=Manager, salary=100000.0, age=36]

********Print Employee List in Descending Order********
Employee [id=3, firtsName=Shailesh, lastName=Nagar, designation=Manager, salary=100000.0, age=36]
Employee [id=1, firtsName=Saurabh, lastName=Gupta, designation=Sr Project Lead, salary=60000.0, age=35]
Employee [id=5, firtsName=Ranjith, lastName=Ranjan, designation=Tester, salary=35000.0, age=45]
Employee [id=6, firtsName=Ramesh, lastName=Bhardwaj, designation=Support, salary=25000.0, age=35]
Employee [id=2, firtsName=Gaurav, lastName=Gupta, designation=Developer, salary=50000.0, age=32]
Employee [id=4, firtsName=Ankur, lastName=Mehrotra, designation=Lead, salary=55000.0, age=30]

********Print Employee List in Ascending Order********
Employee [id=6, firtsName=Ramesh, lastName=Bhardwaj, designation=Support, salary=25000.0, age=35]
Employee [id=1, firtsName=Saurabh, lastName=Gupta, designation=Sr Project Lead, salary=60000.0, age=35]
Employee [id=2, firtsName=Gaurav, lastName=Gupta, designation=Developer, salary=50000.0, age=32]
Employee [id=4, firtsName=Ankur, lastName=Mehrotra, designation=Lead, salary=55000.0, age=30]
Employee [id=3, firtsName=Shailesh, lastName=Nagar, designation=Manager, salary=100000.0, age=36]
Employee [id=5, firtsName=Ranjith, lastName=Ranjan, designation=Tester, salary=35000.0, age=45]

********Print Employee List in Descending Order********
Employee [id=5, firtsName=Ranjith, lastName=Ranjan, designation=Tester, salary=35000.0, age=45]
Employee [id=3, firtsName=Shailesh, lastName=Nagar, designation=Manager, salary=100000.0, age=36]
Employee [id=4, firtsName=Ankur, lastName=Mehrotra, designation=Lead, salary=55000.0, age=30]
Employee [id=2, firtsName=Gaurav, lastName=Gupta, designation=Developer, salary=50000.0, age=32]
Employee [id=1, firtsName=Saurabh, lastName=Gupta, designation=Sr Project Lead, salary=60000.0, age=35]
Employee [id=6, firtsName=Ramesh, lastName=Bhardwaj, designation=Support, salary=25000.0, age=35]
<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>

Reference :

https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

How to Sort By Comparable Interface in Ascending and Descending Order : Java


As in previous post shown like wrapper of primitive type , String and Date classes having  implements in-built comparable interface which provide natural or chronological or alphabetical sorting of elements.

Sort ArrayList in Ascending or Descending Order or Natural or Chronological Order

How to sort object by Comparator interface in ascending and descending order : JAVA

Java : Comparable Vs Comparator

What is Comparable Interface?

java.lang.Comparable  interface imposes a total natural ordering on the objects of each class that implements it.  it provide compareTo() method which compares the receiving object with the specified object and returns a negative integer, 0, or a positive integer depending on whether the receiving object is less than, equal to, or greater than the specified object. If the specified object cannot be compared to the receiving object, the method throws a ClassCastException.

How to use Comparable Interface?

Below is syntax of compareTo method:

public interface Comparable {
    public int compareTo(T o);

}

compareTo() method compare current object (this)  fields values with passing object fields values and return negative integer, 0 or a positive integer and Collections.sort() method will sort based on this return value.

Lists (and arrays) of objects that implement this comparable interface can be sorted automatically by Collections.sort (and Arrays.sort). Objects that implement this comparable interface can be used as keys in a sorted map or as elements in a sorted set, without the need to specify a comparator.

Example :

Below Employee class implements compareTo() method of  java.lang.Comparable  interface which is comparing firstName value with specified object firstName value. This  method return a integer value like (negative integer, 0 or positive integer) depend on compare result.

package sorting;

public class Employee implements Comparable{
private int id;
private String firtsName;
private String lastName;
private String designation;
private double salary;
private int age;

//Default Constructor
public Employee()
{

}

//Parametrize Constructor
public Employee(int id, String firtsName, String lastName, String designation, double salary, int age) {
	super();
	this.id = id;
	this.firtsName = firtsName;
	this.lastName = lastName;
	this.designation = designation;
	this.salary = salary;
	this.age = age;
}

@Override
public int compareTo(Employee employee) {
	//sort by firstName
	return this.firtsName.compareTo(employee.firtsName);
}

public int getId() {
	return id;
}
public void setId(int id) {
	this.id = id;
}
public String getFirtsName() {
	return firtsName;
}
public void setFirtsName(String firtsName) {
	this.firtsName = firtsName;
}
public String getLastName() {
	return lastName;
}
public void setLastName(String lastName) {
	this.lastName = lastName;
}
public String getDesignation() {
	return designation;
}
public void setDesignation(String designation) {
	this.designation = designation;
}
public double getSalary() {
	return salary;
}
public void setSalary(double salary) {
	this.salary = salary;
}
public int getAge() {
	return age;
}
public void setAge(int age) {
	this.age = age;
}

@Override<span id="mce_SELREST_start" style="overflow:hidden;line-height:0;"></span>
public String toString() {
	return "Employee [id=" + id + ", firtsName=" + firtsName + ", lastName=" + lastName + ", designation=" + designation
			+ ", salary=" + salary + ", age=" + age + "]";
}

}

In below class sorting  Employee list objects by names in ascending order by Collections.sort(list). As shown above Employee Class implements  Comparable interface and it’s  compareTo() method  will sort elements in Ascending order by firstName on objects.

For Descending order used Collections.reverse(List) reverse method which will reverse list of sorted list.

 

package sorting;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortComparable {

	public static void main(String[] args) {
		Employee [] empArr={
				new Employee(1,"Saurabh","Gupta","Sr Project Lead",60000,35),
				new Employee(2,"Gaurav","Gupta","Developer",50000,32),
				new Employee(3,"Shailesh","Nagar","Manager",100000,36),
				new Employee(4,"Ankur","Mehrotra","Lead",55000,30),
				new Employee(5,"Ranjith","Ranjan","Tester",35000,45),
				new Employee(6,"Ramesh","Bhardwaj","Support",25000,35)
				};
		//Convert Array to LIst
		List empList=Arrays.asList(empArr);
		//Print Assigned Values Before Sort;
		System.out.println("********Print Employee List Before Sort********");
		printArrayList(empList);

		//Sort List in Ascending order by collections api
		Collections.sort(empList);
		System.out.println("\n********Print Employee List in Ascending Order********");
		printArrayList(empList);

		//Sort List in Descending order by collections api
		Collections.reverse(empList);
		System.out.println("\n********Print Employee List in Descending Order********");
		printArrayList(empList);

	}

	private static void printArrayList(List empList)
	{
		for(Employee emp:empList)
		{
			System.out.println(emp);
		}
	}
}

 

Reference :

https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

Sort ArrayList in Ascending or Descending Order or Natural or Chronological Order


Collections framework provide Collections.sort(List) method which sort String elements in natural or chronological order or ascending order.

For descending order use Collections.reverse(List) method to reverse order of complete list elements.

Related Topics:

How to Sort By Comparable Interface in Ascending and Descending Order : Java

How to sort object by Comparator interface in ascending and descending order : JAVA

Java : Comparable Vs Comparator

Points to Remember:

  • Below are classes  implements  Comparable interface which provide a natural ordering for a class  sorted automatically.
  • If sorting a list of the elements which do not  implement Comparable , Collections.sort(list) method will throw ClassCastException. Similarly, Collections.sort(list, comparator ) will throw ClassCastException if you try to sort a list whose elements cannot be compared to another using Comparator.
                                 Classes Implementing Comparable
Class Natural Ordering
Byte Signed numerical
Character Unsigned numerical
Long Signed numerical
Integer Signed numerical
Short Signed numerical
Double Signed numerical
Float Signed numerical
BigInteger Signed numerical
BigDecimal Signed numerical
Boolean Boolean.FALSE < Boolean.TRUE
File System-dependent lexicographic on path name
String Lexicographic
Date Chronological
CollationKey Locale-specific lexicographic

Example :
In below example sorting list of names in ascending order by Collections.sort(list). As shown above String Class by default having Comparable interface which will sort elements in Ascending or Chronological order.

For Descending order used Collections.reverse(List) reverse method which will reverse list of sorted list.

package sorting;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SortData {

	public static void main(String[] args) {
		String [] empArr={"Saurabh","Gaurav","Shailesh","Ankur","Ranjith","Ramesh"};
		//Convert Array to LIst
		List empList=Arrays.asList(empArr);
		//Print Assigned Values Before Sort;
		System.out.println("********Print Employee List Before Sort********");
		printArrayList(empList);

		//Sort List in Ascending order by collections api
		Collections.sort(empList);
		System.out.println("\n********Print Employee List in Ascending Order********");
		printArrayList(empList);

		//Sort List in Descending order by collections api
		Collections.reverse(empList);
		System.out.println("\n********Print Employee List in Descending Order********");
		printArrayList(empList);

	}

	private static void printArrayList(List empList)
	{
		for(String emp:empList)
		{
			System.out.println(emp);
		}
	}

}

Output:

********Print Employee List Before Sort********
Saurabh
Gaurav
Shailesh
Ankur
Ranjith
Ramesh

********Print Employee List in Ascending Order********
Ankur
Gaurav
Ramesh
Ranjith
Saurabh
Shailesh

********Print Employee List in Descending Order********
Shailesh
Saurabh
Ranjith
Ramesh
Gaurav
Ankur

Reference :

https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

How to sort HTML Table Columns in ascending and descending by JQuery and JAVA Script and show sorting image


Below example is for sorting HTML table on ascending and descending order after click on header name. Based on sorting will display ascending and descending images.

Source Code

Copy your ascending and descending images on images folder and change path according to you project configuration.


Sort Table

var order;
function sortTable(col)
{
	changeSortHeaderImage(col);
	//get list of all rows of table content except header
	var rows=$('#employeeTbl tbody tr').get();

	rows.sort(function(a,b){
	var A= $(a).children('td').eq(col).text().toUpperCase();
	var B= $(b).children('td').eq(col).text().toUpperCase();
	//sort in ascending order
	if(order=="asc")
		{
	return (A <b> B) ? 1 : 0);
		}
	//sort in descnding order
	if(order=="desc")
		{
	return (B <a> A) ? 1 : 0);
		}
	});
	//iterate each row of table for changing order
	$.each(rows, function(index, row) {
	    $('#employeeTbl').children('tbody').append(row);
	  });
}
//Change image for column sorting
function changeSortHeaderImage(col)
{	

	var imgArr= document.getElementById("employeeTbl").getElementsByTagName('input');
    var altAtr;
    for (i = 0; i &lt; imgArr.length; i++) {

            altAtr=imgArr[i].getAttribute(&quot;alt&quot;);

              if(i==col &amp;&amp; &quot;asc&quot; == altAtr)
                 {
                    imgArr[i].setAttribute(&quot;src&quot;, &quot;images/desc.png&quot;);
                    imgArr[i].setAttribute(&quot;alt&quot;, &quot;desc&quot;);
                    order=&quot;desc&quot;;
                  }
           else if (i==col &amp;&amp; (&quot;nosort&quot; == altAtr ||  &quot;desc&quot; == altAtr))
                 {
                 imgArr[i].setAttribute(&quot;src&quot;, &quot;images/asc.png&quot;);
                 imgArr[i].setAttribute(&quot;alt&quot;, &quot;asc&quot;);
                 order=&quot;asc&quot;;
                 }
           else
                 {
                 imgArr[i].setAttribute(&quot;src&quot;, &quot;images/nosort.png&quot;);
                 imgArr[i].setAttribute(&quot;alt&quot;, &quot;nosort&quot;);
                 }
           }

}</a></b></pre>
&nbsp;
<table id="employeeTbl">
<thead>
<tr>
<th>ID</th>
<th>Name</th>
<th>Age</th>
<th>Designation</th>
<th>Salary</th>
</tr>
<tr>
<td>1</td>
<td>Saurabh Gupta</td>
<td>34</td>
<td>Sr Lead</td>
<td>50000</td>
</tr>
<tr>
<td>2</td>
<td>Gaurav Gupta</td>
<td>30</td>
<td>Software Engineer</td>
<td>40000</td>
</tr>
<tr>
<td>3</td>
<td>Ranjith Kumar</td>
<td>45</td>
<td>Manager</td>
<td>60000</td>
</tr>
<tr>
<td>4</td>
<td>Sakshi Mehta</td>
<td>25</td>
<td>Trainee</td>
<td>25000</td>
</tr>
<tr>
<td>5</td>
<td>Arun Roi</td>
<td>35</td>
<td>Tester</td>
<td>28000</td>
</tr>
<tr>
<td>6</td>
<td>Nitin Verma</td>
<td>40</td>
<td>SEO</td>
<td>55000</td>
</tr>
</thead>
</table>
<pre><b><a>

Initial Table Without Soring

HTML Table Sort column by Jquery Intial
Initial Employee Detail Table Without Sorting

Sort in Ascending Order for Column Designation

HTML Table Sort columns by Jquery Ascending
Employee Table  with Ascending Order soring for column  Designation

Sort in Descending Order for column Designation

HTML Table Sort columns by Jquery descending
Employee Table  with Desscending Order soring for column  Designation

 Summary

In above example. I try to cover below topics.

  • How to create HTML Table with column header and rows column content.
  • Apply JQuery and Java Script for sorting ascending and descending order on click each columns.
  • On click Change columns header sorting images by Java Script.
  • How to apply CSS on table column headers and background image.