problem in Insertion_Sort

[kbiyer]

I copied this progrm from "Jumpin into C++" by Alex Allain.However when icopied the whole and ran the progrm an error is coming- undefined refrence to -findSmallestremaingElement in -Int index. could some one help me with this. no other error is shown.thanks

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
int findSmallestRemainingElement (int array[], int size, int index);
void swap (int array[], int first_index, int second_index);
void sort (int array[], int size)
{
for ( int i = 0; i < size; i++ )
{
int index = findSmallestRemainingElement( array, size, i );
swap( array, i, index );
}

[ne555]

You are supposed to implement that function
The algorithm isn't insertion sort but selection sort

[jahanzaib ali khan Iiu]

The Function Used Above For Sorting Is False:I could Help you bit By Giving You the correct Function of Sorting and Function Of Swapping which is USed in Sorting Which Will Help You.


1.Function For Sorting:

void sort(int m[],n)
{
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(m[i]>m[j])
swap(m[i],m[j]);
}

2.Function Of Swapping:

void swap(int&a,int&b)
{
int temp;
temp=a;
a=b;
b=temp;
}

[ne555]

You are swapping too much ;)
selection sorts only needs O(n) swapping of the elements

[Cubbi]

Nice illustration of a book that teaches C while pretending it has something to do with C++.

Finishing your program using C++ gives:

#include <iostream>
#include <algorithm>
using namespace std;

int findSmallestRemainingElement (int array[], int size, int index)
{
    return min_element(array+index, array+size) - array;
}

void swap (int array[], int first_index, int second_index)
{
    swap(array[first_index], array[second_index]);
}

void sort (int array[], int size)
{
    for ( int i = 0; i < size; i++ )
    {
        int index = findSmallestRemainingElement( array, size, i );
        swap( array, i, index );
    }
}

demo: http://ideone.com/t79zd

Writing it using C++ from the start, gives

#include <iostream>
#include <algorithm>
using namespace std;

template<typename Iter>
void select_sort (Iter beg, Iter end)
{
    for(Iter i = beg; i != end; ++i)
        iter_swap(i, min_element(i, end));
}

demo: http://ideone.com/blC0t

(and yes, it's known as selection sort)