# 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 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.

## 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

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)

``````
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

``````

```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 };
printArray(items);

// Perform counting sort sort

printArray(items);
}

// radix sort method to sort values of array 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

``````
170 45 75 90 2 802 2 66
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
}

//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)

• 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.

• 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

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

• 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
``````

# 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

• 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))

• 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

• 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))

• 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]
``````

# 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>();

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

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

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>();

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

``````

# Java : Comparable Vs Comparator

Comparable and Comparator both are interface used for compare and sorting collections of objects. Where  Comparable used for natural ordering of objects while Comparator used for sorting on user specific value on different type objects. In both the cases if objects are not equate or compatible will through ClassCastException.

In below links, I have explained about in depth detail about Comparable and Comparator implementation and cases where to use. Here mainly focus on some points for technical, implementation and functional points.

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

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

## Difference between Comparable and Comparator

Comparable Comparator
Comparable is in java lang package as java.lang.Comparable. Comparator is in java util package as java.util.Comparator.
Method used int compareTo(Object t); Method used int compare(Object t1 , Object t2);

Comparable is used to compare itself by using with another object.

Here modify the class whose instance you want to sort. So that only one sort sequence can be created per class.

Comparator is used to compare two datatypes are objects.

Here build a class separate from class whose instance you want to sort. So that multiple sort sequence can be created per class.

A comparable used for default and natural ordering of objects.  A comparator represents the ordering itself for specific use.

Some java classes having build in Comparable interface like String, Date, Wrapper Classes etc.

Some classes actually provide Comparators for common cases; for instance, Strings are by default case-sensitive when sorted, but there is also a static Comparator called CASE_INSENSITIVE_ORDER.
For sorting use methods like Collections.Sort(List) or Array.sort().  For Sorting use method Collections.sort(List, Comparator).

Reference :

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

# 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(2,"Gaurav","Gupta","Developer",50000,32),
new Employee(3,"Shailesh","Nagar","Manager",100000,36),
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)
{
//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
{

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">
<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>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>
</table>
<pre><b><a>

```

## 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.

# 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