Question

Quick Revision of basic ideas about strings – 695-701.

Do this via strategic questions of the students

Use set 5.1 StringSorts slides 1-16.

Again if the lecturer has a computer in the lectern, it would be helpful to go through some of the code snippets throughout this lecture.

Go through 51DemoKeyIndexed Counting slides 1-19 – preferably by having the students act it out as before in conjunction with slides 17-21 of 5.1 StringSorts.

Try to cover at least LSD and MSD sorts and 3-way radix sort. Slides 22-57 of 5.1 StringSorts.

Could skip section on suffix arrays slides 58-73 of 5.1 StringSorts.

Slides 74-89 are missing.

Discuss Slide 90

Homework Exercises

1. Why are StringSorts stable?
2. Why are StringSorts efficient compared with other types of sorts?
3. Are there times when StringSorts are not efficient? If yes, when and why does this occur?
4. If the answer to 3 is yes, what, if anything, can be done to make the sort more efficient?

Answer 1

1. There are basically two methods of string filtering.
i) .LSD --- This method checks the letters of the keys in the right-to-left sequence. This filter is used when all buttons are equal in length

ii). MSD - This method scans the letters for the left and right sequences, working with the most important character first.

By using (LSD and MSD) String sort algorithm, we maintain a consistent order of records with equal keys. That equal objects retain their relative position after filtering. We can therefore say that the types of cables are stable in data structure and algorithms.

2. complexity

as you can see the space and time complexity of string sort is very less as compared to other sorts . so the speed of the sort will be more. Biggest advantage of string sort is its speed because it is branch-free algorithm. It makes string sort fastest possible sort algorithm for relatively short fixed length keys. The stability of string sort  is also nice feature.

It can handle strings of variable length. It doesn't always need to scan the entire strings (it can decide sooner about the order ). One can use insertion sort to avoid the disadvantages of counting sort.

3. The string type slows down when the word size is large, such as when there is a large key range but a small radix. The reason that large radix can be used all the time is because it becomes a color calculator, with a large memory associated with it. string -radix  sorting is more specialized. You need a specific key that's in lexicographic order. You need one bucket for each possible symbol in the key, and the buckets need to hold a lot of records.

Thank YOu !!