sort\' algorithm to sort these words. Simply put, you get the into a single arra

Question

sort' algorithm to sort these words. Simply put, you get the into a single array. Then, you make 26 arrays (one for each letter) and g with "a" will be found - but they will not be in order yet). Then, you send each bucket to a selection sort algorithm to be sorted. you copy each bucket's contents (from 'a" to 'z") back into a single array to generate the final sorted array. This Pron sot easiest to make a has the effect of making 26 shorter arrays, each of which will be faster to Each bucket array must be the same size as the original array, since it's possible that the be no real difference from a standard selection sort.) However, most of the time, you'd expect words to be more evenly distributed across the buckets (with a few being fuller, of learn about the concept of threads and parallel For interest, in a later course the buckets are created, they can begin to be Tarmed out" to individual processor cores in problem much faster on larger datasets. of the

Explanation / Answer

public static void sort(String[] array) {
if (array.length == 0) return; // empty check

// Determine max length
int max = 0;
for (int i = 1; i < array.length; i++) {
// update max length
if (max < array[i].length()) max = array[i].length();
}

// Initialize buckets
int bucketCount = 26; // alphabet
// buckets in maps
HashMap<Character, Vector<String>> buckets = new HashMap<Character, Vector<String>>(bucketCount);
// create the buckets
char a = 'a';
for (int i = 0; i <= bucketCount; i++, a++){
buckets.put(a, new Vector<String>());
}

// assign array values into buckets
for (int i = 0; i < array.length; i++) {
// get first letter of word
String current = array[i];
char letter = current.toLowerCase().charAt(0);
buckets.get(letter).add(array[i]);
}

// Sort buckets and place back into input array
int index = 0; // keeps global array index
for (char key = 'a'; key <= 'z'; key++) {
// retrieve the bucker
Vector<String> bucket = buckets.get(key);

// do an insertion sort on bucket
for (int i = 1; i < bucket.size(); i++){
// i starts as 1, as a list of size 1 is already sorted

// save the value at the index and remove it
String temp = bucket.get(i);
bucket.remove(i);

// move all values one up, until we find the saved value's location
int j;
for(j = i-1; j >= 0 &&
bucket.get(j).compareToIgnoreCase(temp) > 0; j--){
// to "insert", we need to add and remove
bucket.add(j+1, bucket.get(j));
bucket.remove(j);
}
// place the saved value in the proper location
bucket.add(j+1, temp);
}

// pile the current bucket back into array
for (int j = 0; j < bucket.size(); j++) {
array[index++] = bucket.get(j);
}
}
}

This is only a function which you can call in your main method so as to for a complete program.

Note: I used insertion sort instead of selection as in the question selection sort is chosen because it will not affect complexity but its own complexity. So i choose insertion as both these have similar complexity.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.