0

I have sorted the second array and arrange first array with respect to sorted second array in O(n^2) time and my code is something like this-

//c++ code
void sort(int size,int arr1[],int arr2[])
{
    for(int i=0;i<size-1;++i)
    {
        for(int j=i+1;j<size;++j)
        {
            if(arr2[i]>arr2[j])
            {
                swap(arr2[i],arr2[j]);
                swap(arr1[i],arr1[j]);
            }
            //for duplicate data in arr2 
            if(arr2[i]==arr2[j])
            {
                if(arr1[i]>arr1[j])
                {                                   
                    swap(arr1[i],arr1[j]);
                }
            }
        }
    }
}

for example if-

arr1=[2,1,3,9,7,12,5,13]
arr2=[1,3,6,9,2,3,1,3]

after sorting arr2 with respect to arr1

arr1=[2,5,7,1,12,13,3,9]
arr2=[1,1,2,3,3,3,6,9]

the time complexity of this function is O(n^2) now what will be the better approach to sort it?

Akash Kumar
  • 29
  • 1
  • 1
  • 8
  • What language are you using `C` or `C++`? Only tag the language that's relevant. – PaulMcKenzie Oct 12 '21 at 16:31
  • 2
    Do you know how to sort a *single* array with respect to *itself* in a better way? – Eugene Sh. Oct 12 '21 at 16:33
  • Is it required to have two separate arrays or could you change your code to use an array of structures, e.g. `struct foo { int a; int b };` `struct foo arr[] = {{2, 1}, {1, 3}, {3, 6}, 9, 9}, {7, 2}, {12, 3}, {5, 1}, {13, 3}};`. With this change you could use the standard function `qsort`. – Bodo Oct 12 '21 at 16:37
  • Why is `arr1` being adjusted and changed if the goal is to sort `arr2`? – PaulMcKenzie Oct 12 '21 at 16:40
  • Yes, I want to sort arr2 and arrange arr1 with respect to sorted arr2. – Akash Kumar Oct 12 '21 at 16:43
  • Somebody, maybe me, will have the idea to sort indexes and use in the comparison the indexd value. After that we can build the other array based on the sorted indices . . . – A M Oct 12 '21 at 16:46
  • @AkashKumar -- Please see [this answer](https://stackoverflow.com/questions/46382252/sort-array-by-first-item-in-subarray-c/46382976#46382976). The idea is to sort an index, not the actual array(s). – PaulMcKenzie Oct 12 '21 at 16:48

1 Answers1

0

As indicated by this answer, build an index and sort on the index.

Then you can use the index array to repopulate the arrays. Then you can also use std::sort which is O(n log n) instead of the O(n^2) approach you were using:

#include <algorithm>
#include <iostream>
#include <numeric>

int main()
{
    int arr1 [] = {2,1,3,9,7,12,5,13};
    int arr2 [] = {1,3,6,9,2,3,1,3};
    int index[8];
    std::iota(index, index + 8, 0);
    std::sort(std::begin(index), std::end(index), [&](int n1, int n2) { return arr2[n1] < arr2[n2]; });
    for (auto i : index)
      std::cout << arr1[i] << " ";
    std::cout << "\n";
    for (auto i : index)
      std::cout << arr2[i] << " ";
}

Output:

2 5 7 1 12 13 3 9 
1 1 2 3 3 3 6 9
PaulMcKenzie
  • 34,698
  • 4
  • 24
  • 45