How to partition an array

This is a discussion on How to partition an array within the C Programming forums, part of the General Programming Boards category; There is some problem in the following code that seeks to partition the array (the first element taken as pivot). ...

  1. #1
    Registered User
    Join Date
    Sep 2012
    Posts
    18

    Cool 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;
    }
    Last edited by Salem; 12-20-2012 at 10:29 AM. Reason: fixed tags, caused by copy/paste cross-posting

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,694
    Please help me read your post.

    Also please help me understand, but describing why you are unhappy with your code...
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    Registered User
    Join Date
    Nov 2012
    Posts
    1,220
    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]

  4. #4
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    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.

  5. #5
    Registered User
    Join Date
    Nov 2012
    Posts
    1,220
    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.

  6. #6
    Registered User
    Join Date
    Sep 2012
    Posts
    18
    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.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Partition and scheduling HW/SW help!
    By thangdc01_02 in forum C++ Programming
    Replies: 3
    Last Post: 11-18-2010, 02:07 PM
  2. Partition QUERY
    By anirban in forum Tech Board
    Replies: 5
    Last Post: 07-03-2009, 10:48 AM
  3. an invisible partition?
    By Queatrix in forum Tech Board
    Replies: 11
    Last Post: 12-11-2006, 04:10 PM
  4. unmounting an usb partition
    By Lionel in forum Windows Programming
    Replies: 0
    Last Post: 10-14-2005, 08:47 AM
  5. Partition Question....
    By (TNT) in forum A Brief History of Cprogramming.com
    Replies: 13
    Last Post: 11-27-2001, 11:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21