CODEWITHSUNDEEP
c++arrayssorting
user3507072
user3507072

Reputation: 287

Deleting from an array and shifting

For an array, say, size 5, I'm trying to find a random position between 0 and the current last element of the array.

(This last position is 4 the first time, will be 3 the second time, and so on.)

Delete whatever element is in that array position, shifting all elements above it down so that there are no empty spots in the array.

I am trying to be as time-efficient as possible, so I want to avoid setting said random position to 0 or something like that.

So if my array looked something like int n[] = {1,3,5,7,9}; and my random position finder chose position 2, how would I move 5(position 2) to the end and shift everything down so that my resulting array looks like {1,3,7,9,5} ?

So far I have:

for (int j = 0; j < 5; j++)
    {
    printf ("before removal:\n");
    printarray (array, 5);

    int randompos =  (   rand() % (5-j)   ); //selects random number from 0 to active last pos.
    /* ?????? */ = array[randompos]; // What position will hold my random position?

//Also, what goes in place of the 'deleted' element?

    insertion_sort (array, 5-j); //sort only the active elements

    printf ("after removal:\n");
    printarray (array, 5);

    }

desired output:

before removal:
1,3,5,7,9

(say random position was array position 2, storing number 5)

after removal:
1,3,7,9,5

Upvotes: 0

Views: 247

Answers (2)

Dimitrios Bouzas
Dimitrios Bouzas

Reputation: 42889

#include <iostream>
#include <algorithm>
#include <random>

int main() {
  int n[] = {1, 3, 5, 7, 9};
  std::size_t n_size = sizeof(n) / sizeof(int);

  std::default_random_engine generator;  
  for(std::size_t i(0), sz(n_size); i < sz; ++i) {
    std::cout << "before removal:" << std::endl;
    std::cout << "  ";
    for(std::size_t j(0); j < n_size; ++j) std::cout << n[j] << " ";
    std::cout << std::endl;
    --n_size;
    std::uniform_int_distribution<int> distribution(0, n_size);
    std::size_t idx = distribution(generator);
    std::cout << "  Removing index: " << idx << std::endl;
    std::swap(n[idx], n[n_size]);
    std::sort(std::begin(n), std::begin(n) + n_size); // use your sorting here
    std::cout << "after removal:" << std::endl;
    std::cout << "  ";
    for(std::size_t j(0); j < n_size; ++j) std::cout << n[j] << " ";
    std::cout << "\n" << std::endl; 
  } 
}

LIVE DEMO

Upvotes: 0

Edwin
Edwin

Reputation: 825

Given the array {1,3,5,7,9} and pos = 2, you can do the following:

int main()
{
    int pos = 2;
    int arr[] = {1, 3, 5, 7,9};
    int length =sizeof(arr)/sizeof(arr[0]);
    int val = arr[pos];

    for (int i = pos; i < length; i++){
        int j = i + 1;
        arr[i] = arr[j];
    }
    arr[length - 1] = val;

    return 0;
}

Upvotes: 2

Related Questions