CODEWITHSUNDEEP
calgorithm
topcoder
topcoder

Reputation: 59

Quick sort algorithm with central pivot element not working

I'm a newbie C-programmer and have been working on this algorithm for a long time. I'm very frustrated because I have not been able to get a correct non-decreasing sorted sequence.

All help is welcome. Thanks in advance.

Here is my code:

#include <stdio.h>
#include <conio.h>

int swap(short* a, short fst , short scnd){
    short temp  = a[fst] ;
    a[fst]          = a[scnd] ;
    a[scnd]         = temp ;

    return 0 ;
}

int div(short* a ,short p,short middle ,short r){
    while( p < r ){
        if( p < middle ){       
            if( a[p]      > a[middle] ){
                swap(a ,p ,middle) ; 
            }
            p++ ; 
        }
        if( middle < r ){
            if( a[middle] > a[r] ){
                swap(a ,middle , r) ;      
            }         
            r-- ;
        }
    }

    return 0 ;
}

int fast(short* a , short p , short r){
    if( p < r){
        int middle = (p+r)/2 ;
        div(a, p, middle ,r ) ;
        fast(a, p ,middle-1 ) ;
        fast(a ,middle+1 ,r);
    }
}

int main(){
    short n ,i ;
    scanf("%hd",&n);
    short a[n+1] ;
    for(i=1 ; i<=n ; i++ ){
        scanf("%hd",&a[i]);
    }

    fast(a ,1 ,n ) ;
    i=1;
    while(i<=n){
        printf("%hd " , a[i]);
        i++ ;
    }
    getch() ;
    return 0 ;
}

Upvotes: 0

Views: 2007

Answers (3)

cyber-monk
cyber-monk

Reputation: 5560

I would change your div function to return the resulting index of the partition. That way in the fast() function you can recurse on both side of the partition point. This cleans up the logic and should make it easy to test the div function in isolation and find the weak point in your logic (it's definitely in the div() function).

It looks like currently your code is assuming that the partition always happens in the middle, which is not always the case for quicksort (in fact that is one of the subtle points to quicksort).

Here is an example partition function:

// please forgive any C-syntax errors not my best language
// low and high indicate a segment of the array to partition
// returns the index between low and high which serves as
// the partition point
int partition(short a[], int low, int high){
  int partition = low;
  int pivot = high;  // sub-optimal when a is already sorted
  for(int i=low; i<high; i++){
    if(a[i] < a[pivot]){
      swap(&a[i], &a[partition]);
      partition++;
    }
  }
  // places the pivot into its final sorted position at partition
  swap(&a[partition], &a[pivot]);
  return partition;
}

This can be used recursively as follows

sort(short a[], int low, high){
  if(high-low > 0){
    int partition = partition(a, low, high);
    // recurse to left and right of partition
    sort(a, low, partition-1);
    sort(a, partition+1, high);
  }
}

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

one data seq:
index:1 2 3 4 5 6 7
data: 1 2 0 10 8 4 5
middle: (1 + 7) / 2 = 4
a[middle]=10
what do your function div want?

Upvotes: 0

Parallelis
Parallelis

Reputation: 719

The bug is in the div function itself, that didn't follow the QuickSort logic. You could fin working code here Quicksort algorithm

I would recommend to copy-paste the code and get inspired by it's coding-standard too, including comments :)

Upvotes: 1

Related Questions