Quicksort is a recursive, average-case O(NlogN) sorting algorithm. The following is some pseudo-code for Quicksort to...

Transcribed Image Text:

Quicksort is a recursive, average-case O(NlogN) sorting algorithm. The following is some pseudo-code for Quicksort to sort an array of integers in non-decreasing order: void quicksort (integer A[], integer p, integer r) begin integer q; if p < r then q = partition (A, p, r) quicksort (A, p, q) quicksort (A, q+1, r) end if end quicksort integer partition (integer A[], integer p, integer q) begin integer pivot := A[p] integer i:= p-1 integer j := q+1 while (true) repeat j = j-1 until (A[j] <= pivot) repeat i :=i+1 until (A[i] >= pivot) if i j then swap (A, i, j) else return j end if end loop end partition void swap (integer A[], integer i, integer j) begin integer temp : = A[i] A[i]:=A[j] A[j] = temp end swap In the provided hw2-quicksort.s file, the swap function and some other starting codes are given. You are expected to modify the code marked with 'TODO' to complete the implementation. You do not need to follow the above pseudo-code exactly. When you test your code, please also try other values besides the array in the given file. Quicksort is a recursive, average-case O(NlogN) sorting algorithm. The following is some pseudo-code for Quicksort to sort an array of integers in non-decreasing order: void quicksort (integer A[], integer p, integer r) begin integer q; if p < r then q = partition (A, p, r) quicksort (A, p, q) quicksort (A, q+1, r) end if end quicksort integer partition (integer A[], integer p, integer q) begin integer pivot := A[p] integer i:= p-1 integer j := q+1 while (true) repeat j = j-1 until (A[j] <= pivot) repeat i :=i+1 until (A[i] >= pivot) if i j then swap (A, i, j) else return j end if end loop end partition void swap (integer A[], integer i, integer j) begin integer temp : = A[i] A[i]:=A[j] A[j] = temp end swap In the provided hw2-quicksort.s file, the swap function and some other starting codes are given. You are expected to modify the code marked with 'TODO' to complete the implementation. You do not need to follow the above pseudo-code exactly. When you test your code, please also try other values besides the array in the given file.

Answer rating: 100% (QA)

Corrected implementation of Quicksort in Python python def quicksortA ... View the full answer