Provide non-recursive implementation for quick sort inside QuickSort class. Hint

Question

Provide non-recursive implementation for quick sort inside QuickSort class. Hint: A stack can be used to store intermediate results. A stack instance can be created by using java.util.Stack.

Given Code:

public class QuickSort{
  
   // provide non-recursive version of quick sort
   // hint: use stack to stored intermediate results
   // java.util.Stack can be used as stack implementation
   public static <T extends Comparable<T>> void sort(T[] a) {
       throw new UnsupportedOperationException();
   }

   // Partition into a[lo..j-1], a[j], a[j+1..hi]
   private static <T extends Comparable<T>> int partition(T[] a, int lo, int hi) {
       int i = lo, j = hi + 1; // left and right scan indices
       T v = a[lo]; // the pivot

       while (true) { // Scan right, scan left, check for scan complete, and exchange
           while (SortUtils.isLessThan(a[++i], v)) {//++i is evaluated to i+1
               if (i == hi) {
                   break;
               }
           }
           while (SortUtils.isLessThan(v, a[--j])) {//--j is evaluated to j-1
               if (j == lo) {
                   break;
               }
           }
           if (i >= j) {
               break;
           }

           SortUtils.swap(a, i, j);
       }

       SortUtils.swap(a, lo, j); // Put v = a[j] into position
       return j;
   }

}

Explanation / Answer

I hope this code might help you

code:
package project;
import java.util.*;
/* Quick sort code implemented using stack */
public class sorting {
public static void main(String args[])
{
int[] dataset = {14, 33, 28, 1, 16, 61, 35, 99, 55, 67, 5};
System.out.println("dataset: " + Arrays.toString(dataset));
Quicksort(dataset);
System.out.println("Sorted data : " + Arrays.toString(dataset));
}
/* Quick Sort Algorithm */
public static void Quicksort(int[] numbers) {
Stack stack = new Stack();
stack.push(0);
stack.push(numbers.length);
while (!stack.isEmpty())
{
int last = (int) stack.pop();
int start = (int) stack.pop();
if (last - start < 2) {
continue;
}
int mid = start + ((last - start) / 2);
mid = partition(numbers, mid, start, last);
stack.push(mid + 1);
stack.push(last);
stack.push(start);
stack.push(mid);
}
}
/* method to swap 2 values */
private static void swap(int[] array, int i, int j)
{
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/* partitoning the arrays into smaller one's and then comapring and rearranging them to perform the quick sort */
private static int partition(int[] input, int pos, int start, int last)
{
int p = input[pos];
int a = start;
int b = last - 2;
swap(input, pos, last - 1);
while (a < b) {
if (input[a] < p)
{
a++;
}
else if (input[b] >= p)
{
b--;
}
else
{
swap(input, a, b);
}
}
int x = b;
if (input[b] < p)
{
x++;
}
swap(input, last - 1, x);
return x;
}
}

output:
dataset: [14, 33, 28, 1, 16, 61, 35, 99, 55, 67, 5]
Sorted data : [1, 5, 14, 16, 28, 33, 35, 55, 61, 67, 99]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.