## Question

In this task, you should implement both Quicksort and Randomized-Quicksort algorithms.

QUICKSORT(A, p, r)

if p < r

q = PARTITION(A, p, r)

QUICKSORT(A, p, q-1)

QUICKSORT(A, q + 1, r)

PARTITION(A, p, r)

x = A[r]

i = p - 1

for j = p to r - 1

if A[j] ≤ x

i = i + 1

exchange A[i] with A[j]

exchange A[i + 1] with A[r]

return i + 1

RANDOMIZED-QUICKSORT(A, p, r)

if p < r

q = RANDOMIZED-PARTITION(A, p, r)

RANDOMIZED-QUICKSORT(A, p, q - 1)

RANDOMIZED-QUICKSORT(A, q + 1, r)

RANDOMIZED-PARTITION(A, p, r)

i = RANDOM(p, r)

exchange A[r] with A[i]

return PARTITION(A, p, r)

￼Both algorithms are compared with a sortings algoritm with worst case running time of O(n²) eg Insertion-Sort and sorting algorithm with optimal worst case execution time (Θ(n log n)).

The comparison should be done by testing a set of different permutations and input sizes. It is going to be ensured that the worst case permutations are included in the set being tested. The results will be compiled in a table and should moreover be plotted on a graph.

Task 2 - Radix-Sort

In this task, you implement Radix-Sort algorithm. This requires that you implement a stable sorting algorithm like. Counting-Sort to sort the numbers on a digit.

RADIX-SORT(A, d)

for i = 1 to d

use a stable sort to sort array A on digit i

COUNTING-SORT(A, B, k)

let C[0..k] be a new array

for i = 0 to k

C[i] = 0

for j = 1 to A.length

C[A[j]] = C[A[j]] + 1

//C[i] now contains the number of elements equal to i.

for i = 1 to k

C[i] = C[i] + C[i - 1]

//C[i] now contains the number of elements less than or equal to i

for j = A.length downto i

B[C[A[j]]] = A[j]

C[A[j]] = C[A[j]] - 1

The implementation shall be able to share the numbers to be sorted into digits on different ways i.e (that is) it should not be locked into a number system. The lectures discussed the following boundary Θ (b (n + 2r)) for the running time of Radix-Sort, where b is the number of r bits per displayed in the input and K is the selected number of bits per digit. In this thesis b = 32 since we'll sort Integers which normally is four bytes in size. You must allow their implementation can be run with different selected values of r i.e (that is), expand the algorithm so that r can be passed as a parameter.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public class main {/**

* @param args the command line arguments

*/

static long startTime, endTime;

public static void main(String[] args) {

// TODO code application logic here

Scanner sc = new Scanner(System.in);

int r = 0;

while(r < 1 || r > 32){

System.out.print("Enter r : ");

r = sc.nextInt();

}

long max_ = (long) Math.pow(2, r);

// System.out.println(max_);...