1

So, I have to sort an array of integers so that every lesser number than some scanf'd integer is on the left, this set variable is in the middle, and every greater numbers on the right. I've got left and right part covered, but I am not sure how to make it so the variable is in the middle.. any ideas?

#include <stdio.h>
int main()
{
    int y, i, k, temp;
    printf("give integer\n");
    scanf("%d", &y);
    int x[10] = {5,8,9,4,2,3,2,4,5,6};
    i=0;
    k=1;
    while(i<10)
    {
        while(x[i]>y&&k<10)
        {
            temp=x[k];
            x[k]=x[i];
            x[i]=temp;
            k++;
        }    

        i++;
        k=i+1;
    }


    for(i=0; i<10; i++)
    {
        printf("x[%d]=%d\n", i, x[i]);
    }
}

Example input/output:

input: x[i]={5,2,1,6,7,3,2,4,5,6}    y=5
output: x[i]={2,1,4,3,2,5,5,7,6,6}
Improve this question
16
  • 1
    Look at this Possible implementation std::partition Its C++, but you can figure out what to do Commented Oct 27, 2013 at 18:49
  • Can you clarify your question? It looks like you're basically asking us to sort an array, which can be done in place with a number of methods, Heap sort, Quick sort, insertion sort, etc. Commented Oct 27, 2013 at 18:49
  • @AndyG he wants 2,2,3,4,4,y,5,5,6,8,9 Commented Oct 27, 2013 at 18:52
  • well it's not supposed to be sorted ascending or descending, just that numbers greater than y should be on the right side of numbers equal y. Sorry I can't explain it any better but I am new to programming and not native in english. Commented Oct 27, 2013 at 18:54
  • 1
    @deviance: I think an example input and output sequence (added to the question, not here in the comments) would help immensely. Commented Oct 27, 2013 at 18:57

4 Answers 4

Reset to default
2

Instead of using one array you could use two arrays for reducing your code complexity.

Search for the numbers those are less than y and then store them in an array. Let's say A[ ]
Again search for the numbers those are greater than y and then store them in another array B[ ]
Like so..

Now you've got all of them. You could store them in another array which can be called as the sorted array. Or if you just want to print them, then

  1. print all the elements of first array A[ ]
  2. then print y
  3. finally print the elements of second array B[ ]

That's all. Hope this idea will help you to code and solve this quickly.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I think I have to use 1 array for this task (I have to rearrange it) :(
You are still able to rearrange this. Just iterate through x[] from beginning to end. And store the elements sequentially from A[], y, B[]. This will overwrite the x[] which is fine.
Well I guess I'll do it if won't be able to think of anything better, I already thought about it but thought it's going to miss the point of exercise.
@deviance - Are you sure? You have to use intermediate storage at some point, to do the "pseudo sorting". That does not mean that the original array cannot be updated with the manipulated results when the sorting is done.
1

You are looking for an algorithm similar to "partition" as in the quicksort algorithm. The idea is to have 2 indexes i and j where i is used to iterate through the array whereas j is the index of the first item that is greater or equal to y.

After that first loop, you have the numbers that are lesser than y on the left and the other numbers on the right. However, you actually want to group the values equal to y and have only the number greater than y on the right. So I'm suggesting to do the same on the interval [j,n] but now I'm also moving when it's equal.

// Function to exchange the values of 2 integer variables.
void swap(int *a, int *b) {
    int buf = *a;
    *a = *b;
    *b = buf;
}

// Do the job, in place.
void partition(int *tab, int n, int y) {
    // This first part will move every values strictly lesser than y on the left. But the right part could be "6 7 5 8" with y=5. On the right side, numbers are greater or equal to `y`.
    int j = 0; // j is the index of the position of the first item greater or equal to y.
    int i;
    for (i = 0; i < n; i++) {
        if (tab[i] < y) {
        // We found a number lesser than y, we swap it with the first item that is greater or equal to `y`.
            swap(&tab[i], &tab[j]);
            j++; // Now the position of the first value greater or equal to y is the next one.
        }
    }

    // Basically the same idea on the right part of the array.
    for (i = j; i < n; i++) {
        if (tab[i] <= y) {
            swap(&tab[i], &tab[j]);
            j++;
        }
    }
}

