Sort array by sorting its smallest sub-array in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class FindIndexOfSubArray {
    private int[] arr;
    final boolean aval;
  
    public FindIndexOfSubArray(int[] arr) {
      this.arr = arr;
      aval = arr[arr.length - 1] - arr[0] < 0;
    }

    public int[] findIndexOfSubArray(){
        int[] size = {arr.length, 0};
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (aval && arr[i] < arr[j] || !aval && arr[i] > arr[j]) {
                    size[0] = Math.min(i, size[0]);
                    size[1] = Math.max(j, size[1]);
                }
            }
        }
        return size[0] < arr.length ? size : new int[2];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import java.util.Arrays;
public class FindIndexOfSubArray {
    private int[] arr;
    public FindIndexOfSubArray(int[] arr) {
        this.arr = arr;
    }

    public int[] findIndexOfSubArray(){
    int [] someArr = new int[arr.length];
        for (int i = 0; i <arr.length ; i++) {
            someArr[i] = arr[i];
        }
        Arrays.sort(someArr);
        if (arr[0] > arr[arr.length-1]) {
            for (int i = 0; i < someArr.length/2; i++) {
                int temp =someArr[i];
                someArr[i] = someArr[someArr.length-1-i];
                someArr[someArr.length-1-i] = temp;
            }
        }
        boolean check = true;
        int m = 0;
        int n = 0;
        for (int i = 0; i <arr.length ; i++) {
            if (arr[i] != someArr[i] && check) {
                m = i;
                check = false;
            }
        }
        check = true;
        for (int i = arr.length-1; i >=0 ; i--) {
            if (arr[i] != someArr[i] && check) {
                n = i;
                check = false;
            }
        }
        System.out.println(m+ "   "+ n);
        return new  int[] {m, n};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

import java.util.Arrays;
import java.util.stream.IntStream;

class FindIndexOfSubArray {
    private int[] arr;

    public FindIndexOfSubArray(int[] arr) {
        this.arr = arr;
    }

    public int[] findIndexOfSubArray(){
        int[] ascending  = Arrays.stream(this.arr).sorted().toArray();
        int[] descending = IntStream.rangeClosed(1, ascending.length).map(i -> ascending[ascending.length-i]).toArray();
        int m = 0; int n = 0;
        int a = 0; int b = 0;

        for (int i = 0; i < this.arr.length; i++) {
            if (this.arr[i] != ascending[i]) {
                n = i; break;
            }
        }

        for (int i = this.arr.length-1; i > 0; i--){
            if (this.arr[i] != descending[i]){
                m = i; break;
            }
        }


        for (int i = 0; i < this.arr.length; i++) {
            if (this.arr[i] != descending[i]) { 
                a = i; break;
            }
        }

        for (int i = this.arr.length-1; i > 0; i--){
            if (this.arr[i] != ascending[i]){
                b = i; break;
            }
        } return Math.abs(n - m) > Math.abs(a - b) ? new int[]{a, b} : new int[]{n, m};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import org.junit.Test;
import static org.junit.Assert.assertTrue;
import org.junit.runners.JUnit4;
import java.util.Arrays;

public class SolutionTest {
     @Test
    public void testSomething1() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 4, 4}).findIndexOfSubArray();
        assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
    }

    @Test
    public void testSomething2() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3}).findIndexOfSubArray();
        assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));
    }

    @Test
    public void testSomething3() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 1, 1}).findIndexOfSubArray();
        assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));

    }

    @Test
    public void testSomething4() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 5, 4}).findIndexOfSubArray();
        assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));

    }

    @Test
    public void testSomething5() {
        int[] actual = new FindIndexOfSubArray(new int[]{6, 5, 4, 1, 2, 3}).findIndexOfSubArray();
        assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
    }

    @Test
    public void testSomething6() {
        int[] actual = new FindIndexOfSubArray(new int[]{9, 2, 32, 123, 3, 2, 2}).findIndexOfSubArray();
        assertTrue("should return [0,4]", Arrays.deepEquals(new Integer[]{0, 4}, new Integer[]{actual[0], actual[1]}));
    }

}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

import org.junit.Test;
import static org.junit.Assert.assertTrue;
import java.util.Arrays;
import java.util.Random;

public class SolutionTest {
    @Test
    public void testSomething1() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 4, 4}).findIndexOfSubArray();
        assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
    }

    @Test
    public void testSomething2() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3}).findIndexOfSubArray();
        assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));
    }

    @Test
    public void testSomething3() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 1, 1}).findIndexOfSubArray();
        assertTrue("should return [0,0]", Arrays.deepEquals(new Integer[]{0, 0}, new Integer[]{actual[0], actual[1]}));

    }

    @Test
    public void testSomething4() {
        int[] actual = new FindIndexOfSubArray(new int[]{1, 2, 3, 6, 5, 4}).findIndexOfSubArray();
        assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));

    }

    @Test
    public void testSomething5() {
        int[] actual = new FindIndexOfSubArray(new int[]{6, 5, 4, 1, 2, 3}).findIndexOfSubArray();
        assertTrue("should return [3,5]", Arrays.deepEquals(new Integer[]{3, 5}, new Integer[]{actual[0], actual[1]}));
    }

    @Test
    public void testSomething6() {
        int[] actual = new FindIndexOfSubArray(new int[]{9, 2, 32, 123, 3, 2, 2}).findIndexOfSubArray();
        assertTrue("should return [0,4]", Arrays.deepEquals(new Integer[]{0, 4}, new Integer[]{actual[0], actual[1]}));
    }


    private int[] generateExpectedResult(int[] arr) {
        int[] clone = Arrays.copyOf(arr, arr.length);
        Arrays.sort(clone);
        int[] mnAsc = findIndex(arr, clone);

        int temp;
        for (int i = 0, j = clone.length - 1; i <= j; i++, j--) {
            temp = clone[i];
            clone[i] = clone[j];
            clone[j] = temp;
        }
        int[] mnDesc = findIndex(arr, clone);
        return mnAsc[1] - mnAsc[0] <= mnDesc[1] - mnDesc[0] ? mnAsc : mnDesc;
    }

    private int[] findIndex(int[] arr, int[] sorted) {
        int m = -1, n = -1;
        for (int i = 0; i < sorted.length; i++) {
            if (arr[i] != sorted[i]) {
                m = i;
                break;
            }
        }
        for (int i = sorted.length - 1; i >= 0; i--) {
            if (arr[i] != sorted[i]) {
                n = i;
                break;
            }
        }

        return new int[]{Math.max(m, 0), Math.max(n, 0)};
    }


    @Test
    public void testSomethingRandom() {
        for (int i = 50; i < 100; i++) {
            int[] data = testDataGenerator(i);
            int[] actual = new FindIndexOfSubArray(data).findIndexOfSubArray();
            int[] expected = generateExpectedResult(data);
            assertTrue(String.format("should return [%d,%d]", expected[0], expected[1]),
                    Arrays.deepEquals(new Integer[]{expected[0], expected[1]}, new Integer[]{actual[0], actual[1]}));
        }
    }

    private int[] testDataGenerator(int size) {
        int[] temp = new int[size];
        int[] prefix = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] suffix = new int[]{101, 102, 103, 104, 105, 106, 107, 108, 109, 110};
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            temp[i] = random.nextInt(100);
        }

        if (random.nextBoolean()) {
            for (int j = 0; j < 10; j++) {
                temp[j] = prefix[j];
            }
        } else {
            for (int j = size - 10, k = 0; j < size && k < 10; j++, k++) {
                temp[j] = suffix[k];
            }
        }
        return temp;
    }
}