Sunday, July 19, 2015

Sorting a sub array makes the whole array sorted

Given an unsorted array.
Find the positions of two elements in it, sorting which the whole array will be in sorted order.

Algorithm:
1. Starting from first index, find the position of element which is less than its previous element.
Call it as "start".
If there is no such element, then the array is already in sorted form.
2. Starting from last index, find the position of element which is less than its next element.
Call it as "end".
3. Now find min and max elements in the sub array of [start, end] inclusive.
Call them as min and max.
4. Find the position of first element in [0, start-1], which is greater than "min" ==> index1
5. Find the position of first element in [len-1, end-1], which is less than "max" ==> index2

Now if we sort the sub array formed by [index1, index2], then the whole array will be sorted.

Code:

class MinSortArray {
static public void printPositions(int[] ar) {
int st = -1, end = -1;

for(int i=0; i<ar.length-1; i++) {
if(ar[i+1] < ar[i]) {
st = i+1;
break;
}
}

if(st == -1) {
System.out.println("Array is in sorted form...");
return;
}

for(int i=ar.length-1; i>1; i--) {
if(ar[i-1] > ar[i]) {
end = i-1;
break;
}
}

int min = ar[st], max = ar[end];

for(int i=st; i<=end; i++) {
if(ar[i] < min)
min = ar[i];

if(ar[i] > max)
max = ar[i];
}

int p1 = 0, p2 = 0;

for(int i=0; i<st; i++) {
if(ar[i] > min) {
p1 = i;
break;
}
}

for(int i=ar.length-1; i>end; i--) {
if(ar[i] < max) {
p2 = i;
break;
}
}

System.out.println("min=" + p1 + ", max=" + p2);
}

static public void main(String[] args) {
int[] ar = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60};

printPositions(ar);
}
}

Example:
Lets the input array be: {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}

Step 1:
30 < 25 ==> start=4

Step 2:
32 > 31 ==> end = 6

Step 3:
sub array: {25, 40, 32}
min = 25, max = 40

Step 4:
in [0, 3] sub array, 30 > 25 ==> index1 = 3

Step 5:
in [7, 10] sub array, 35 < 40 ==> index2 = 8

So sorting the sub array [3, 8], makes the whole array sorted.

No comments:

Post a Comment