Showing posts with label Sorting. Show all posts
Showing posts with label Sorting. Show all posts

Sorting HashMap by Values including duplicate in Java

We have seen sorting HashMap based on custom objects by implementing Comparator and Comparable interfaces. Now lets see how to sort HashMap using values which has duplicate. Can be sorted with multiple ways like using Comparator interface, using Stream from Java 8 etc.,

Sorting HashMap based on values


Sorting HashMap based on custom objects

Now lets see simple example to sort HashMap based on value which has dupilcate using Comparator interface.

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class SortingHashMap {

 public static void main(String[] args) {

  Map<String, Integer> map = new HashMap<String, Integer>();
  map.put("java", 100);
  map.put(".net", 80);
  map.put("python", 99);
  map.put("C++", 65);
  map.put("C", 70);
  map.put("Orale", 65);
  
  System.out.println("Before Sorting : "+map);
  
  map = new SortingHashMap().sortMapByValue(map);
  
  System.out.println("After Sorting  : "+map);
 }

 private Map<String, Integer> sortMapByValue(Map<String, Integer> map) {

  List<Entry<String, Integer>> list = new LinkedList<Entry<String, Integer>>(map.entrySet());
  /*
   * Sorting map values by using Comparator
   */
  Collections.sort(list, new Comparator<Entry<String, Integer>>() {
   public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
    return o1.getValue().compareTo(o2.getValue());
   }
  });

  // LinkedMap to maintain the sorted value order 
  Map<String, Integer> sortedMap = new LinkedHashMap<String, Integer>();
  for (Entry<String, Integer> entry : list) {
   sortedMap.put(entry.getKey(), entry.getValue());
  }

  return sortedMap;
 }
}


OUTPUT:

Before Sorting : {python=99, C++=65, java=100, C=70, .net=80, Orale=65}
After Sorting  : {C++=65, Orale=65, C=70, .net=80, python=99, java=100}




Next we will see how to sort HashMap based on value using stream from Java 8


import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.stream.Collectors;

public class SortingHashMap {

 public static void main(String[] args) {

  Map<String, Integer> map = new HashMap<String, Integer>();
  map.put("java", 100);
  map.put(".net", 80);
  map.put("python", 99);
  map.put("C++", 65);
  map.put("C", 70);
  map.put("Orale", 65);
  
  System.out.println("Before Sorting : "+map);
  
  map = new SortingHashMap().sortMapByValue(map);
  
  System.out.println("After Sorting  : "+map);
 }

 private Map<String, Integer> sortMapByValue(Map<String, Integer> map) {

  Map<String, Integer> sortedMap = 
        map.entrySet().stream()
       .sorted(Entry.comparingByValue())
       .collect(Collectors.toMap(Entry::getKey, Entry::getValue,
                           (o1, o2) -> o1, LinkedHashMap::new));
  
  return sortedMap;
 }
}


OUTPUT:


Before Sorting : {python=99, C++=65, java=100, C=70, .net=80, Orale=65}
After Sorting  : {C++=65, Orale=65, C=70, .net=80, python=99, java=100}

Selection sort

 
Selection sort is conceptually the most simplest sorting algorithm. This algorithm will first find the smallest element in the array and swap it with the element in the first position, then it will find the second smallest element and swap it with the element in the second position, and it will keep on doing this until the entire array is sorted. It is called selection sort because it repeatedly selects the next-smallest element and swaps it into the right place.
Selection Sort


public class SelectionSort {

 public static void main(String[] args) {

  int[] arr = { 4, 14, 6, 15, 8, 0, 313, 80, 21, 67, 81, 142 };

  printArray(arr, "BEFORE SORTING : ");

  selectionSort(arr);

  printArray(arr, "AFTER SORTING : ");
 }

 public static void selectionSort(int[] arr) {

  for (int i = 0; i < arr.length; i++) {
   int minIndex = i;
   for (int j = i + 1; j < arr.length; j++) {
    if (arr[j] < arr[minIndex]) {
     minIndex = j;
    }
   }
   if (minIndex != i) {
    int tmp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = tmp;
   }
  }
 }