int main() {
    int y;
    printf("give integer\n");
    scanf("%d", &y);
    int x[10] = {5,8,9,4,2,3,2,4,5,6};
    partition(x, 10, y);

    int i;
    for(i=0; i<10; i++)
    {
        printf("x[%d]=%d\n", i, x[i]);
    }

    return 0;
}

This code gives, with x = {5,2,1,6,7,3,2,4,5,6}; and y = 5:

x[0]=2
x[1]=1
x[2]=3
x[3]=2
x[4]=4
x[5]=5
x[6]=5
x[7]=7
x[8]=6
x[9]=6

The first 5 elements are lower than 5 and the others are greater or equal to 5.

Improve this answer

5 Comments

Thanks for your time but unfortunately not only I can't modify size of this array but also the other elements have to be only greater, not greater or equal than y.
@deviance see my last edit. Does it respect what you're trying to do? Basically, I've added a second pass to deal with the numbers equal to y.
DAMN it works, would you mind adding some comments to it, as to what each part of the code is doing? Either way thanks a lot!
Im having troubles with understand the first if in function partition, if for example x[0] is lesser than y, than it would be swapped with x[j] which would be x[0] aswell, and then both j and i increase.. how does it work?
@deviance is it clearer now? Of course it might not be obvious to you, so try to run it "with the hands" with a small array.
1

This is a simple, straight forward way to sort the array x into another array y by partition. The numbers are sorted <= partition on left, and > partition on right:

[EDIT] to illustrate method according to OP clarification:
if array has 2 elements that are equal to p, then it should be arranged like this: xxxxxppyyyy where xp and p can't be mixed with either x's or y's.
Except that the example: xxxxxppyyyy is too long for the array, so I assume you meant xxxxppxxxx (10 elements, not 11). 

int * partitionArr(int *z, int p);

int main(void)
{
    int i, x[10] = {5,8,9,4,2,3,2,4,5,6};
    //int i, x[10] = {3,3,3,3,3,8,8,8,8,8};
    int *y;
    int partition;

    printf("enter a number from 0 to 10\n");
    scanf("%d", &partition);

    y = malloc(sizeof(int) * sizeof(x)/sizeof(x[0])+1); //+1 for inserting partition
    y = partitionArr(x, partition);

    printf("Partition is: %d\n\n", partition);  
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        printf("y[%d] == %d\n", i, y[i]);   
    }
    getchar();
    getchar();

    return 0;
}

int * partitionArr(int *z, int p)
{
    int i=0,j=0;
    int x[10];

    //load y with x
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++) x[i] = z[i];

    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        if(x[i]<p) 
        {
            z[j] = x[i];
            j++;
        }
    }   
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        if(x[i]==p) 
        {
            z[j] = x[i];
            j++;
        }
    }   
    for(i=0;i<sizeof(x)/sizeof(x[0]);i++)
    {
        if(x[i]>p) 
        {
            z[j] = x[i];
            j++;
        }
    }
    return z;
}

OUTPUT for following conditions: x < P; x== P; x< p (the only way to ensure P is in middle)

enter image description here

Improve this answer

8 Comments

This would have the same output as my code, it wouldn't move the first 5.
I will add an image of output. It does what you ask: smaller on left, larger on right, and do not include variable partition. I am using "5", and comparison for smaller is x <= p. (so the 5s would show up on the left.
Yeah, but p must be in the middle, so comparison for smaller would have to be < and not <=
Okay, then change the comparison accordingly, I will edit my code :)
I think you misunderstood me :D Just like in example input/output in OP if array has 2 elements that are equal to p, then it should be arranged like this: xxxxxppyyyy where x<p and y>p and p can't be mixed with either x's or y's.
|
1

Simple algorithm, in case you want to work this through yourself:

  1. partition entire array as [min..y][y+1..max], and take note of where the split is.
  2. re-partition the first part only as [min..y-1][y..y].

Array should now be partitioned [min..y-1][y..y][y+1..max].

Simplest is to have a partition_helper function which does the partitioning and returns position of the split. Then the primary partition function calls this function twice, with right arguments.

You could also partition the other way, [min..y-1][y..max] first and then the re-partition the last part as [y..y][y+1..max], end result should be the same.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.