negative elements problems of quickSort

U2y 0
Viewed 89

my code works well when elements are all positive.When I added some negative elements to my array,it went wrong.my code could run,but negative parts are totally wrong,and elements had been changed.

here are my codes:

#include<stdio.h>

int median3(int A[],int left,int right);
void Swap(int *a,int *b);
void qSort(int A[],int left,int right);
void quickSort(int A[],int N);

int main(){
    int a[] = {-99,-11,1,3,55,9,12,3,4,90,0,12,32};
    const int length = sizeof(a)/sizeof(a[0]);
    quickSort(a,length);
    for(int i=0;i<length;i++){
        printf("%d ",a[i]);
    }
    return 0 ;
}
/*
median3 is to find the pivot between 3 elements(find the median)
*/
int median3(int A[],int left,int right){
    int center = (left+right)/2;
    if(A[left]>A[center])
        Swap(&A[left],&A[center]);
    if(A[left]>A[right])
        Swap(&A[left],&A[right]);
    if(A[center]>A[right])
        Swap(&A[center],&A[right]);
    Swap(&A[center],&A[right-1]);
    return A[right-1];
}

void Swap(int *a,int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void qSort(int A[],int left,int right){
    int pivot = median3(A,left,right);
    int i = left;
    int j = right-1;
    if(i<j){
        while(1){
            while(A[++i]<pivot){}
            while(A[--j]>pivot){}
            if(i<j){
                Swap(&A[i],&A[j]);
            }else{
                break;
            }
        }
        Swap(&A[i],&A[right-1]);
        qSort(A,left,i-1);
        qSort(A,i+1,right);
    }
}

void quickSort(int A[],int N){
    qSort(A,0,N-1);
}

my codes excuted like this: enter image description here

when there are no negative elements,it works well: enter image description here

c
1 Answers

When I tried out your code, I constantly received segmentation faults. Using an old school technique of sprinkling "printf" statements in the code to provide a printed debug trail, I zeroed in on the swapping occurring within your "median3" function. Really the culprit wasn't so much including negative integers in the list, it had more to do with the location of negative or even small values starting with the first integer in the array.

I found that in those instances, the array index value could go out of bounds to a value of "-1" causing the segmentation faults in my case and your strange behavior you witnessed. With that I added in a guardrail test before attempting to perform a swap as noted in the following revised code snippet.

#include<stdio.h>

int median3(int A[],int left,int right);
void Swap(int *a,int *b);
void q_Sort(int A[],int left,int right);
void quickSort(int A[],int N);

int main()
{
    int a[] = {-99,-11,1,3,55,9,12,3,4,90,0,12,32};
    const int length = sizeof(a)/sizeof(a[0]);
    quickSort(a,length);
    for(int i=0; i<length; i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0 ;
}
/*
median3 is to find the pivot between 3 elements(find the median)
*/
int median3(int A[],int left,int right)
{
    int center = (left+right)/2;
    if(A[left]>A[center])
    {
        printf("median3 left>center swap left: %d, center: %d\n", left, center);
        Swap(&A[left],&A[center]);
    }
    if(A[left]>A[right])
    {
        printf("median3 left>right swap left: %d, right: %d\n", left, right);
        Swap(&A[left],&A[right]);
    }
    if(A[center]>A[right])
    {
        printf("median3 center>right swap center: %d, right: %d\n", center, right);
        Swap(&A[center],&A[right]);
    }
    printf("median3 final swap center: %d, right - 1: %d\n", center, right - 1);
    if (right > 0)      /* Added this for a guardrail */
    {
        Swap(&A[center],&A[right-1]);
    }
    return A[right-1];
}

void Swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void q_Sort(int A[],int left,int right)
{
    int pivot = median3(A,left,right);
    int i = left;
    int j = right-1;

    if (j < 0)
    {
        return;
    }

    if(i<j)
    {
        while(1)
        {
            while(A[++i]<pivot) {}
            while(A[--j]>pivot) {}
            if(i<j)
            {
                Swap(&A[i],&A[j]);
            }
            else
            {
                break;
            }
        }
        Swap(&A[i],&A[right-1]);
        q_Sort(A,left,i-1);
        q_Sort(A,i+1,right);
    }
}

void quickSort(int A[],int N)
{
    q_Sort(A,0,N-1);
}

I left the "printf" statements to allow for testing of other integer combinations, but the "if" test prior to the call of the swap function where possibly the index could go negative avoids that condition. Testing it out with your array of integer values produces a sorted array. FYI, I revised the function name "qsort" to "q_sort" just to possibly avoid a conflict with the standard "qsort" function if ever that function is used in your other programs. You can spot in the output where the index value would have gone negative.

@Una:~/C_Programs/Console/Q_Sort/bin/Release$ ./Q_Sort 
median3 final swap center: 6, right - 1: 11
median3 final swap center: 3, right - 1: 6
median3 final swap center: 1, right - 1: 2
median3 final swap center: 0, right - 1: -1
median3 left>right swap left: 2, right: 3
median3 final swap center: 2, right - 1: 2
median3 left>center swap left: 5, center: 6
median3 left>right swap left: 5, right: 7
median3 center>right swap center: 6, right: 7
median3 final swap center: 6, right - 1: 6
median3 final swap center: 5, right - 1: 4
median3 final swap center: 7, right - 1: 6
median3 left>center swap left: 9, center: 10
median3 left>right swap left: 9, right: 12
median3 center>right swap center: 10, right: 12
median3 final swap center: 10, right - 1: 11
median3 left>right swap left: 9, right: 10
median3 final swap center: 9, right - 1: 9
median3 final swap center: 12, right - 1: 11
-99 -11 0 1 3 3 9 4 12 12 32 90 55

Using a debugger is best, but sometimes inserting "printf" statements into the program can sometimes provide a more vivid output of what might be going wrong.

Give that a try.

NoDakker0
Related