The Full Counting Sort

Collapse Content Show Content

In this challenge you need to print the data that accompanies each integer in a list. In addition, if two strings have the same integers, you need to print the strings in their original order. This means your sorting algorithm will need to be stable, i.e. that the original order is maintained for equal elements.

In the previous challenge, you created a “helper array” that contains information about the starting position of of each element in a sorted array. Can you use this array to help you create a sorted array of the original list?

Hint: You can go through the original array to access the strings. You can then use your helper array to help determine where to place those strings in the sorted array. Be careful about being one off.

Details
You will be given a list that contains both integers and strings. Can you print the strings in order of their accompanying integers? If the integers for two strings are equal, make sure to print them in the order they appeared in the original list.

Input Format
t - the number of test cases. t cases follow:
n - the size of the list ar.
n lines follow, each containing an integer x, and a string, s.

Output Format
Print the strings in their correct order.

Challenge

Print the characters according to the order of their accompanying integers.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Previous Next Node

Comments

mike

Aug 31, 2:51 PM

public static void doStuff(Blob[] ar){
    String[] result = countingSort(ar);
    for(int i=0; i<result.length;i++){
    System.out.print(result[i] + " ");

cont...

    }
    System.out.println();
}

public static String[] countingSort(Blob[] ar){
    int[] counts = new int[100];

    for(int i = 0; i < ar.length; i++){
      counts[ar[i].num]++;
    }
    int[] locations = new int[100];
    locations[0] = counts[0];
    for(int i = 1; i < counts.length ; i++){
      locations[i] = counts[i] + locations[i-1];
    }

    String[] output = new String[ar.length];
    for(int i = 0; i < ar.length; i++){
      int count = counts[ar[i].num];
      int location = locations[ar[i].num];
      int actualLocation = location - count;
      output[actualLocation] = ar[i].string;
      counts[ar[i].num]--;
    }

    return output;
}