Java Projects - Second Edition

Non-recursive sorting

To demonstrate that even non-tail recursive methods can be expressed in a non-recursive way, here is the quicksort that way:

 1. public class NonRecursiveQuickSort<E> {
 2. // ... same fields and constructor as in Qsort are      deleted from print ...
 3. 
 4.     private static class StackElement {
 5.         final int begin;
 6.         final int fin;
 7. 
 8.         public StackElement(int begin, int fin) {
 9.             this.begin = begin;
10.             this.fin = fin;
11.         }
12.     }
13. 
14.     public void qsort(Sortable<E> sortable, int          start, int end) {
15.         final var stack = new          LinkedList<StackElement>();
16.         final var partitioner = new Partitioner<E>  (comparator, swapper); 17. stack.add(new StackElement(start, end)); 18. var i = 1; 19. while (!stack.isEmpty()) { 20. var ...