Combine QuickSort and Median selection algorithm

Question

I want to modify QuickSort (in Java) so that every time Partition is called, the median of the proportioned array is used as the pivot.

I have a median selection algorithm in Java that returns the kth smallest element, in this case the median. I have tons of quicksort algorithms in java that all work by themselves and sort an array. Unfortunately I can't combine those two in order to achieve the above... Everytime I try it i usually get stackoverflow erros.

Can anybody show me code to see how it can be done?

Thanks

EDIT: For example this is a median selection algorithm that I have tried to use.

public int quickSelect(int[] A, int p, int r, int k) {
    if (p==r) return A[p];
    int q = Partition(A,p,r);
    int len = q-p+1;

    if (k == len) return A[q];
    else if (k<len) return Select(A,p,q-1,k);
    else return Select(A,q+1,r,k-len);
}

public int partition(int[]A, int p, int r) {
    int x = A[r];
    int i = p-1;
    for (int j = p; j<=r-1; j++) {
        if (A[j] <= x) {
            i++;
            swap(A,i,j);
        }
    }
    swap(A,i+1,r);
    return i+1;
}

It works by itself but when I try to call quickSelect through quicksort's partition function to return the pivot to be used, it doesn't work. Obviously I'm doing something wrong but I don't know what. Unfortunately on the Internet I haven't found any algorithm, even in pseudocode, that would combine a median selection with quicksort.

It would be helpful to see the code you're using. Ideally just the relevant bits. — James Montagne, May 15 '12 at 22:22
Anyone? I didn't realize it was so tough... Or maybe I'm not very clear for what I'm looking for? — user1397309, May 17 '12 at 11:55

score 0 · Answer 1 · answered May 15 '12 at 23:14

0

The standard way to get the median is to sort the data. And you want to sort the data by partitioning on the median. This seems very chicken and egg to me.

Could you elaborate on why you want to partition/pivot on the median?

answered May 15 '12 at 23:14

user949300

15,364
7
35
66

I know that I can find the median by sorting the data but that's the whole point, I want to find it without doing that. I want the median to be used as pivot each time the quicksort's partition function is called because the median is the ideal pivot. – user1397309 May 15 '12 at 23:37
@user1397309 You did not answer the question - why would you do that? Are you aware, that pushing the algorithm to be more effective (partitioning by median) by doing excessive work (finding the median) may be slower than (for example) random partitioning? – Frantisek Kossuth May 16 '12 at 11:17
@FrantisekKossuth yes I am aware of what you're saying. I'm experimenting. – user1397309 May 16 '12 at 11:51

score 0 · Answer 2 · answered May 15 '12 at 23:52

0

What you are looking for is the Selection Algorithm. Here's a link with pseudocode.

From the link:

In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list

To find the median you want to find the k=floor((n+1)/2) smallest number in the list where n is the size of the list.

answered May 15 '12 at 23:52

Himadri Choudhury

10,217
6
39
47

Thanks, I know. That's what I'm using (I think). I want to combine this selection algorithm with Quicksort, but I can't do it. – user1397309 May 15 '12 at 23:56

Avi Cohen · Answer 3 · 2012-07-18T06:20:27.557

Note that in PARTITION the pivot is A[r].

public int QUICKSORT2(int[] A, int p, int r) {
    if (p<r) {
        int median=Math.floor((p + r) /2) - p + 1
        int q=SELECT(A, p, r, median)
        q=PARTITION2(A, p, r, q)
        QUICKSORT2(A, p, q-1)
        QUICKSORT2(A, q+1, r)
    }
}

public int PARTITION2(int[]A, int p, int r, int q) {
    int temp = A[r];
    A[r]=A[q];
    A[q]=temp;
    return PARTITION(A, p, r)
}

score 0 · Answer 4 · answered Jan 20 '13 at 11:29

You can use this ...

int Select(int array[],int start, int end,int k){

if(start==end){
    return start;
}

int x=array[end];
int i=start-1;
for(int j=start;j<=end-1;j++){
    if(array[j]<x){
        i++;
        Swap(array+i,array+j);
    }
}
i++;
Swap(array+i,array+end);

if(i==k){
    return i;
}
else if(i>k){
    return Select(array,start,i-1,k);
}
else{
    return Select(array,i+1,end,k);
}

}

Select will partition array on kth smallest element in array;

Combine QuickSort and Median selection algorithm

4 Answers4

Linked

Related