Problem Solving with Algorithms and Data Structures using Kotlin The Interactive Edition

Generate a random list of integers. Show how this list is sorted by the following algorithms:

Consider the following list of integers: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. Show how this list is sorted by the following algorithms:

Consider the following list of integers: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. Show how this list is sorted by the following algorithms:

Consider the list of characters: ["G", "A", "R", "L", "I", "C"]. Show how this list is sorted using the following algorithms:

Devise alternative strategies for choosing the pivot value in a quicksort. For example, pick the middle item. Reimplement the algorithm and then execute it on random data sets. Under what criteria does your new strategy perform better or worse than the strategy from this chapter?

Set up a random experiment to test the difference between a sequential search and a binary search on a list of integers.

Use the binary search functions given in the text (recursive and iterative). Generate a random, ordered list of integers and do a benchmark analysis for each one. What are your results? Can you explain them?

Implement the binary search using recursion without the slice operator. Recall that you will need to pass the list along with the starting and ending index values for the sublist. Generate a random, ordered list of integers and do a benchmark analysis.

Implement quadratic probing as a rehash technique.

Using a random number generator, create a list of 500 integers. Perform a benchmark analysis using some of the sorting algorithms from this chapter. What is the difference in execution speed?

A bubble sort can be modified to “bubble” in both directions. The first pass moves “up” the list, and the second pass moves “down.” This alternating pattern continues until no more passes are necessary. Implement this variation and describe under what circumstances it might be appropriate.

Perform a benchmark analysis for a shell sort, using different increment sets on the same list.

Implement the mergeSort function without using the slice operator.

One way to improve the quicksort is to use an insertion sort on lists that have a short length (call it the “partition limit”). Why does this make sense? Reimplement the quicksort and use it to sort a random list of integers. Perform an analysis using different list sizes for the partition limit.

Implement the median of three method for selecting a pivot value as a modification to quickSort. Run an experiment to compare the two techniques.