lundi 6 mars 2017

Quicksort algorithm with random pivot in the middle of the array

i have to write a quicksort-algorithm with a random pivot so i created the following code:

public void quickSort(int left, int right)
{
    if(a.length == 1)
    {
        System.out.println("Only one element.");
    }
    else
    {
        int l = left;
        int r = right;
        if(right > left)
        {
            Random rand = new Random();
            int num = left + rand.nextInt(right - left);
            int p = a[num];

            int tmp = a[r];
            a[r] = a[num];
            a[num] = tmp;
            num = r;
            r--;


            while(r > l)
            {
                while((l<right)&&(a[l]<=p))
                {
                    l++;
                }
                while((r > left)&&(a[r]>=p))
                {
                    r--;
                }
                if(l < r)
                {
                    tmp = a[l];
                    a[l] = a[r];
                    a[r] = tmp;
                }
            }

            if(a[l] > p) {
                tmp = a[l];
                a[l] = a[num];
                a[num] = tmp;
            }

            quickSort(left,l-1);
            quickSort(l+1,right);
        }

       }
    }

"a" is supposed to be an int-Array. As you can see, as soon as I get my random pivot I swap it with the last element of the array so I don't get any problems with the algorithm, but I wonder if there is a possibility to let the pivot stay at it's random position and sort it without problems, nevertheless. Thx in advance.




Aucun commentaire:

Enregistrer un commentaire