How to find maximum number of groups needed to sort an Array?

Question

Suppose I had an array:

[1, 8, 5, 6, 10, 9, 11, 12];

I want to sort it by ascending order, but find out the maximum groups I would need to sort. In this example, the answer would be:

[1], [8,5,6], [10,9], [11], [12]: so 5

[3, 2, 1] would come out to be 1 because the entire array would need sorting.

I am at a complete loss of how to do this a nudge in the right direction would be greatly appreciated.

Answer 1

Here is the code that works out well with an array of n distinct integers. This is in C.

#include <stdio.h>
//code for the case where each element of the array is distinct 
//and greater than 0
//finding index of the maximum value in array
int maximum(int *a,int n)
{
    int i,max;
    max=0;
    for(i=0;i<n;i++)
    {
        if(a[i]>a[max])
        {
            max=i;
        }
    }
    return max;
}

//finding index of the minimum value in array(excluding zeros)
int minimum(int *a,int n)
{
    int i,min,index;
    min=100000;
    for(i=0;i<n;i++)
    {
        if(a[i]!=0 && a[i]<min)
        {
            min=a[i];
            index=i;
        }
    }
    return index;
}

//checks for the presence of a non-zero element in array
int check(int *a,int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i]!=0)
        return 1;
    }
    return 0;
}

//main function
int main()
{
    int n,j,k,max,min,slices;
    slices=0;
    scanf("%d",&n);
    int a[n];
    for(int j=0;j<n;j++)
    {
        scanf("%d",&a[j]);
    }
    //until all the elements of the array become 0
    //continue iterating to find slices
    while(check(a,n))
    {
        max=maximum(a,n);
        min=minimum(a,n);
        //if index of minimum value is greater than 
        //index of maximum value
        if(max<min)
        {
            slices=slices+1;
            for(j=0;j<n;j++)
            a[j]=0;
        }
        else
        {
            for(j=0;j<=min;j++)
            {
                a[j]=0;
            }
            slices=slices+1;
            if(check(a,n))
            {
                for(j=max;j<n;j++)
                {
                    a[j]=0;
                }
                slices=slices+1;
            }
        }
    }
    printf("slices %d",slices);
    return 0;
}

Answer 2

My solution uses the insertion sort algorithm, which keeps sorted elements on their places and moves unsorted elements towards the beginning of the array until they get in their place. We can use this behavior to detect groups that need to be sorted.

At each iteration, we check whether the current element is greater than or equal to the previous one. If so, we may have encountered a new group. We push the current index to a stack.

If the current element is less than previous, then we're still in the same group. We start to swap this element with previous elements until it gets in place. And at each step we check if we have crossed the boundary of the previous group. If the boundary is crossed, it means that these two groups are actually one group, so we pop the last value from the stack.

Finally, the number of groups equals to the stack size.

Here is the implementation:

public static int countGroups(int[] a) {
    if (a.length < 2) return a.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(0);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack.peek()) stack.pop();
        }
    }
    return stack.size();
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

And here is a JavaScript snippet with some examples:

console.log(countGroups([1, 8, 5, 6, 10, 9, 11, 12]));    //5 - [1], [8, 5, 6], [10, 9], [11], [12]
console.log(countGroups([1, 8, 5, 6, 10, 9, 2, 11, 12])); //4 - [1], [8, 5, 6, 10, 9, 2], [11], [12]
console.log(countGroups([3, 8, 5, 6, 10, 9, 2, 11, 1]));  //1 - [3, 8, 5, 6, 10, 9, 2, 11, 1]
console.log(countGroups([1, 2, 8, 6, 10, 9, 11]));        //5 - [1], [2], [8, 6], [10, 9], [11]
console.log(countGroups([1, 2, 1, 1, 10, 9, 10]));        //4 - [1], [2, 1, 1], [10, 9], [10]

function countGroups(a) {
    if (a.length < 2) return a.length;
    let stack = [0];
    for (let i = 1; i < a.length; i++) {
        if (a[i] >= a[i - 1]) stack.push(i);
        for (let j = i; j > 0 && a[j] < a[j - 1]; j--) {
            swap(a, j, j - 1);
            if (j <= stack[stack.length - 1]) stack.pop();
        }
    }
    return stack.length;
}

function swap(a, i, j) {
   let t = a[i];
   a[i] = a[j];
   a[j] = t;
}

UPDATE: If you don't need to actually sort the array, it seems that the problem can be solved in linear time:

public static int countGroupsLinear(int[] a) {
    Stack<Integer> stack = new Stack<>();
    stack.push(a[0]);
    for (int i = 1; i < a.length; i++) {
        if (a[i] >= stack.peek()) stack.push(a[i]);
        else {
            int last = stack.pop();
            while (stack.size() > 0 && a[i] < stack.peek()) stack.pop();
            stack.push(last);
        }
    }
    return stack.size();
}