Sorting an array in which multiple succeeding index number form one entry which should stay together

Question

I have an array of over 1 million in length in which 3 succeeding indexes are 1 data-entry. The data-set would look something like this where 2.0 and 1.0 are the starting point of a data-entry the array:

double[] dataEntries = {2.0, 2.2, 2.1, 1.0, 1.2, 1.1, ...};

Now I want to sort them but I have to keep them as entries together. I thought about swapping places like bubble-sort, but that has as complexity of O(n^2). I also thought about Array.sort() but this does only works with an array without grouped indexes. I could use %3 and get all the starting points of each data-set, then apply Array.sort() on this, but I have no idea if I am guaranteed to build back the relations correctly if I were to try to build back the relationships of the 3 succeeding indexes afterwards.

The result of the sorted dataEntries above:

sortedDataEntries = {1.0, 1.2, 1.1, 2.0, 2.2, 2.1, ...};

I hope someone knows a good way to do this.

Answer 1

The safest and simplest way to do this is to convert the array of doubles to a List<SomeClass>, where SomeClass is a class that holds 3 doubles and also implements Comparable. You can then sort however you like, including using built-in sorting support, and then convert back to an array of doubles at the end.

Answer 2

Not considering the performance into note, O(n^2). Assuming the array length is 3*n

 for(int i = 0;i<length_of_array-3;i+=3){
   for(int j = i+3; j<length_of_array-3;j+=3){
      if(arr[i] > arr[j]{
        swap(i,j);
    }
   }

you swap method would do

 swap(int i, int j){
  for(int k=i;k<i+3;k++,j++){
     double temp = arr[k]; 
     arr[k]=arr[j];
     arr[j]=temp;
   }
  }   

Answer 3

Here you go with complexity O(n*log(n)).

I just take each third element into new array and when sorting it, I remember the position it had. Then based on changed position of grouped array I compose a new one. You can see that in last method "merge" I only need position array and the original array, the "grouped" one is no longer needed.

import java.util.Arrays;

public class JavaApplication39 {

    public static void main(String[] args) {
        double[] dataEntries = {2.0, 2.2, 2.1, 1.0, 1.2, 1.1, 7.0,7.1,7.5};
        double[] dataGrouped = new double[dataEntries.length/3];
        int[] positions = new int[dataGrouped.length];

        int j=0;
        for (int i = 0; i < dataEntries.length; i+=3) {
            dataGrouped[j] = dataEntries[i];
            positions[j] = j;
            j++;                    
        }
        quickSort(dataGrouped,positions,0,dataGrouped.length-1);
        double[] merged = merge(dataEntries,positions);
        System.out.println(Arrays.toString(merged));
    }

    private static double[] merge(double[] dataEntries,int[] positions){
        double[] toReturn = new double[dataEntries.length];
        for (int i = 0; i < positions.length; i++) {
            toReturn[i*3] = dataEntries[positions[i]*3];
            toReturn[i*3+1] = dataEntries[positions[i]*3+1];
            toReturn[i*3+2] = dataEntries[positions[i]*3+2];
        }
        return toReturn;
    }

    private static void quickSort(double[] array, int[] positions, int lowerIndex, int higherIndex) {

        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number, I am taking pivot as middle index number
        double pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {
            /**
             * In each iteration, we will identify a number from left side which
             * is greater then the pivot value, and also we will identify a number
             * from right side which is less then the pivot value. Once the search
             * is done, then we exchange both numbers.
             */
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(array,positions, i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(array,positions, lowerIndex, j);
        if (i < higherIndex)
            quickSort(array,positions, i, higherIndex);
    }

    private static void exchangeNumbers(double[] array, int[] positions, int i, int j) {
        double temp = array[i];
        array[i] = array[j];
        array[j] = temp;

        int postemp = positions[i];
        positions[i] = positions[j];
        positions[j] = postemp;
    }
}

Output is :

[1.0, 1.2, 1.1, 2.0, 2.2, 2.1, 7.0, 7.1, 7.5]