Question

Hello i need someone to implement in JAVA a radix sort algorithm forsorting strings in ascending order. The input to your algorithm should be a (multi)set S = [S1, S2, . . . , Sn] of strings each of which is of length m over the English alphabet [A…Z, a…z]. The output should be the set sorted in ascending lexicographical order.

Number of strings is >= 100 and number of characters >= 50

i need the answer fast please

Answer 1

Radix sort

Radix sort was developed for sorting large integers. As integers are treated as strings of digits, so it can be called as String sorting algorithm.

Two types of radix sorting:

· MSD radix sort: Sorts from the beginning of strings (most significant digit).

· LSD radix sort: Sorts from the end of strings (least significant digit).

Given, in the question:

Input: Multi set, S = [S1, S2, . . . , Sn] of strings, each of length m

English Alphabet [A..Z, a..z]

Output Expected: String set sorted in ascending lexicographical order.

Solution:

1. Theory:

Generally, Radix sort sorts the elements in the order similar to names of the students sorted in alphabetical order. So, we have 26 radix for all 26 alphabets.

In the first iteration, the names are choosed based on ascending order of the first letter of names. In the second iteration, the names are choosed based on ascending order of the second letter. The process repeats until we get the sorted list of names. The number of iterations is based on the length of the name with the maximum letters.

2. Algortihm:

RadixSort(S)

Input: (Multi) set S = {S1, S2, . . . , Sn} of strings of length m over alphabet [A…Z, a…z].

Output: S in ascending lexicographical order.

(1) for l ← m − 1 to 0 do CountingSort(S,l)

(2) return S

CountingSort(S,l): It processes the strings in S by the symbols at position l using counting sort

It is simple to show that after “i” iterations, the strings are sorted by suffix of length “i”. Hence, they are completed sorted at the end.

3. Java Implementation of Radix sort for” S” string set.

Consider characters from right to left. Sort using “d”th character as the key.

After pass ”i”, strings are sorted by last i characters.

· If two strings differ on sorting key, sorting technique puts in proper order.

· If two strings agree on sorting key, stability puts in proper relative order.

Code:

public class RadixSort

{

public static String[] radixSort(String[] S, int m)

{

int s = 256; int = S.length;

String[] a = new String[N];

for (int d = m-1; d >= 0; d--)

{

int[] count = new int[s+1];

for (int i = 0; i < N; i++)

count[S[i].charAt(d) + 1]++;

for (int r = 0; r < s; r++)

count[r+1] += count[r];

for (int i = 0; i < N; i++)

aux[count[S[i].charAt(d)]++] = S[i];

for (int i = 0; i < N; i++)

S[i] = a[i];

return S;

}

}

     /* Read input from standard input;*/

/* LSD radix Sort is used to sort them;*/

/ * Output is printed to standard output in ascending order.*/

public static void main(String[] args)

{

        String[] S = StdIn.readAllStrings();

int n = S.length;

int m = S[0].length();

for (i = 0; i < n; i++)

        assert S[i].length() == w : "Strings must have fixed length";

radixSort(S, m);

        for (int i = 0; i < n; i++)

        StdOut.println(S[i]);

    }

}