Thread: How to partition an array

After replacing (a+i) with *(a+i) also the problem remains the same- the partitioned array is not printed. I think there is some run time problem which I find difficult to fix.

the example array- 7,5,3,8
Expected output- the index of pivot element is 2 and the partitioned array is
3 5 7 8
obtained output- after entering the array, the program stops working and says "process returned -1073741819 <0xC0000005>

I just can't understand the problem with the code.
I hope I can be helped now.

When you partition an array, you are simply dividing it up, with the "center line", being the pivot you've chosen. The array will NOT usually be sorted, after one partition. There are two ways to sort an array, using partitioning:

1) As you repeatedly partition it, you cut down on the number of items you are partitioning - Quicksort uses this, most effectively. In the end, you have two numbers, and one of them is the new pivot.

2) Change the pivot value, through the range of numbers being sorted. If the pivot is set for every possible value in the array, then the array will be sorted. The downside of this, is you wind up swapping a huge amount of numbers, over and over.

Your partition logic appears wrong to my eyes, and that's why it's not printing.

Compare it with this partition code, which works correctly, note the while() loops on the i and j "markers", instead of a do() while, which increments or decrements, before there is a need to do so.

Also, note the ++i and --j, after a swap is made. The code will loop endlessly without those, given some particular array values, without them.

This functions using a global array and SIZE, because it's part of another program, which requires it.

Code:

void partition(void)
{
   int i,j,temp,swaps, pivot; 
   swaps=i=0;
   j=SIZE-1;
   
   pivot=a[0]+a[j];
   opivot=pivot;

   while(pivot>0) { 
      pivot-=1; 
      
      do {    
         while (a[i] < pivot) ++i; 
         while (a[j] > pivot) --j;
         if (i<j) {  
            swaps++;
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;  
            ++i;
            --j;
         }
      }while(i<j); 
      printf("\nSwaps were: %d\n",swaps);
      i=0;
      j=SIZE-1;
   }
 printf("opivot: %d\n",opivot);

}

If you change the pivot-=1; to a larger value than one, you'll begin to see that the array won't be sorted correctly, depending on the values in the array.

If you only partition an array by ONE number, the array will only be divided up, acording to that ONE number - nothing else, and not sorted.