Is there a more efficient form of sorting this array than bubblesort given the problem criteria?

Question

I was practicing some more problems on HackerRank and I ran into this one called "New Year Chaos". Basically the premise is to sort the array and count the switches made. The catch is no number is allowed to make more than 2 switches. BubbleSort passes the first few tests, but times out on the rest. Is there a more efficient array sorting algo that still takes into account the number of switches? I tried mergeSort and quickSort but it's hard to track the switches when dividing the array like that.

Problem prompt: It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment by from at the front of the line to at the back.

Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others. For example, if n = 8 and Person 5 bribes Person 4, the queue will look like this: {1, 2, 3, 5, 4, 6, 7, 8}.

Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state!

public class LineBribing {

    static int[] replace(int[] q, int i, int n) {
        int temp = q[i];
        q[i] = q[n];
        q[n] = temp;
        return q;
    }

    static void minimumBribes(int[] q) {
        int count = 0;
        for (int i = 0; i < q.length - 1; i++) {
            if (q[i] > i + 3 || q[i] < i - 1) {
                System.out.println("Too chaotic");
                return;
            }
            if (q[i] > q[i + 1]) {
                count++;
                replace(q, i, i + 1);
                i = 0;
            }
        }
        System.out.println(count);
    }

    public static void main(String[] args) {
        int[] test = {1, 2, 5, 3, 4, 7, 8, 6};
        int[] test2 = {1, 2, 5, 3, 7, 8, 6, 4};
        minimumBribes(test);
        minimumBribes(test2);

    }
}

Given the input in the main method, the output should be 4 for test 1 (switches: 5, 3 at index = 3 | 5, 4 at index = 4 | 8, 6 at index = q.length - 1 | 7, 6 at index = q.length - 2) and "Too Chaotic" for test 2 (Because 5 is > 2 switches away from its initial position)

Answer 1

I think this problem don't need to sort the array. You only need count the number of person who overtake a person. Note that:

• a person can bribe at most 2 different persons
• a person can bribe who is in the front of him So, you should judge that anyone bribe more than 2 persons first. Then count the number of overtake person.

My Java code like this:

        int ans = 0;
        for (int i = q.length - 1; i >= 0; i--) {
            if (q[i] - (i + 1) > 2) {
                System.out.println("Too chaotic");
                return;
            }
            for (int j = Math.max(0, q[i] - 2); j < i; j++) {
                if (q[j] > q[i]) {
                    ans++;
                }
            }
        }
        System.out.println(ans);