Question

-I need help with C++. I'm working with an array of words. The array size is 1000 but not all 1000 slots will be filled. I run an insertion sort algorithm and then output the array but the sorted array output includes the unused empty slots so there is a lot of blank spaces before the sorted words appear.

-The sorting algorithm seems to be reading in the empty array slots as well. Is there a way to read an array and only work with the non-empty slots? In other words, how do I filter out the array so that it will exclude the blanks? I can't be sorting and printing out the blank array slots, only the slots with a word on it.

Answer 1

I can suggest you few methods for the same:

method 1:

Since Insertion sort is based on sequential sorted frame checking so it checks that the elements before the current cell is sorted or not.

You can use vectors<string>new_array;

and traverse the array and only push the non_blank elements int the vector<string> and then perform sort on this vector<string>

so now you have eliminated the blank string blocks.

if you want to preserve the array index,you could create a vector of pairs of type pair<sting,int>

vector<pair<string,int>> and apply insertion sort on this then just reassign the elements according to the new index.

you could also create a function to convert this back to the array of words with only non_blank slots then perforn sorting.

Method2:

you can create a Boolean array bool has_a_word[1000];

then traverse through the whole array of words in O(n) complexity and store true in the array index where words are non_blank and false other wise

bool has_a_word[1000];

for(int i=0;i<1000;i++)

{

if(arr[I]==" ")

has_a_word[I]=false;

else

has_a_word[I]=true;

}

then while operating the insertion sort code function you could just check if it has a word then only check for the sorted order in the previous words else just iterate ahead and the same while checking and compare functions.

and

while printing the array you could just print the elements or the words with bool value true from the Boolean array.