Sort an array according to the order defined by another array - GeeksforGeeks


Given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order.
Input: A1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8}
       A2[] = {2, 1, 8, 3}
Output: A1[] = {2, 2, 1, 1, 8, 8, 3, 5, 6, 7, 9}
The code should handle all cases like number of elements in A2[] may be more or less compared to A1[]. A2[] may have some elements which may not be there in A1[] and vice versa is also possible.

https://shawnlincoding.wordpress.com/2015/04/13/sort-array-given-order/
    public void sortOrder(int[] array, int[] order){
        if(array == null || order == null){
            throw new IllegalArgumentException();
        }
        if(array.length == 0 && order.length == 0){
            return;
        }
        if(array.length != order.length){
            return;
        }
         
        int N = array.length;
        for(int i = 0; i < N; i++){
            while(i != order[i]){
                swap(array, i, order[i]);
                swap(order, i, order[i]);
            }
        }
    }
     
    private void swap(int[] num, int i, int j){
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }



Method 1 (Using Sorting and Binary Search)
Let size of A1[] be m and size of A2[] be n.
1) Create a temporary array temp of size m and copy contents of A1[] to it.
2) Create another array visited[] and initialize all entries in it as false. visited[] is used to mark those elements in temp[] which are copied to A1[].
3) Sort temp[]
4) Initialize the output index ind as 0.
5) Do following for every element of A2[i] in A2[]
…..a) Binary search for all occurrences of A2[i] in temp[], if present then copy all occurrences to A1[ind] and increment ind. Also mark the copied elements visited[]
6) Copy all unvisited elements from temp[] to A1[].
Time complexity: The steps 1 and 2 require O(m) time. Step 3 requires O(mLogm) time. Step 5 requires O(nLogm) time. Therefore overall time complexity is O(m + nLogm).
/* A Binary Search based function to find index of FIRST occurrence
  of x in arr[].  If x is not present, then it returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
    if (high >= low)
    {
        int mid = low + (high-low)/2;  /* (low + high)/2; */
        if ((mid == 0 || x > arr[mid-1]) && arr[mid] == x)
            return mid;
        if (x > arr[mid])
            return first(arr, (mid + 1), high, x, n);
        return first(arr, low, (mid -1), x, n);
    }
    return -1;
}
// Sort A1[0..m-1] according to the order defined by A2[0..n-1].
void sortAccording(int A1[], int A2[], int m, int n)
{
    // The temp array is used to store a copy of A1[] and visited[]
    // is used mark the visited elements in temp[].
    int temp[m], visited[m];
    for (int i=0; i<m; i++)
    {
        temp[i] = A1[i];
        visited[i] = 0;
    }
    // Sort elements in temp
    sort(temp, temp + m);
    int ind = 0;  // for index of output which is sorted A1[]
    // Consider all elements of A2[], find them in temp[]
    // and copy to A1[] in order.
    for (int i=0; i<n; i++)
    {
        // Find index of the first occurrence of A2[i] in temp
        int f = first(temp, 0, m-1, A2[i], m);
        // If not present, no need to proceed
        if (f == -1) continue;
        // Copy all occurrences of A2[i] to A1[]
        for (int j = f; (j<m && temp[j]==A2[i]); j++)
        {
            A1[ind++] = temp[j];
            visited[j] = 1;
        }
    }
    // Now copy all items of temp[] which are not present in A2[]
    for (int i=0; i<m; i++)
        if (visited[i] == 0)
            A1[ind++] = temp[i];
}
Method 3 (Use Hashing)
1. Loop through A1[], store the count of every number in a HashMap (key: number, value: count of number) .
2. Loop through A2[], check if it is present in HashMap, if so, put in output array that many times and remove the number from HashMap.
3. Sort the rest of the numbers present in HashMap and put in output array.