 public static void printArray(int[] arr, String msg) {
  System.out.print(msg);
  for (int i : arr) {
   System.out.print(i + ", ");
  }
  System.out.println();
 }
}


OUTPUT:


BEFORE SORTING : 4, 14, 6, 15, 8, 0, 313, 80, 21, 67, 81, 142, 
AFTER SORTING : 0, 4, 6, 8, 14, 15, 21, 67, 80, 81, 142, 313, 

Selection sort in Java

 
Selection sort is a combination of searching (search for smaller element) and sorting (Swap with first element) and move on. During each pass unsorted element with the smallest value will be swapped to its proper position. Number of times the loop passes through the array will be one less than the size of array (N-1 times). 
In selection sort we need to 2 loops as same as bubble sort, where here inner loop will find the smallest element and outer loop need to swap with the other element and need to place it in proper position. Now lets see simple Java code for selection sort.
Selection sort in Java


public class SelectionSort {

 public static void main(String[] args) {
  int array[] = {3,4,8,5,1,7,9,2,6};
  System.out.print("Array before sorting : ");
  printArray(array);
  
  selectionSort(array);
  
  System.out.print("Array after sorting : ");
  printArray(array);
 }

 public static void selectionSort(int[] values) {
  for (int i = values.length - 1; i > 0; i--) {
   int first = 0; 
   for (int j = 1; j <= i; j++) {
    if (values[j] > values[first])
     first = j;
   }
   int tmp = values[first]; 
   values[first] = values[i];
   values[i] = tmp;
  }
 }
 
 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.print(i + ", ");
  }
  System.out.println();
 }
}



OUTPUT:


Array before sorting : 3, 4, 8, 5, 1, 7, 9, 2, 6, 
Array after sorting : 1, 2, 3, 4, 5, 6, 7, 8, 9, 



Sorting duplicate elements in single array

 
There are lot of sorting algorithms like bubble sort, quick sort, insertion sort, rad-ix sort etc., But all these sorting algorithm gives array of elements in an ascending or descending order. 
In point of interview if they ask to sort the array with all the duplicate elements should be placed at end of the array again with sorted sub arrays.
Sorting duplicate elements in single array


For example 

Input array : { 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3 }

Output array : {1, 2, 3, 4, 5, 6, 8,    1, 2, 3, 4, 5,    3, 5,   5 }

If we see above output, input array has been sorted with sub arrays with all duplicate elements at last. So lets see simple java code with the help of Collection API to sort the given array as per above problem


import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class DuplicateArraySort {

 public static void main(String[] args) {

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

  System.out.print("Before array sorting : ");
  printArray(array);

  Map<Integer, Integer> myMap = generateMap(array);
  Set<Integer> set = (Set<Integer>) myMap.keySet();

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

   Iterator<Integer> itr = set.iterator();

   while (itr.hasNext()) {
    int key = itr.next();
    if ((myMap.get(key)) > 0) {
     myMap.put(key, (myMap.get(key) - 1));
     array[i] = key;
     i++;
    }
   }
  }

  System.out.print("\nAfter array sorting : ");
  printArray(array);
 }

 public static Map<Integer, Integer> generateMap(int[] array) {

  Map<Integer, Integer> myMap = new TreeMap<Integer, Integer>();
  for (int i : array) {
   if (myMap.containsKey(i)) {
    myMap.put(i, myMap.get(i) + 1);
   } else {
    myMap.put(i, 1);
   }
  }
  return myMap;
 }

 public static void printArray(int[] array) {
  for (int i : array) {
   System.out.printf("%d, ", i);
  }
 }
}


OUTPUT:


Before array sorting : 5, 6, 2, 4, 8, 3, 5, 1, 3, 4, 5, 2, 1, 5, 3, 
After array sorting : 1, 2, 3, 4, 5, 6, 8, 1, 2, 3, 4, 5, 3, 5, 5,