Sort an array as values are inputted into the array

Question

I need help with a loop that will shift the elements of an array if a newly added value is lower than an existing value, so the array is being sorted as new values are inputted.

The array is empty to start with.

I had tried several loops but they don't seem to work in my case as they were loops used for arrays that were already full.

Here is the code I currently have.

if(index < 0)
    index = -(index + 1);

if(arr[index] > key)
    for(int i = 0; i < count -1; i++) {
        arr[index + i] = arr[index + i + 1];
    }

arr[index] = key;

The index is from a binary search.

So for example, if I have input 80 first, it would take the slot of arr[0]. Then I input 45, which will also take the slot of arr[0].

Since 45, key, is smaller than the existing arr[0] (80), 80 is to move up an index.

Hint to understand what your problem in that code is; we would need to understand how you setup the whole thing. How are index/count getting their values?! It is really confusing to see that index might < 0 in some cases?! — GhostCat
– GhostCat, Commented Oct 2, 2016 at 19:38

Maytham Fahmi · Accepted Answer · 2016-10-02 19:52:10Z

2

You might want the loop so that it does the following:

Shift the elements with indices > index so that you make space for the new element, and
then add the element to given index.

for (int  i = count; i > index; i--) {
    arr[i] = arr[i - 1]; // shifts the elements to the one place right
}
arr[index] = key; // add the key to the given index

Note: The count is the current number of elements in the array and it is less than arr.length

edited Oct 2, 2016 at 19:52

Maytham Fahmi

33.2k17 gold badges132 silver badges159 bronze badges

answered Oct 2, 2016 at 19:38

Moonstruck

5034 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

FiftySentos Over a year ago

Thanks. That worked. Working from the end of the array downwards definitely makes a lot more sense than what I was trying to do.

Moonstruck Over a year ago

Sure! Happy to help

Thomas Over a year ago

@FiftySentos Please mark this answer as "correct" so that Jainul gets his due credit and others with the same problem will easily find it.

Squirrelkiller Over a year ago

You may want to add recreating the array bigger, if its current length is reached. That's how an ´Arraylist´ works btw, keeping an array internaly and doubling its length when its current capacity is reached.

GhostCat · Accepted Answer · 2016-10-02 19:31:11Z

1

You can go for something like this:

First of all, you need

A counter that tells you how many "unused" array elements are left; there is no point in swapping index 1 to 2, 2 to 3, ... if you find in the end that your array is "full"
Keep an eye on the index, to avoid going beyond the length of your array

Then it is really simple:

You iterate your current array to find the first index (lets call it n here) that is bigger than key
Then you turn to the last array index that is "in use" ... and start moving values to the right from there
Finally, after you moved arr[n] to arr[n+1]; you assign arr[n] = key

answered Oct 2, 2016 at 19:31

GhostCat

141k28 gold badges190 silver badges262 bronze badges

Comments

Joe C · Accepted Answer · 2016-10-02 19:27:29Z

0

It looks like you're attempting to shift your array elements in the wrong direction.

Given index = 0 and i = 0, you'd end up with:

arr[0] = arr[1];

When you probably want the other way around.

answered Oct 2, 2016 at 19:27

Joe C

15.8k8 gold badges42 silver badges52 bronze badges

1 Comment

FiftySentos Over a year ago

arr[index + i + 1] = arr[index + i] would make it arr[1] = arr[0]?

Collectives™ on Stack Overflow

Sort an array as values are inputted into the array

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related