6( 10%)Suppose you have an array of a million English vocabulary Strings to sort
ID: 3607060 • Letter: 6
Question
6( 10%)Suppose you have an array of a million English vocabulary Strings to sort, but you happen to know that there are only four different varieties of Strings in it: "Family", "Hero". "Monkey", and Together". You want to sort this vocabulary array to put all the "Family" words first, then all the "Hero", then all the "Monkey" then all the "Together" words. How would you do it? You could use merge sort or Quicksort and get a runtime proportional to N log N, where N is-one million. Carn you do better? Adjust your answer by illustrating how to sort itExplanation / Answer
The following algorithm takes in an array of strings containing only permutations of words Family, Hero, Monkey, and Together and sorts it.
Algorithm Known_sort(array[]):
Declare an integer array Count of size 4.
Initialize all the elements of array Count with 0.
For i = 1 to length of array:
If array[i] == “Family” then, Count[1] = Count[1] + 1
Else If array[i] == “Hero” then, Count[2] = Count[2] + 1
Else If array[i] == “Monkey” then, Count[3] = Count[3] + 1
Else If array[i] == “Together” then, Count[4] = Count[4] + 1
Else, Print(“Invalid String”)
Declare j as int
Set j = 1
For i=1 to length of array:
If Count[j] == 0:
j = j+1
If j==1:
array[i] = “Family”
Else, If j==2:
array[i] = “Hero”
Else, If j==3:
array[i] = “Monkey”
Else:
array[i] = “Together”
Count[j] = Count[j] – 1
The algorithm works by finding the number of times each word appears in the given array and then inserts each word in the given array that number of times in the sorted order.
The loop to find the number of times each word appears in the array takes N time as each element of the array is visited once.
The loop to insert the values in the array in the sorted order takes N time. Therefore, the total running time of the algorithm is as follows:
Running time (known_sort) = N + N
= 2N
= O(N)
It is known that O(N) < O(N log N)
Therefore, the algorithm known_sort is better than using Merge sort or Quick sort which have a running time of N log N
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.