CODEWITHSUNDEEP
c++arraysalgorithmsorting
Mike Smith
Mike Smith

Reputation: 1

Algorithm for deleting multiple array elements and shifting array

I have an array let's say with 5 items, if element[i] is less than 3 need to move element[i+1] in place of element[i].

int array[5] = {4, 2, 3, 5, 1};
int number = 3;

    for (int i = 0; i < number; i++)
    {
        if (array[i] > number)
        {
           for (int j = 0; j < i - 1; j++)
           {
               array[j] = array[j + 1];
           }
           number = number - 1;
        }
    }

expected result is array = {2, 3, 1, anyNumber, anyNumber};

Upvotes: 0

Views: 3844

Answers (6)

Agent 0
Agent 0

Reputation: 401

I created my own example, hope this helps people as a reference:

// Removing an element from the array. Thus, shifting to the left.
void remove(){
    int a[] = {1, 2, 3, 4, 5, 6};
    int size = sizeof(a)/sizeof(int);               // gives the size
    for(int i = 0; i < size; i++){
        cout << "Value: " << a[i] << endl;
    }

    int index = 2;                                  // desired index to be removed

    for(int i = 0; i < size; i++){
        if(i == index){
            for(int j = i; j < size; j++){
                a[j] = a[j+1];
            }
        }
    }

    size--;                                        // decrease the size of the array

    cout << "\nTesting output: " << endl;
    for(int i = 0; i < size; i++){
        cout << "Value: " << a[i] << endl;
    }

}

int main(){
    remove();
    return 0;    
}

Upvotes: 0

PaulMcKenzie
PaulMcKenzie

Reputation: 35440

As an alternative, if you want to keep your items, but denote what will be at some later time, "removed", the algorithm that can be used is stable_partition:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <functional>

int main()
{
    int vValues[] = {4,2,3,5,1};

    // partition the values on left and right.  The left side will have values
    // <= 3, and on right >3.  The return value is the partition point.
    int *p = std::stable_partition(vValues, vValues + 5, 
                                   std::bind2nd(std::less_equal<int>(), 3));
    // display information 
    std::cout << "Partition is located at vValues[" << std::distance(vValues, p) << "]\n";
    std::copy(vValues, vValues + 5, std::ostream_iterator<int>(std::cout, " "));
}

Output:

Partition is located at vValues[3]
2 3 1 4 5

You will see that 2,3,1 are on the left of partition p, and 4,5 are on the right of the partition p. So the "removed" items start at where p points to. The std::partition ensures the elements are still in their relative order when done.

Upvotes: 0

R Sahu
R Sahu

Reputation: 206597

Here's a more compact and idiomatic (that's how I view it anyway) way to remove items from an array:

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
   int array[] = {4, 2, 3, 5, 1};
   int* begin = array;
   int* end = begin + sizeof(array)/sizeof(array[0]);
   int number = 3;

   end = std::remove_if(begin, end, [&number](int v) {return v > number;});
   std::copy(begin, end, std::ostream_iterator<int>(std::cout, " "));
   std::cout << std::endl;

   return 0;
}

Just for comparison, here's a version using std::vector:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main()
{
   std::vector<int> array = {4, 2, 3, 5, 1};
   int number = 3;

   auto end = std::remove_if(array.begin(), array.end(), [&number](int v) {return v > number;});
   std::copy(array.begin(), end, std::ostream_iterator<int>(std::cout, " "));
   std::cout << std::endl;

   return 0;
}

Upvotes: 0

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145279

Nested loops give you O(n2) complexity, and non-obvious code.

Better use std::remove_if:

int array[5] = {4, 2, 3, 5, 1};
int number = 3;
remove_if( begin( array ), end( array ), [=]( int x ) { return x>number; } );

Disclaimer: code untouched by compiler's hands.

Upvotes: 1

Laura Maftei
Laura Maftei

Reputation: 1863

Try this code. You should not decrease number at each step. Also, the second loop should start at i and stop at the end of array:

int array[5] = {4, 2, 3, 5, 1};
int number = 3;

for (int i = 0; i < number; i++)
{
    if (array[i] > number)
    {
       for (int j = i; j < 5; j++)
       {
           array[j] = array[j + 1];
       }
    }
}

Upvotes: 0

Haris
Haris

Reputation: 12270

A O(n) working code for the above problem.. But as others pointed out in the comments.. You end up with an array that is using less space then allocated to it..

#include<stdio.h>

int main()
{

        int arr[] = {4, 2, 3, 5, 1};

        int* temp1 = arr;
        int* temp2 = arr;
        int i, n1 = 5, n2 = 5;

        for(i = 0; i < n1; i++)
        {
                if(*temp2 >= 3)
                {
                        *temp1 = *temp2;
                        temp1++;
                        temp2++;
                }
                else
                {
                        n2--; //the number of elements left in the array is denoted by n2
                        temp2++;
                }
        }
}

Upvotes: 1

Related Questions