inplace quicksort with random pivot C implementation

fabianod 0
Viewed 51

I need to implement a quicksort algorithm that uses random pivot; I'm working with big matrices, so i can't afford the worst case.

Now, I've found this implementation that works correctly, but it uses as pivot the first element.

I've modified it to fit my scenario (I'm working with Sparse Matrices, and I need to sort the elements by "row index, col index") and this is what I have:

void quicksortSparseMatrix(struct sparsematrix *matrix,int first,int last){
    
    int i, j, pivot, temp_I, temp_J;
    double temp_val;
    

    if(first<last){
        pivot=first;            //(rand() % (last - first + 1)) + first;
        
        i=first;
        j=last;     

        while(i<j){
            while(lessEqual(matrix,i, pivot)&&i<last)
                i++;
            while(greater(matrix,j, pivot))
                j--;
            if(i<j){   
                temp_I = matrix->I[i];
                temp_J = matrix->J[i]; 
                temp_val = matrix->val[i];
                matrix->I[i] = matrix->I[j];
                matrix->J[i] = matrix->J[j];
                matrix->val[i] = matrix->val[j];
                matrix->I[j]=temp_I;
                matrix->J[j]=temp_J;
                matrix->val[j]=temp_val;
            }
        
        }


    temp_I = matrix->I[pivot];
    temp_J = matrix->J[pivot]; 
    temp_val = matrix->val[pivot];
    matrix->I[pivot] = matrix->I[j];
    matrix->J[pivot] = matrix->J[j];
    matrix->val[pivot] = matrix->val[j];
    matrix->I[j]=temp_I;
    matrix->J[j]=temp_J;
    matrix->val[j]=temp_val;
    
    quicksortSparseMatrix(matrix,first,j-1);
    quicksortSparseMatrix(matrix,j+1,last);
    }
}

Now, the problem is that some of the matrices i'm working with are almost sorted and the algorithm runs extremely slow. I want to modify my algorithm to make it use random pivot, but if I apply the change you see commented in the code above pivot=(rand() % (last - first + 1)) + first;, the algorithm does not sort the data correctly.

Can anyone help me figure out how to change the algorithm to use a random pivot and sort the data correctly?

EDIT: this is the struct sparsematrix definition, I don't think you need it, but for completeness...

struct sparsematrix {
    int M, N, nz;   
    int *I, *J;
    double *val;
};
quicksort data-structures sorting c algorithm
1 Answers

Pivot should be a value, not an index. The first comparison should be lessthan (not lessthanorequal), which will also eliminate the need for checking for i < last . After swapping, there should be i++ and j-- . The last two lines should be quicksortSparseMatrix(matrix,first,j); and quicksortSparseMatrix(matrix,i,last); , for this variation of Hoare partition scheme. Example code for array:

void QuickSort(int *a, int lo, int hi)
{
int i, j;
int p, t;
    if(lo >= hi)
        return;
    p = a[lo + 1 + (rand() % (hi - lo))];
    i = lo;
    j = hi;
    while (i <= j){
        while (a[i] < p)i++;
        while (a[j] > p)j--;
            if (i > j)
                break;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
            i++;
            j--;
    }
    QuickSort(a, lo, j);
    QuickSort(a, i, hi);
}

A merge sort on an array of indexes to rows of matrix may be faster: more moves of the indexes, but fewer compares of rows of matrix. A second temp array of indexes will be needed for merge sort.

rcgldr0
Related