How do I write a Drake sort algorithm for sorting an array in Java? [closed]

Tags: , ,



I’m writing a Drake Sort Algorithm in java that will sort a collection of elements. The algorithm is supposed to work like this:

An array for example: { -2, 4, 1, 4 }

  1. Get the max value of the array
  2. Get the min value of the array
  3. Create array with the size (max value – min value + 1) = 7 (4-(-2)+1) = {0,0,0,0,0,0,0}
  4. Go through the array and for each element in the collection count the corresponding index in the array{ 1, 0, 0, 1, 0, 0, 2 }
  5. Create a new array that is the same size as the collection that I wanted to sort (4)
  6. Go trough the array and fill the new collection with the sorted values { -2, 1, 4, 4 }

I’m not very good at writing algorithm and this is what I have so far (not completed I know)

    public int[] sort(int[] unsorted) {

    int maxValue = unsorted.length;
    int minValue = unsorted[0];
    int [] array = new int[maxValue - minValue + 1];

    for (int i = 0; i < array.length; i++) {
        int newArray = array.length;
    }



    return array;

Do you know how I can improve this and actually get it to work?

Answer

The solution may look as follows according to the specified algorithm.

Disclaimer: the array size in Java cannot be greater than maximum size, therefore the length of the frequency array max - min + 1 < Integer.MAX_VALUE

public static int[] sort(int ... unsorted) {
    if (null == unsorted || unsorted.length < 2) {
        return unsorted; // nothing to sort
    }
    // 1, 2. Find min and max
    int max = unsorted[0];
    int min = unsorted[0];

    for (int i = 1; i < unsorted.length; i++) {
        if (min > unsorted[i]) {
            min = unsorted[i];
        } else if (max < unsorted[i]) {
            max = unsorted[i];
        }
    }

    // 3. New array to store frequencies
    int[] freq = new int[max - min + 1];

    // 4. Count frequencies shifting by min elements
    for (int i = 0; i < unsorted.length; i++) {
        freq[unsorted[i] - min] += 1; // shift by min 
    }

    // 5,6.Create and populate sorted array
    int[] sorted = new int[unsorted.length];

    for (int i = 0, ix = 0; i < freq.length; i++) {
        if (freq[i] == 0) {
            continue;  // skip values with 0 frequency
        }
        while (freq[i] > 0) {
            sorted[ix++] = min + i; // populate sorted array
            freq[i]--;
        }
    }

    return sorted;
}

Online demo

System.out.println(Arrays.toString(sort(1, 4, -2, 4, 2, 0, -1, 2)));

Output

[-2, -1, 0, 1, 2, 2, 4, 4]


Source: stackoverflow