Question

Convert the following pseudocode to Java. Use the same variable names as those in the pseudocode. You may assume that the incoming array contains int values and that a swap method exists elsewhere. The variables low and high represent indices in the array. In a comment before the sort method, list which sorting algorithm is used here and what its runtime complexity is in Big-O notation. This is the only comment required for this code.

SUBROUTINE sort(ARRAY a[0..n], low, high)
    IF (low < high)
        pivot = division(a, low, high)
        sort(a, low, pivot)
        sort(a, pivot + 1, high)
    END-IF
RETURN

SUBROUTINE division(ARRAY a[0..n], low, high)
    pivot = a[low]
    wall = low
    FOR (i = low + 1 .. high)
        IF (a[i] < pivot) 
            swap(a, i, wall)
            wall = wall + 1
        END-IF
    END-FOR
    swap(a, low, wall)
RETURN wall

Answer 1

int division(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
if (arr[j] < pivot)
{
i++;
  
swap(arr[i],arr[j]);
}
}
       swap (arr[i+1],arr[high]);
return i+1;
}
  
/* Here we use QUICK SORT ALGORITHM
       it has a Big O notation of O(log n)
   */
void sort(int arr[], int low, int high)
{
if (low < high)
{
int pivot = division(arr, low, high);
sort(arr, low, pivot-1);
sort(arr, pivot+1, high);
}
}