java quick sort time limit

Question

This code sometimes works okey, but in some tests its Time Limit. Whats the mistake?

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        QuickSort(A, 0, N - 1);
        for (int j = 0; j < N; j++){
            System.out.print(A[j] + " ");
        }
    }

    public static int Partition(int[] A, int l, int r) {
        int x = (int)(Math.random() * (r - l + 1) + l);
        int Z = A[l];
        for (int i = l; i <= r; i++) {
            if (A[i] < Z) {
                Z = A[i];
            }
        }
        while (A[x] == Z) {
            x = (int)(Math.random() * (r - l + 1) + l);
        }
        int C = l - 1;
        for (int i = l; i <= r; i++) {
            int y = A[i];
            if (y >= A[x]) {
                continue;
            }
            if (y < A[x]) {
                int fake = A[C+1];
                A[C+1] = A[i];
                A[i] = fake;
                ++C;
            }
        }
        return C + 1;
    }
    public static int[] QuickSort(int[] A, int l, int r){
        if (r - l + 1 <= 1) {
            return A;
        }
        if (l < r) {
            int Index = Partition(A, l, r);
            QuickSort(A, l,  Index - 1);
            QuickSort(A, Index, r);
        }
        return A;
    }
}

I tried to check short arrays like {3,2,1} or {3,7,4,2,1,9} its ok, but if its 40 or 100 numbers -> TimeLimit. I create partition algorithm, and take random pivot. After this, I check if random number equal min, change it. I count numbers of iterations and make QuickSort for left side and right side.

Answer 1

When the (sub)array being partitioned has only the same value repeated, like [2, 2, 2], or [5, 5], the following loop will never exit:

    while (A[x] == Z) {
        x = (int)(Math.random() * (r - l + 1) + l);
    }

You have added this code (and the loop to find Z) to avoid that the partitioncut happens at the extreme left, leaving the caller with an empty partition and another partition that has the same size as before.

But there are other ways to ensure that. For instance, you could swap the pivot element into the (otherwise) empty partition.

Today another question on random pivot selection came up. The answer over there may be an inspiration to you.