Sorting Two Corresponding Arrays

Sorting two corresponding arrays

Rather than sort the arrays, sort the indices. I.e., you have

int arr[5]={4,1,3,6,2}
string arr1[5]={"a1","b1","c1","d1","e1"};

and you make

int indices[5]={0,1,2,3,4};

now you make a sort indices comparator that looks like this (just and idea, you'll probably have to fix it a little)

class sort_indices
{
   private:
     int* mparr;
   public:
     sort_indices(int* parr) : mparr(parr) {}
     bool operator()(int i, int j) const { return mparr[i]<mparr[j]; }
}

now you can use the stl sort

std::sort(indices, indices+5, sort_indices(arr));

when you're done, the indices array will be such that arr[indices[0]] is the first element. and likewise arr1[indices[0]] is the corresponding pair.

This is also a very useful trick when you're trying to sort a large data object, you don't need to move the data around at every swap, just the indices.

How to sort one array and get corresponding second array in C++?

Create a single array (or vector) of std::pair objects, where first is from the first array and second from the second. Then just use std::sort with a custom comparator function that uses only second from the pair for comparison. Iterate over the sorted array (or vector) and split up into the original arrays.

Note: If the values in each array are tightly coupled then consider putting them in a structure or class instead of using two (or more) distinct arrays.

How to sort two arrays with one being sorted based on the sorting of the other?

Pair Class could do the trick here.

import java.util.*;
public class Main
{
    static class Pair implements Comparable<Pair>
    {
        int a1;
        int a2;
        Pair (int a1, int a2) //constructor 
        {
            this.a1 = a1;
            this.a2 = a2;
        }
        public int compareTo(Pair other) //making it only compare a2 values
        {
            return this.a2 - other.a2;
        }
    }
    public static void main(String[] args) 
    {
        int[] A1 = {1,2,3,4,5,6,7,8,9,10};
        int[] A2 = {1,2,3,0,2,1,1,0,0,0};
        Pair[] pairs = new Pair[A1.length];
        for (int i = 0; i < pairs.length; i++)
        {
            pairs[i] = new Pair(A1[i], A2[i]);
        }
        Arrays.sort(pairs);
        //printing values 
        for (int i = 0; i < A1.length; i++)
        {
            System.out.print(pairs[i].a1 + " ");
        }
        System.out.println();
        for (int i = 0; i < A2.length; i++)
        {
            System.out.print(pairs[i].a2 + " ");
        }
    }
}

By making a Pair class that holds 2 variables a1 and a2, you can override the compareTo method to only compare the a2 value, so that when Arrays.sort is called, the pairs in the Pair array will be swapped only according to the a2 values. You can then access the values in the pairs and print them out. This will produce your desired output.

How to sort multiple arrays based on one and print them out

Using the techniques used in this answer, you can create an array of indices, and sort the index array based on the criteria you're interested in. Then when referencing the data in a sorted manner, you use the index array.

#include <vector>
//...
std::vector<int> index_array;
int main()
{
    for (int i = 0; i < number_of_items; ++i)
        index_array.push_back(i);
//...
    SelectionSort(city, size)
}

void SelectionSort(string city[], int size) 
{
    int i;
    int j;
    int indexSmallest;
    string temp;

    for (i = 0; i < size; ++i)
    {
        indexSmallest = i;
        for (j = i + 1; j < size; ++j)
        {
            if (city[index_array[j]] < city[index_array[indexSmallest]])
            {
                indexSmallest = j;
            }
        }

        temp = index_array[i];
        index_array[i] = index_array[indexSmallest];
        index_array[indexSmallest] = temp;
    }
}

Then when accessing the arrays, use the array of indices:

for (int i = 0; i < size; ++i)
   std::cout << city[index_array[i]] << "\n" << names[index_array[i]] << "\n\n";

How to sort two lists (which reference each other) in the exact same way

One classic approach to this problem is to use the "decorate, sort, undecorate" idiom, which is especially simple using python's built-in zip function:

>>> list1 = [3,2,4,1, 1]
>>> list2 = ['three', 'two', 'four', 'one', 'one2']
>>> list1, list2 = zip(*sorted(zip(list1, list2)))
>>> list1
(1, 1, 2, 3, 4)
>>> list2 
('one', 'one2', 'two', 'three', 'four')

These of course are no longer lists, but that's easily remedied, if it matters:

>>> list1, list2 = (list(t) for t in zip(*sorted(zip(list1, list2))))
>>> list1
[1, 1, 2, 3, 4]
>>> list2
['one', 'one2', 'two', 'three', 'four']

It's worth noting that the above may sacrifice speed for terseness; the in-place version, which takes up 3 lines, is a tad faster on my machine for small lists:

>>> %timeit zip(*sorted(zip(list1, list2)))
100000 loops, best of 3: 3.3 us per loop
>>> %timeit tups = zip(list1, list2); tups.sort(); zip(*tups)
100000 loops, best of 3: 2.84 us per loop

On the other hand, for larger lists, the one-line version could be faster:

>>> %timeit zip(*sorted(zip(list1, list2)))
100 loops, best of 3: 8.09 ms per loop
>>> %timeit tups = zip(list1, list2); tups.sort(); zip(*tups)
100 loops, best of 3: 8.51 ms per loop

As Quantum7 points out, JSF's suggestion is a bit faster still, but it will probably only ever be a little bit faster, because Python uses the very same DSU idiom internally for all key-based sorts. It's just happening a little closer to the bare metal. (This shows just how well optimized the zip routines are!)

I think the zip-based approach is more flexible and is a little more readable, so I prefer it.

---

Note that when elements of list1 are equal, this approach will end up comparing elements of list2. If elements of list2 don't support comparison, or don't produce a boolean when compared (for example, if list2 is a list of NumPy arrays), this will fail, and if elements of list2 are very expensive to compare, it might be better to avoid comparison anyway.

In that case, you can sort indices as suggested in jfs's answer, or you can give the sort a key function that avoids comparing elements of list2:

result1, result2 = zip(*sorted(zip(list1, list2), key=lambda x: x[0]))

Also, the use of zip(*...) as a transpose fails when the input is empty. If your inputs might be empty, you will have to handle that case separately.

Parallel sort two arrays

If you want to use qsort(), you should use an array of structs that contain both the word and the count. You can then pass your array to qsort() with a custom comparison function:

struct wc_s {
  char *word;
  int count;
};

int cmp_words (const void *p1, const void *p2)
{
   const struct wc_s *s1 = p1;
   const struct wc_s *s2 = p2;
   return strcmp (s1->word, s2->word);
}

int cmp_counts (const void *p1, const void *p2)
{
   const struct wc_s *s1 = p1;
   const struct wc_s *s2 = p2;
   return s2->count - s1->count;
}

...
struct wc_s *wc_list = malloc (MAX * sizeof *wc_list);
...
qsort (wc_list, MAX, sizeof *wc_list, cmp_counts);

If qsort() was guaranteed to perform a stable sort (i.e. two elements that compare the same retain their original order), you could solve your problem by first sorting by word, and then sorting by count. Unfortunately, the resulting order of two equal elements is unspecified.

What you could do is sort the array by count, and then go through the array to find sub-arrays with the same counts, and sort those individually:

int start = 0;
int length;
while (start < MAX) {
  for (length = 1; start+length < MAX; length++) {
    if (wc_list[start].count != wc_list[start+length].count)
      break;
  }
  qsort (wc_list+start, length, sizeof *wc_list, cmp_words);
  start += length;
}

Sort two arrays the same way

You can sort the existing arrays, or reorganize the data.

Method 1:
To use the existing arrays, you can combine, sort, and separate them:
(Assuming equal length arrays)

var names = ["Bob","Tom","Larry"];
var ages =  ["10", "20", "30"];

//1) combine the arrays:
var list = [];
for (var j = 0; j < names.length; j++) 
    list.push({'name': names[j], 'age': ages[j]});

//2) sort:
list.sort(function(a, b) {
    return ((a.name < b.name) ? -1 : ((a.name == b.name) ? 0 : 1));
    //Sort could be modified to, for example, sort on the age 
    // if the name is the same.
});

//3) separate them back out:
for (var k = 0; k < list.length; k++) {
    names[k] = list[k].name;
    ages[k] = list[k].age;
}

This has the advantage of not relying on string parsing techniques, and could be used on any number of arrays that need to be sorted together.

Method 2: Or you can reorganize the data a bit, and just sort a collection of objects:

var list = [
    {name: "Bob", age: 10}, 
    {name: "Tom", age: 20},
    {name: "Larry", age: 30}
    ];

list.sort(function(a, b) {
    return ((a.name < b.name) ? -1 : ((a.name == b.name) ? 0 : 1));
});

for (var i = 0; i<list.length; i++) {
    alert(list[i].name + ", " + list[i].age);
}
​

For the comparisons,-1 means lower index, 0 means equal, and 1 means higher index. And it is worth noting that sort() actually changes the underlying array.

Also worth noting, method 2 is more efficient as you do not have to loop through the entire list twice in addition to the sort.

http://jsfiddle.net/ghBn7/38/

---

Related Topics