Java Program to Implement Quick Sort with Given Complexity Constraint

This is a java program to perform quick sort with complexity constraint of time less than n^2.

Here is the source code of the Java Program to Implement Quick Sort with Given Complexity Constraint. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

```
 
```
```
package com.sanfoundry.combinatorial;
```
```
 
```
```
import java.util.Random;
```
```
 
```

public class QuickSortComplexityConstraint

```
{
```
```
    public static int N = 20;
```

    public static int[] sequence = new int[N];

```
 
```

    public static void QuickSort(int left, int right)

```
    {
```
```
        if (right - left <= 0)
```
```
            return;
```
```
        else
```
```
        {
```
```
            Random rand = new Random();
```

            int pivotIndex = left + rand.nextInt(right - left + 1);

```
            swap(pivotIndex, right);
```

            int pivot = sequence[right];

            int partition = partitionIt(left, right, pivot);

            QuickSort(left, partition - 1);

            QuickSort(partition + 1, right);

```
        }
```
```
    }
```
```
 
```

    public static int partitionIt(int left, int right, long pivot)

```
    {
```
```
        int leftPtr = left - 1;
```
```
        int rightPtr = right;
```
```
        while (true)
```
```
        {
```

            while (sequence[++leftPtr] < pivot)

```
                ;
```

            while (rightPtr > 0 && sequence[--rightPtr] > pivot)

```
                ;
```
```
            if (leftPtr >= rightPtr)
```
```
                break;
```
```
            else
```

                swap(leftPtr, rightPtr);

```
        }
```
```
        swap(leftPtr, right);
```
```
        return leftPtr;
```
```
    }
```
```
 
```

    public static void swap(int dex1, int dex2)

```
    {
```
```
        int temp = sequence[dex1];
```

        sequence[dex1] = sequence[dex2];

```
        sequence[dex2] = temp;
```
```
    }
```
```
 
```

    static void printSequence(int[] sorted_sequence)

```
    {
```

        for (int i = 0; i < sorted_sequence.length; i++)

            System.out.print(sorted_sequence[i] + " ");

```
    }
```
```
 
```

    public static void main(String args[])

```
    {
```
```
        System.out
```

                .println("Sorting of randomly generated numbers using QUICK SORT with complexity less than n^2");

```
        Random random = new Random();
```
```
        for (int i = 0; i < N; i++)
```

            sequence[i] = Math.abs(random.nextInt(100));

        System.out.println("\nOriginal Sequence: ");

```
        printSequence(sequence);
```

        System.out.println("\nSorted Sequence: ");

```
        QuickSort(0, N - 1);
```
```
        printSequence(sequence);
```
```
    }
```
```
}
```

Output:

$ javac QuickSortComplexityConstraint.java
$ java QuickSortComplexityConstraint
 
Sorting of randomly generated numbers using QUICK SORT with complexity less than n^2
 
Original Sequence: 
29 19 67 48 23 99 72 40 23 93 0 79 70 87 43 24 56 67 51 71 
Sorted Sequence: 
0 19 23 23 24 29 40 43 48 51 56 67 67 70 71 72 79 87 93 99

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

« Prev - Java Program to Create the Prufer Code for a Tree

» Next - Java Program to Generate All Possible Combinations of a Given List of Numbers

Related Posts:

Recommended Articles: