c++ why doesn't this sort the numbers properly?

Question

i'm trying to write an insertion sort. i have written one, and it compiles and it runs, and it sorts the numbers. it just sorts them into a random order rather than the right order, and i have NO IDEA why it's doing that. i've worked out which part of the code is the problem. this is that code:

w2 = x-1;
w = w2;

while(x > 0)
{

while(w >= 0)
{
if(numbers[x] < numbers[w])
{
temp = numbers[w];
numbers[w] = numbers[x];
numbers[x] = temp;
}

w--;

}
x--;
w = w2;
}

numbers[] is the array containing all of the numbers as floats. the amount of numbers stored in it is x.

please please help!

Answer 1

You implementation does not look like an insertion sort... It kind of looks like a mix between bubble sort and insertion sort, that's why it does not work.

Also I see that if your x contains number of elements, array will be out of bounds when you do the first iteration if(numbers[x] < numbers[w]) as arrays in C++ are 0-based



Here's correct implementation of insertion sort. I replaced x with length, where length is a number of elements in array. If your x is the last index of an array, do length=x+1;



for (int i=1; i


// Create a hole between sorted and unsorted area,

// store the number from the hole in valueToMove

float valueToMove = numbers[i];

int holeIndex = i;



// Move the hole down in sorted area until valueToMove is >= than already sorted value

while(holeIndex>0 && valueToMove


// Move the hole down

numbers[holeIndex] = numbers[holeIndex-1];

holeIndex--;

}

// hole is in right sorted position to insert stored value, fill the hole now

numbers[holeIndex] = valueToMove;

}

Answer 2

The only things I see is that x needs to be the index of the last entry in numbers[], which is ONE LESS than "the amount of numbers". Also, the initialization of w needs to be inside the x loop. Suppose n is the actual number of data values in numbers. Then:



int x = n-1;

while (x > 0)

{

int w = x-1;

whlile (w>=0)

{

...etc.



Then you can lose the w2 and w settings at the top. w is only needed inside the x loop, so that's where it should be declared.



In your original code, w is aways being set to w2. The first two outer loops work as planned, moving the largest element to to numbers[n-1] and the second largest to numbers[n-2]. On the third iteration, though, w is still n-2 at entry and the inner loop will swap the second largest element down to numbers[n-3] on the very first compare. That happens because x is n-3 on that loop, but w was set back to w2, which is equal to n-2.



You might want to pick better variable names, since "w" and "x" aren't exactly self-explanatory. Maybe ix_left and ix_right, or iLeft and iRight? That would emphasize that w must be less than x at all times in the inner loop.



Edit: Kozak is right. This isn't really an insertion sort. I believe the technical name is "selection sort" since it selects the largest element from the unsorted portion of the data on each inner loop, placing it in the correct position. Selection and insertion sorts have roughly the same runtime, but opposite orientation:



An insertion sort removes elements sequentially from the unsorted list and finds the place to insert each into the sorted list. A selection sort removes elements form the list in their final sort order and adds them sequentially to the sorted lest.



The insertion sort might look like:



int xnext = 1;

while (xnext < n)

{

int nextval = numbers[xnext ];

int xinsert = xnext ;

while (xinsert > 0 && nextval < numbers[xinsert-1])

{

--xinsert;

numbers[xinsert+1] = numbers[xleft];

}

numbers[xinsert] = nextval;

}



That's just typed on-the-fly so there may be errors. The general idea is that numbers[0] is a starting sorted output list, and values numbers[1], numbers[2], etc. are inserted into that list on each iteration of the outer loop. The inner loop searches from right to left for where to put the new number, and moves bigger values to the right to make room for the insert.

Answer 3

This looks like a bubble sort not an insertion sort.



The problem is that this sort requires that you compare adjacent values, w and x are not always pointing to values next to each other and so the sort doesn't work.



If in doubt on this sort of thing write each variable out by hand and track how they change as you work through the code.



change your code to this and it should work



while(x >= 1) {

w = x-1;

while(w >= 0) {

if(numbers[x] < numbers[x-1])

{

temp = numbers[x-1];

numbers[x-1] = numbers[x];

numbers[x] = temp;

}

}

}



Also it's more normal to do this sort of thing with a for loop, it just makes it a little clearer what's going on.

Answer 4

hi, hugs, inspite of it somewhat is, and that i know many that spoke returned, i replace into pulled in with the 1st 2 strains. I say this reward a Pulitzer, UM ok wait that could desire to be somewhat over the main substantial suitable, in spite of the shown fact that the relationship with Kool-help threw me, is that approximately Jim Jones? together as's the amazing time ya mentioned Blue submit to indoors the woods with a roll of Charmin?

Answer 5

I'm not seeing an issue here.



Could you give an example of what you are inputting and what you are getting for results?