0

I'm doing a fairly easy HackerRank test which asks the user to write a function which returns the minimum number of swaps needed to sort an unordered vector in ascending order, e.g.

Start: 1, 2, 5, 4, 3

End: 1, 2, 3, 4, 5

Minimum number of swaps: 1

I've written a function which works on 13/14 test cases, but is too slow for the final case.

#include<iostream>
#include<vector>

using namespace std;


int mimumumSwaps(vector<int> arr) {
    int p = 0;  // Represents the (index + 1) of arr, e.g. 1, 2, ..., arr.size() + 1 
    int swaps = 0;

    for (vector<int>::iterator i = arr.begin(); i != arr.end(); ++i) {
        p++;
        if (*i == p)    // Element is in the correct place
            continue;
        else{   // Iterate through the rest of arr until the correct element is found
            for (vector<int>::iterator j = arr.begin() + p - 1; j != arr.end(); ++j) {
                if (*j == p) {  
                    // Swap the elements
                    double temp = *j;
                    *j = *i;
                    *i = temp;

                    swaps++;
                    break;
                }
            }
        }
    }
    return swaps;
}


int main()
{
    vector<int> arr = { 1, 2, 5, 4, 3 };

    cout << mimumumSwaps(arr);

}

How would I speed this up further?

Are there any functions I could import which could speed up processes for me?

Is there a way to do this without actually swapping any elements and simply working out the min. swaps which I imagine would speed up the process time?

Asher Leask
  • 39
  • 7
  • Your solution is `O(n*n)`. As soon as you wrote that double nested loop, you were at risk of a time-out occurring on large data sets. Nothing will make a `O(n*n)` solution faster -- you need to take a different approach that is logarithmic, as your code seems to be a bubble-sort (one of the worst) in disguise. Also -- *I'm doing a fairly easy HackerRank test* -- those questions are designed to have "simple" but naive solutions that will not work for large data sets. Those questions are testing to see if you can come with a non-naive technique. – PaulMcKenzie Dec 22 '19 at 16:57

2 Answers2

1

All permutations can be broken down into cyclic subsets. Find said subsets.

Rotating a subset of K elements by 1 takes K-1 swaps.

Walk array until you find an element out of place. Walk that cycle until it completes. Advance, skipping elements that you've put into a cycle already. Sum (size-1) for each cycle.

To skip, maintain an ordered or unordered set of unexamined items, and fast remove as you examine them.

I think that gives optimal swap count in O(n lg n) or so.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
-1
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>

using namespace std;

int minimumSwaps(vector<int> arr)
{
    int i,c,j,k,l;
    
    j=c=0;
    l=k=arr.size();
       
        while (j<k)
        {
            i=0;
                while (i<l)
                {
                     if (arr[i]!=i+1)
                     {
                         swap(arr[i],arr[arr[i]-1]);
                         c++;
                     }    

                  i++;

                }

         k=k/2;
         j++;

        }

return c;

}

int main()
{
    int n,q;
    cin >> n;
    
    vector<int> arr;
    
    for (int i = 0; i < n; i++)
    {
        cin>>q;
        arr.push_back(q);
    }
    
    int res = minimumSwaps(arr);
    cout << res << "\n";

return 0;
}
gaurav singh
  • 1
  • 1