Description of the program: Your program will implement the Quicksort algorithm

Question

Description of the program: Your program will implement the Quicksort algorithm and should work with data supplied for testing using Dr.Racket. (if possible)

Functional Quicksort Algorithm:

quicksort (list)

     if (list ==null) or (list has only one element) return list

     otherwise

          pivot = a random value from list

          append (quicksort of left partition)

               (quicksort of right partition)

NOTE: Remember, while the algorithm uses the name “list” for the argument, “list” is a reserved word.

There are a few details to work out here:

1. How to get a random value?

Save a random value in the list to pivot using the list-ref, random, and length functions.

2. How to get a partition?

We want the left partition to be those values less than the pivot and the right partition to be those values greater-than-or-equal-to the pivot. We can use the filter function to do this.

Explanation / Answer

function quicksort(array) if length(array) > 1 pivot := select any element of array left := first index of array right := last index of array while left right while array[left] pivot right := right - 1 if left right swap array[left] with array[right] left := left + 1 right := right - 1 quicksort(array from first index to right) quicksort(array from left to last index)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---