http://www.techiedelight.com/custom-sort-sort-elements-array-order-elements-defined-second-array/
The idea is to count frequency of each element of first array and store it in a map. Now for each element of second array, we check if the element is present in the map or not. If it is present in the map, then we print the element n number of times where n is the frequency of that element in first array. We also remove that element from the map so that we are only left with elements that are only present in the first array (but not present in the second array). In order to append them in the end, they need to be sorted.


    Note that if we use std::map, we have O(log n) insertion, retrieval time but keys are already ordered, so no need to sort. If we use std::unordered_map, we have O(1) insertion, retrieval time but its keys are unordered, so we need to sort the keys..
    void customSort(int arr1[], int arr2[], int m, int n)
    {
        // map to store frequency of each element of first array
        unordered_map<int, int> freq;

        // freq frequency of each element of first array and
        // store it in a map.
        for (int i = 0; i < m; i++)
            freq[arr1[i]]++;

        // Note that once we have the frequencies of all elements of
        // first array, we can overwrite elements of first array
       
        int index = 0;
        // do for every element of second array
        for (int i = 0; i < n; i++)
        {
            // If current element is present in the map, print it n times
            // where n is the frequency of that element in first array
            while (freq[arr2[i]])
            {
                arr1[index++] = arr2[i];
                freq[arr2[i]]--;
            }
            // erase the element from map
            freq.erase(arr2[i]);
        }

        // Now we are only left with elements that are only present
        // in the first array but not present in the second array
        // We need to sort the remaining elements present in the map
        // Note - If use std::map, keys already sorted
        int i = index;
        for (auto it = freq.begin(); it != freq.end(); ++it)
            while (it->second--)
                arr1[index++] = (it->first);

        // sort the remaining elements
        sort(arr1 + i, arr1 + index);
    }
    .Method 2 (Using Self-Balancing Binary Search Tree)
    We can also use a self balancing BST like AVL TreeRed Black Tree, etc. Following are detailed steps.
    1) Create a self balancing BST of all elements in A1[]. In every node of BST, also keep track of count of occurrences of the key and a bool field visited which is initialized as false for all nodes.
    2) Initialize the output index ind as 0.
    3) Do following for every element of A2[i] in A2[]
    …..a) Search for A2[i] in the BST, if present then copy all occurrences to A1[ind] and increment ind. Also mark the copied elements visited in the BST node.
    4) Do an inorder traversal of BST and copy all unvisited keys to A1[].
    http://algorithms.tutorialhorizon.com/sort-an-given-array-in-the-order-defined-by-another-array/
    public int [] SortAndSearch(int [] arrA, int [] arrB){
      //create an Aux array and copy all the elements of arrA
      // create another boolean array, visited[] of size arrA[]
      // Initialize visited[] = false
      // Sort the Aux array using Merge sort.
      // Navigate through the arrB, taking one element at a time, say x
      //  1. perform binary search of x on Aux array and find the first occurrence of x
      //  2. if x is found, copy it to arrA, make visited[] = true
      //  3. Do linear navigation on Aux array till you find x, copy all these to arrA and mark visited[] = true
      // When arrB is over, copy rest of the elements from Aux to arrA.

      int oIndex = -1;
      boolean [] visited = new boolean [arrA.length];
      for(int i=0;i<visited.length;i++){
        visited[i] = false;
      }
      int [] Aux = new int[arrA.length];
      for(int i=0;i<arrA.length;i++){
        Aux[i] = arrA[i];
      }
      System.out.println("Original Array : ");
      displayArray(arrA);
      System.out.println("\nDefined Array : ");
      displayArray(arrB);
      MergeSort m = new MergeSort(Aux);
      Aux = m.mergeSorting();
      for(int i=0;i<arrB.length;i++){
        int x = arrB[i];
        int index = findFirstOccurrence(Aux, x, 0, Aux.length-1);
        if(index>=0){
          arrA[++oIndex]=Aux[index];
          visited[index] = true;
          //oIndex++;
          while(Aux[++index]==x){
            arrA[++oIndex]=Aux[index];
            visited[index] = true;
          }
        }
      }
      for(int i=0;i<Aux.length;i++){
        if(visited[i]==false){
          arrA[++oIndex] = Aux[i];
        }
      }
      return arrA;
    }

    public int findFirstOccurrence(int [] arrA, int x, int start, int end){
      if(end>=start){
        int mid = (start+end)/2;
        if((mid==0||(arrA[mid-1]<x)) && arrA[mid]==x){
          return mid;
        }else if(arrA[mid]<x){
          return findFirstOccurrence(arrA, x, mid+1, end);
        }else{
          return findFirstOccurrence(arrA, x, start, mid-1);

        }
      }else return -1;
    }

    public int [] usingHashing(int [] arrA, int [] arrB){
      //Insert all the elements of arrA in hash Table,
      //Element as key and its count as its value
      //Navigate through arrB, check element's presence in Hash table
      //if it is present then takes its value (count) and insert into arrA.
      //Once arrB is completed, take rest of the elements from Hash table
      // Sort Them and insert into arrB.
      int resIndex = -1;
      Hashtable<Integer, Integer> h = new Hashtable<>();
      for(int i=0;i<arrA.length;i++){
        if(h.containsKey(arrA[i])){
          int count = h.get(arrA[i]);
          count++;
          h.put(arrA[i], count);
        }else{
          h.put(arrA[i], 1);
        }
      }
      for(int i=0;i<arrB.length;i++){
        if(h.containsKey(arrB[i])){
          int count  = h.get(arrB[i]);
          while(count>0){
            arrA[++resIndex] = arrB[i];
            count--;
          }
          h.remove(arrB[i]);
        }
      }
      ArrayList<Integer> al = new ArrayList<Integer>();
      Set<Integer> keys = h.keySet();
      for(Integer x:keys){
        al.add(x);
      }
      Collections.sort(al);
      Iterator<Integer> it = al.iterator();
      while(it.hasNext()){
        arrA[++resIndex] = it.next();
      }
      return arrA;
    }

    Method 4 (By Writing a Customized Compare Method)
    http://www.techiedelight.com/custom-sort-sort-elements-array-order-elements-defined-second-array/
    We can also write a custom compare method to solve this problem. Let the two element to be compared are x and y. Then
    1. If both x and y are present in the second array, then the element with lower index in the second array should come first.
       
    2. If only one of x or y is present in the second array, then the element which is present in the second array should come first.
       
    3. If both elements are not present in second array, then the default ordering will be considered.
    class CustomComparator implements Comparator<Integer>
    {
        Map<Integer, Integer> map;
        public CustomComparator(Map<Integer, Integer> map)
        {
            this.map = map;
        }
     
        public int compare(Integer x, Integer y)
        {
            if (map.containsKey(x) && map.containsKey(y))
                return map.get(x) - map.get(y);
            else if (map.containsKey(y))
                return 1;
            else if (map.containsKey(x))
                return -1;
            else
                return x - y;
        }
    }
            // Wrapper class used
            Integer[] arr1 = { 5, 8, 9, 3, 5, 7, 1, 3, 4, 9, 3, 5, 1, 8, 4 };
            Integer[] arr2 = { 3, 5, 7, 2 };

            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            for (int i = 0; i < arr2.length; i++)
                map.put(arr2[i], i);
         
            // Arrays.sort method doesn't work with primitive array
            // when used with user defined comparator 
            Arrays.sort(arr1, new CustomComparator(map));


    int search(int key)
    {
        int i=0, idx = 0;
        for (i=0; i<size; i++)
            if (A2[i] == key)
                return i;
        return -1;
    }
    // A custom comapre method to compare elements of A1[] according
    // to the order defined by A2[].
    int compareByA2(const void * a, const void * b)
    {
        int idx1 = search(*(int*)a);
        int idx2 = search(*(int*)b);
        if (idx1 != -1 && idx2 != -1)
            return idx1 - idx2;
        else if(idx1 != -1)
            return -1;
        else if(idx2 != -1)
            return 1;
        else
            return ( *(int*)a - *(int*)b );
    }
    // This method mainly uses qsort to sort A1[] according to A2[]
    void sortA1ByA2(int A1[], int size1)
    {
        qsort(A1, size1, sizeof (int), compareByA2);
    }
    according to the order defined by another array - GeeksforGeeks

    Labels

    LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

    Popular Posts