Shifting Objects Up in an Array

Question

I'm creating a program that creates an array of objects in random positions in an array size 8. Once created, I need them to sort so that all the objects in the array are shifted up to the top, so no gaps exist between them. I'm almost there, but I cannot seem to get them to swap to index 0 in the array, and they instead swap to index 1. Any suggestions? (Must be done the way I'm doing it, not with other sorting algorithms or whatnot)

#include <iostream>
#include <string>
#include <ctime>
using namespace std;

struct WordCount {
    string name = "";
    int count = 0;
};

int main() {
    cout << "Original random array: " << endl;

    srand(static_cast<int>(time(0)));

    int i = 0;
    WordCount wordArr[8];

    while (i < 4) {
     int randomNum = 0 + (rand() % static_cast<int>(7 + 1));

     if(wordArr[randomNum].name == "") {
          wordArr[randomNum].name = "word" + static_cast<char>(i);
          wordArr[randomNum].count = i;
          i++;
     }
    }

    int j = 0;
    while (j < 8) {
      cout << wordArr[j].name << " " << wordArr[j].count << endl;
      j++;
    }

    cout << "\n\nSorted array: " << endl;

    for (int i = 7; i >= 0; i--) {
      for (int j = 0; j <= 7; j++) {
        if (wordArr[i].name != "") {
          if (wordArr[j].name == "") {
            WordCount temp = wordArr[i];
            wordArr[i] = wordArr[j];
            wordArr[j] = temp;
          }
        }
      }
    }

    int k = 0;
    while (k < 8) {
      cout << wordArr[k].name << " " << wordArr[k].count << endl;
      k++;
    }


    return 0;   
}

Once you've completed this exercise of doing it by hand, please look at std::partition which does this as a single well-tested function call that is part of the standard. Please don't make the mistake of thinking standard algorithms come with a penalty or need external libraries, or are somehow not "real" C++. They don't, they're part of C++ and there for you to use. — acraig5075
– acraig5075, Commented Nov 7, 2017 at 7:37

Ken Y-N · Accepted Answer · 2017-11-07 06:48:16Z

If I understand your requirement correctly, you want to move all the non-blank entries to the start of the array. To do this, you need an algorithm like this for example:

for i = 0 to 7
    if wordArr[i].name is blank
        for j = i + 1 to 7
          if wordArr[j].name is not blank
              swap [i] and [j]
              break

So, starting from the beginning, if we encounter a blank entry, we look forward for the next non-blank entry. If we find such an entry, we swap the blank and non-blank entry, then break to loop again looking for the next blank entry.

Note, this isn't the most efficient of solutions, but it will get you started.

Note also I'd replace the 4 and 8 with definitions like:

#define MAX_ENTRIES (8)
#define TO_GENERATE_ENTRIES (4)

Finally:

wordArr[randomNum].name = "word" + static_cast<char>(i);

That will not do what you want it to do; try:

wordArr[randomNum].name = "word" + static_cast<char>('0' + i);

To append the digits, not the byte codes, to the end of the number. Or perhaps, if you have C++11:

wordArr[randomNum].name = "word" + std::to_string(i);

R Sahu · Accepted Answer · 2017-11-07 06:55:08Z

I see couple of problems.

The expression "word" + static_cast<char>(i); doesn't do what you are hoping to do.

It is equivalent to:
```
char const* w = "word";
char const* p = w + i;
```
When i is 2, p will be "rd". You need to use std::string("word") + std::to_string(i).

The logic for moving objects with the non-empty names to objects with empty names did not make sense to me. It obviously does not work for you. The following updated version works for me:

for (int i = 0; i <= 7; ++i) {

   // If the name of the object at wordArr[i] is not empty, move on to the
   // next item in the array. If it is empty, copy the next object that
   // has a non-empty name.
   if ( wordArr[i].name == "") {

      // Start comparing from the object at wordArr[i+1]. There
      // is no need to start at wordArr[i]. We know that it is empty.
      for (int j = i+1; j <= 7; ++j) {
         if (wordArr[j].name != "") {
            WordCount temp = wordArr[i];
            wordArr[i] = wordArr[j];
            wordArr[j] = temp;
         }
      }
   }
}

R Sahu · Accepted Answer · 2017-11-07 06:56:12Z

1

There was two problems as :

wordArr[randomNum].name = "word" + static_cast<char>(i); this is not what your are looking for, if you want that your names generate correctly you need something like this :
```
wordArr[randomNum].name = "word " + std::to_string(i);
```

Your sorting loop does not do what you want, it's just check for the "gaps" as you said, you need something like this :

for (int i = 0; i < 8; ++i) {
        for (int j = i+1; j < 8; ++j) {
            if (wordArr[i].name == "" || (wordArr[i].count < wordArr[j].count)) {
                WordCount temp = wordArr[i];
                wordArr[i] = wordArr[j];
                wordArr[j] = temp;
            }
        }
    }

edited Nov 7, 2017 at 6:56

R Sahu

207k15 gold badges168 silver badges291 bronze badges

answered Nov 7, 2017 at 6:55

HMD

2,2256 gold badges29 silver badges40 bronze badges

1 Comment

R Sahu Over a year ago

Using 4 spaces to format code works in normal text. Under lists, you'll have to use 8 spaces. I can't quickly find where that is documented.

gsamaras · Accepted Answer · 2017-11-07 06:48:32Z

Your algorithm sorts the array, but then looses the sorting again.

You want to swap elements only when i > j, in order to push elements to the top only. As a result, you need to change this:

if (wordArr[j].name == "")

to this:

if (wordArr[j].name == "" && i > j)

Consider this array example:

 0
ord 1
 0
 0
rd 2
word 0
d 3
 0

Your code will sort it to:

d 3
ord 1
word 0
rd 2
 0
 0
 0
 0

but when i = 3, it will try to populate the 5th cell, and it will swap it with rd 2, which is not what we want.

This will push rd 2 down, but we don't want that, we want gaps (zeroes) to go to the end of the array, thus we need to swap eleemnts only when they are going to go higher, not lower, which is equivalent to say when i > j.

PS: If you are a beginner skip that part.

You can optimize the inner loop by using one if statement and a break keyword, like this:

  for (int j = 0; j <= 7; j++) {
    if (wordArr[i].name != "" && wordArr[j].name == "" && i > j) {
        WordCount temp = wordArr[i];
        wordArr[i] = wordArr[j];
        wordArr[j] = temp;
        break;
    }
  }

Collectives™ on Stack Overflow

Shifting Objects Up in an Array

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related