CODEWITHSUNDEEP
c++arrays
Mozein
Mozein

Reputation: 807

a function that takes an array A and index i and rearrange it

Question is: write a function that takes an array A of length n and an index i into A, and rearrange the elments such that all elements less than A[i] appear first, followed by elements equal to A[i], followed by elements greater than A[i].

explanation for my code:

Ask user for n numbers, which is 11. And ask him what the index that he wants to rearrange the elements with. It takes it to function1, and creates a for loop and does an if else statement. if A[i] < A{index} , place it in the begining, else if it's less, place it at the end, or place it in the middle:

Here is my code

#include <iostream>
using namespace std;

void function1(int a[], int ind);
int main()

{
    int a[11];
    int index;
    cout << " enter the numbers: " << endl;
    for(int i=0; i < 11; i++)
        cin >> a[i];

    cout << "what is the index ? " << endl;
    cin >> index;

    function1(a,index);
}

void function1(int a[], int ind)
{
    int x = a[ind];
    int newArray[11];
    for(int i=0; i < 11; i++)
    {
        if(a[i] < x)
        {
            newArray[i] = a[i];
        }
        else if(a[i] > x)
        {
            newArray[10-i] = a[i];
        }
        else
        {
            newArray[10/2] = a[i];
        }
    }

    for(int i=0; i<11; i++)
        cout << newArray[i] << " ";
}

The output that I am expecting to get is the rearrangement of the new array which will probably look similar to this:

a[0....x....n-1], where x is the index that represents a[i] however I am getting incorrect output with numbers randomly scattered across

what is wrong with my logic ?

Upvotes: 0

Views: 275

Answers (3)

xmoex
xmoex

Reputation: 2702

The problem is that (like Olaf Dietsche pointed out) you take just one index where two are necessary. Further you can't know if the element that is neither smaller not bigger than a[ind] (means equal to a[ind]) is to be inserted in the middle of the new array. (Imagine 3 2 1 and index 3 results in 2 1 3 but 3 isn't in the middle!)

Updated Version (allows for multiple elements with same value as pivot element)

void rearange(int* data, int size, int pivot)
{
    int* temp_data = new int[size];
    int start_index = 0, end_index = size - 1;

    for (int i = 0; i < size; i++)
    {
        if (data[i] < data[pivot]) // -> insert 'before' pivot element
        {
            temp_data[start_index] = data[i];
            start_index++;
        }
        else if (data[i] > data[pivot]) // -> insert 'behind' pivot element
        {
            temp_data[end_index] = data[i];
            endIndex--;
        }
        // else: skip pivot(s)
    }

    // insert pivot element(s)
    for (int i = start_index; i <= end_index; i++)
    {
        temp_data[i] = data[pivot];
    }

    for (int i = 0; i < size; i++)
    {
        std::cout << temp_data[i] << " ";
    }
    delete[] temp_data;
}

Input:

11 10 9 8 7 7 7 6 5 4 3
5

Output

6 5 4 3 7 7 7 8 9 10 11

As you see, all elements smaller than element 5 (with value of 7) are before, all elements greater are behind the pivot element. All other elements with same value as pivot are wrapped around position 5, wherever there's free space. However the rearranged elements are not yet sorted (apart from being positioned relative to pivot element)!

Upvotes: 1

Olaf Dietsche
Olaf Dietsche

Reputation: 74028

You use the same index i for the smaller and larger values. This means, if only the last value a[10] is larger than x, you will write it in the first location newArray[10 - 10], even though you already filled all places up to the 10th. Another problem is, when you have multiple middle values. They will all be stored into newArray[5].

What you want to achieve is called partitioning, as used in the quicksort algorithm.

You need to maintain two indexes (pointers), one for the smaller (left) and one for the larger (right) values.

Upvotes: 1

Cem Aytekin
Cem Aytekin

Reputation: 109

You have to determine the size of your array at the beginning and pass the fixed size of the array to the function as a parameter.

Upvotes: 0

Related Questions