Consider an input string TAM of letters ‘A’, ‘M’, and ‘T’. This string, which is given by the user, ends with ‘#’. It should be stored in a table (or array), called TAMUK. The number of each of these letters is unknown. We have a function, called SWAP(TAM,i,j), which places the i th letter in the j
Consider an input string TAM of letters ‘A’, ‘M’, and ‘T’. This string, which
is given by the user, ends with ‘#’. It should be stored in a table (or array), called TAMUK. The
number of each of these letters is unknown. We have a function, called SWAP(TAM,i,j), which
places the i
th letter in the j
th entry of string TAM and the j
th letter in the i
th entry of TAM. Note that
SWAP(TAM,i,j) is defined for all integers i and j between 0 and length(TAM)–1, where
length(TAM) is the number of letters of TAM.
1. Using our algorithmic language, write an
letters in the array TAMUK in a way that all T’s appear first, followed by all A’s, and
followed by all M’s. The algorithm Sort_TAM should have one parameter: The array
TAMUK. Also, your solution is correct only if the following four constraints are satisfied:
- Constraint 1: Each letter (‘A’, ‘M’, or ‘T’) is evaluated only once.
- Constraint 2: The function SWAP(TAM,i,j) is used only when it is necessary.
- Constraint 3: No extra space can be used by the algorithm Sort_TAM. In other words,
only the array TAMUK can be used to sort the ‘A’, ‘M’, or ‘T’.
- Constraint 4: You cannot count the number of each letter ‘A’, ‘M’, or ‘T’.
2. Show that the algorithm Sort_TAM is correct using an informal proof (i.e., discussion).
3. Give a program corresponding to Sort_TAM using your favorite programming language.
Need code in HTML with output and detailed explanation.
The output should be with swapping not sorting (i.e, TTAAMMM not AAMMTT)
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
