How to partition an array

There is some problem in the following code that seeks to partition the array (the first element taken as pivot). Please help me fix the issue.

Code:

---

#include<stdio.h>
#include<conio.h>
int partition(int [],int,int);
main()
{
int a[20],n,i;
printf("enter the number of elements in the array\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter the number\n");
scanf("%d",a+i);
}
printf("the index of the pivot is %d and the partitioned array is\n",partition(a,0,n-1));
for(i=0;i<n;i++) printf("%d\t",a+i);
getch();
}
int partition(int a[],int lower,int upper)
{
int p=a[lower];
int i=lower,j=upper+1,temp;
do
{ do{i++;}while(a[i]<=p);
do{j--;}while(a[j]>=p);
if(i<j){ temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i>=j);
a[lower]=a[j];
a[j]=p;
return j;
}

---

Please help me read your post.

Also please help me understand, but describing why you are unhappy with your code...

In the line

Code:

---

for(i=0;i<n;i++) printf("%d\t",a+i);

---

I think it should be

Code:

---

for(i=0;i<n;i++) printf("%d\t",*(a+i));

---

This is easily found if you turn on warnings in the compiler:

Code:

---

main.c:15:2: warning: format '%d' expects argument of type 'int', but argument 2
 has type 'int *' [-Wformat]

---

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.

Give an example array where it does not work. Also state what output you are expecting, giving a certain input array. I tried that code just now with some arrays and got some output just fine. Whether the output is correct or not, I cannot say... this depends on what you are expecting for correct output.

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. :cool:

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.