insertion sort code

[adam2016]

Hi people I just asked a question on finding the smallest number and index I have figured that out with credit to all the people who helped me on here but now I move onto the bigger picture trying to sort a list of numbers,granted my code is quite messy sorry about that in advance.I'm following code from Alex Allains jumping into c++ on using an insertion sort algorithm I copied I followed it not quite word from word but my code does not sort the list of numbers BUT it just cuts off the last number in the list and prints the list out in it's original order not the new order like I want it,heres the code any ideas where I am going wrong and how I can fix this?

   #include <iostream>

using namespace std;

int findSmallest(int values[],int index,int size){

     int smallest = index;

    for(int i = index + 1;i < size; i++){

        if (values[i] < values[smallest]){

            smallest = i;

        }
    }
    return smallest;
}

void swapArray(int aray[],int fIndex,int sIndex){

  int temp = aray[fIndex];
  aray[fIndex] = aray[sIndex];
  aray[sIndex] = temp;

}

void sort(int aray[],int size){


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

      int index = findSmallest(aray,size,i);
      swapArray(aray,i,index);
     }


}

int main()
{
   int ray[3];
   for(int i = 0;i <3;i++){

       cout << "enter values" << endl;
       cin >> ray[i];
   }

   cout << findSmallest(ray,0,3) << endl;

   cout << "---------" << endl;

   sort(ray,3);

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

      cout << ray[i] << endl;
   }
}

[Naughty Albatross]

So what does your program output look like?

When you input 3 numbers?
When you input 5 numbers?

[adam2016]

so when I input 3 numbers
lets say 2 3 1

I get

2
3


then it cuts the last number off

then I tried 5 and I got the same result pretty much

lets say I put 7,6,5,4,3

I get the output

7
6
5
4

[Duthomhas]

Line 33: you mixed up size and i

Hope this helps.

[adam2016]

at Duoas

first of all thanks and second that made a world of difference now my code works perfect I get the exact output I was hoping for

I kind of understand the code but I'm not still 100 perecent sold on how the code actually works if someone could summarize it up for me that would be amazing.

thanks =)

and a side not in Alex Allains book he actually writes it word for word like it is on line 33 he must have made a mistake in the book how come mixing up the order of those two makes such a huge difference?

[adam2016]

anyone know why mixing them up made such a huge difference ?

[Duthomhas]

Books are notoriously flawed. Good books are reviewed by several people who can fix those kinds of problems. But even then, some do slip through.


BTW, this is a selection sort, not an insertion sort.


The basic idea is this: an array has n elements, indexed 0 to n-1.

     0   1   2   3   4
    [5] [3] [2] [1] [4]     

Sort has an index variable i that counts through those values.

Initially i equals 0, so we'll find the smallest value in the entire array with findSmallest(aray,i,5) and swap it with the item at i:

     0   1   2   3   4
    [5] [3] [2] [1] [4]
     ↑           ↑
     i           smallest   

     0   1   2   3   4
    [1] [3] [2] [5] [4]     

Notice that at this point, every element of the array with index ≤ i is already sorted.

     0 │ 1   2   3   4
    [1]│[3] [2] [5] [4]     
sorted │

Let's increment i (so now it is equal to 1) and continue by finding the smallest value in the remainder of the array (from i to the end) with findSmallest(aray,i,5) and again swap it with the item at i:

     0   1   2   3   4
    [1] [3] [2] [5] [4]     
         ↑   ↑
         i   smallest   

     0   1   2   3   4
    [1] [2] [3] [5] [4]     

Again, notice that you now have sorted (x≤i) and unsorted (x>i) sections:

     0   1 │ 2   3   4
    [1] [2]│[3] [5] [4]     
    sorted │

Again, increment i and repeat. This time we find that i and findSmallest(aray,i,size) have the same value, so we swap the element at index 2 with itself (which changes nothing). Nevertheless, we are guaranteed that the elements (x≤i) are all properly sorted.

     0   1   2   3   4
    [1] [2] [3] [5] [4]     
             ↑
             i,smallest   

     0   1   2   3   4
    [1] [2] [3] [5] [4]     

     0   1   2 │ 3   4
    [1] [2] [3]│[5] [4]     
        sorted │

And again:

     0   1   2   3   4
    [1] [2] [3] [5] [4]     
                 ↑   ↑
                 i  smallest

     0   1   2   3   4
    [1] [2] [3] [4] [5]     

     0   1   2   3 │ 4
    [1] [2] [3] [4]│[5]     
            sorted │

This is where your algorithm should stop -- as the final element will always be the largest one left. But it doesn't because i<size, so we'll increment i and repeat, swapping the final element with itself:

     0   1   2   3   4
    [1] [2] [3] [4] [5]     
                     ↑
                  i,smallest

     0   1   2   3   4
    [1] [2] [3] [4] [5]     

     0   1   2   3   4 │
    [1] [2] [3] [4] [5]│    
                sorted │

(If you want to end early, make sure sort() makes i from 0 to size-1.)


You can see a nice animation at the FAQ page on selection sort:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/selection-sort/


Hope this helps.

[adam2016]

thanks for the help much appreciated I'm going to study that =)

just one question though how come the order mattered on line 33?

int index = findSmallest(aray,size,i);

[adam2016]

I tried redoing the code without looking at it for practice but when I redone it I don't get exactly what I am looking for the numbers seem to be jumbled quite randomly this time here is what I wrote

#include <iostream>

using namespace std;

void swapRay(int aray[],int fIndex,int sIndex){

     int temp;
     temp = aray[fIndex];
     aray[fIndex] = aray[sIndex];
     aray[sIndex] = temp;

}

int findSmallest(int ray[],int index,int size){

     int smallest = index;

     for(int i = index+1;i < size;i++){

        if(ray[i] < ray[smallest]){

            smallest = i;
        }

     }
         return smallest;
}

void sort(int ray[],int size){

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

       int index = findSmallest(ray,0,size);
       swapRay(ray,i,index);

    }

}

int main()
{
     int ray[4];

     for(int i = 0;i<4;i++){
     cout << "enter vales" << endl;
     cin >> ray[i];
     }


     cout << findSmallest(ray,0,4) << endl;
     sort(ray,4);

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

        cout << ray[i] << endl;

     }
}

lets say if I input 2,4,5,1

I get the output
4
5
2
1

it's almost like they have now been mixed randomly,why is my code doing that to me I'm so confused =(

[adam2016]

I figured out why I was getting that output changed 0 to i on line 34