-4

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?

monsteraflam
  • 27
  • 5
  • Implement steps 4,5,6 and come back if you encounter a specific problem. – MrSmith42 Mar 02 '21 at 14:19
  • Is there a publication available online where the *"Drake Sort Algorithm"* is described in more precise terms? As it stands, steps 5 and 6 are not so clear to me. – Janez Kuhar Mar 02 '21 at 14:37
  • I have a feeling that "drake sort" is a fake name for .... something else. – Stephen C Mar 02 '21 at 15:08
  • 1
    @StephenC seems to be a specialization of counting sort for a min...max range. – Surt Mar 02 '21 at 16:27
  • 1
    Yes, I'm sure you are correct. What I am saying is that ... maybe ... "Drake sort" is a fabrication to avoid students from Googling "Counting sort java" for a solution. (Or maybe it is just a misunderstanding on the OP's part.) Either way, when I did a Google for "Drake Sort algorithm", I saw no relevant search results. – Stephen C Mar 02 '21 at 23:38

1 Answers1

2

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]
Nowhere Man
  • 19,170
  • 9
  • 17
  • 42