Software & Finance





Java - Sorting Algorithm - QuickSort Iterative





 

We often using sorting algorithm to sort numbers and strings. Also we have many sorting algorithms. I have explained here on how quicksort algorithm works in iterative mode.

 

For each time when partition method is called, the pivot is placed at the correct position meaning all the elements to the left are less than the pivot value and all the elements to right are greater than the pivot value.

 

The iteration approach requires stacking of the beg(left), end(right) positions that are used in recursion. I have used the List to store the values and made sure the loop is getting repeated until List is empty. For Partition, we need two arguments - left and right.

 

Click here for Java BubbleSort Algorithm

Click here for Java InsertionSort Algorithm

Click here for Java MergeSort Recursive Algorithm

Click here for Java MergeSort Iterative Algorithm

Click here for Java QuickSort Recursive Algorithm

Click here for Java QuickSort Iterative Algorithm

 

The complete program and test run output are given below:

 

 

Source Code


import java.io.*;

import java.util.*;

import java.lang.*;

 

 

class QuickSort {

 

      public static int Partition(int[] numbers, int left, int right)

    {

        int pivot = numbers[left];

        while (true)

        {

            while (numbers[left] < pivot)

                left++;

 

            while (numbers[right] > pivot)

                right--;

 

            if (left < right)

              {

                int temp = numbers[right];

                numbers[right] = numbers[left];

                numbers[left] = temp;

              }

              else

              {

                    return right;

              }

        }

    }

 

    public static class QuickPosInfo

    {

        public int left;

        public int right;

    };

     

      public static QuickPosInfo info = new QuickPosInfo();

 

      public static void QuickSort_Iterative(int[] numbers, int left, int right)

    {

       

        if(left >= right)

            return; // Invalid index range

 

            LinkedList<QuickPosInfo> list = new LinkedList< QuickPosInfo>();

 

        info.left = left;

        info.right = right;

            list.add(info);

 

        while(true)

        {

            if(list.size() == 0)

                break;

 

                  left = list.get(0).left;

                  right = list.get(0).right;

                  list.remove(0);

 

            int pivot = Partition(numbers, left, right);   

            

            if(pivot > 1)

            {

                info.left = left;

                info.right = pivot - 1;

                list.add(info);

            }

 

            if(pivot + 1 < right)

            {

                info.left = pivot + 1;

                info.right = right;

                list.add(info);

            }

        }

    }

 

    public static void main(String[] args)

    {

        int[] numbers = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };

        int len = 9;

 

            System.out.println();

            System.out.println("QuickSort By Iterative Method");

        QuickSort_Iterative(numbers, 0, len - 1);

            for (int i = 0; i < 9; i++)

                  System.out.println(numbers[i]);

       

    }

}

 

Output


QuickSort By Iterative Method

1

2

3

4

5

6

7

8

9

Press any key to continue . . .