Use Vector to do Insert Sort

[dannytoy]

Hello,

I am a newbie of C++, who has some experience in Java. I just finished my first C++ book and am doing some exercises for beginners.

I am trying to write an insert sort method using Vector. Following is my code. My IDE, Netbean 7, just simply says "Run Failed". In the Main() function, it works fine till line 53.

I was trying to use wildcard/templates too. But.. er... it didn't work.

Please advise. Thank you.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;


//template <class T>
vector<int> insertSort(vector<int> array){
    unsigned int i, j;
    vector<int> sortedArray;
    int max;
    
    for(i = 0; i<array.size();i++){
        max = array[i];
        
        for(j = i; j<array.size();j++){
           max = array[j] > max ? array[j]:max;  
              
        }
        
        sortedArray[i] = max;
    }
    
    return sortedArray;
}


int main() {

   srand(time(NULL));
   int element;
   unsigned int i; 
    
   vector<int> nums;
   
   for(i = 0; i < 10; i++){
       
       element = rand()%10 + 1;
       nums.push_back(element);
   }
       
   
   
   cout<<"The array before sorting: ";
           
   for(i = 0; i<nums.size(); i++){
       cout << nums[i] << " ";
   }
 
   
   vector<int> sortedNums = insertSort(nums);
   
   cout<<"The array after sorting: ";
           
   for(i = 0; i<sortedNums.size(); i++){
       cout <<  sortedNums[i];
   }
     
   return 0;
}

[D80DSL3A]

It's crashing because you forgot to reserve space in sortedArray:
Fix = replace line 12 with vector<int> sortedArray( array.size() );
BTW array is a keyword, consider renaming this.

This fix allows the program to run, revealing that the sort doesn't work.
Can you see why?

[dannytoy]

Thank you very much fun2code.

I am still unfamiliar with most of C++ syntax. I kind of remembered vector didn't need to reserve space when declared. I have modified it and it works, better works as I decided. I am not sure if it is the best way to do it (probably not). But I learn!

Thank you.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;


template <class T>
//vector<int> insertSort(vector<int> arr){
vector<T> insertSort(const vector<T> &arr){
    
    unsigned int i, j;
    
    vector<T> sortedArray(arr.size());
    sortedArray = arr;
    
    int max;
    
    for(i = 0; i<arr.size();i++){
        //max = arr[i];
        
        for(j = i; j<arr.size();j++){
           if(sortedArray[i] < sortedArray[j]){
               T tmp;
               tmp = sortedArray[i];
               sortedArray[i] = sortedArray[j];
               sortedArray[j] = tmp;
           }  
              
        }
        
        //sortedArray[i] = max;
    }
    
    return sortedArray;
}


int main() {

   srand(time(NULL));
   int element;
   unsigned int i; 
   //int i;
   
   vector<int> nums;
   
   for(i = 0; i < 10; i++){
       
       element = rand()%10 + 1;
       nums.push_back(element);
       //nums[i] = element;
   }
       
   
   
   cout<<"The array before sorting: ";
           
   for(i = 0; i<nums.size(); i++){
       cout << nums[i] << " ";
   }
 
   
   vector<int> sortedNums = insertSort(nums);
   
   cout<<"The array after sorting: ";
           
   for(i = 0; i<sortedNums.size(); i++){
       cout <<  sortedNums[i] << " ";
   }
     
   return 0;
}

[D80DSL3A]

You're welcome. Glad you got it working.

A couple of more suggestions...
1) If you pass nums to insertSort() by value (as in your 1st version) instead of by reference then you already have a local copy (arr). You could sort arr without affecting nums and return arr. This eliminates the local sortedArray vector.

2) It looks like your sort function works but there is more swapping being done than necessary.
In the inner loop you want to find the max array element then swap it with arr[i] afterward (in the outer loop).
Your function swaps each element found to be > arr[i] with arr[i] along the way in the inner loop.

This is what I got:

template<class T>
vector<T> insertSort(vector<T> arr){
    int maxIdx;    
    for(unsigned int i = 0; i<arr.size()-1;i++){
        maxIdx = i;        
        for(unsigned int j = i+1; j<arr.size();j++)
           if(arr[j] > arr[maxIdx])
			   maxIdx = j;

        // swap values
        if( maxIdx != i ){
			T temp = arr[i];
			arr[i] = arr[maxIdx];
			arr[maxIdx] = temp;
		}
    }    
    return arr;
}

[dannytoy]

Thank you, fun2code.

Yes you are right. Using index to record the place and swapping only once is much more efficient.

In terms of point one, mostly I am still using the java pattern. means, I am more comfortable to use Pass By Reference. (another symptom is to think vector = arraylist, so it doesn't need to be reversed space)

I was also thinking:

1.The textbook says (forgive me for saying that), pass-by-reference can be more efficient b/c it doesn't copy the whole array. I think this suggestion doesn't hold here because I do need a copy of the whole array. Am I right?

2. I kind of thought, if I don't make another copy, I would change the argument, the original arr.

3. I am still struggling with the & and const syntax...

[LB]

1. Yes, if you pass by reference and then make a copy of it anyway, it's the same as passing by copy and not making a copy of it. Parameters not passed by reference are generally thought of as local function variables because what happens to them in the function stays in the function, just like Vegas.
2. Yep, as said above it's just a local variable if not passed by reference.
3. const means it can't change (similar to final in Java), and the & sign has multiple meanings depending on usage. In this case it's a reference variable, eg:

int x = 7;
int y = x;
int &z = x;
z = 3;
cout << "x = " << x << endl << "y = " << y << endl << "z = " << z << endl;

[D80DSL3A]

We could eliminate another copy operation by passing both vectors to inserSort() by reference.
I pass nums by constant reference because I don't wish to change it.
We're down to one copy operation now. The copy occurs in the function.

#include <ctime>
#include <vector>
#include <iostream>
using namespace std;

template<class T>
void insertSort(const vector<T>& source, vector<T>& target)
{
    target = source;// the single copy operation
    int maxIdx;    
    for(unsigned int i = 0; i<target.size()-1;i++)
    {
        maxIdx = i;        
        for(unsigned int j = i+1; j<target.size();j++)
           if(target[j] > target[maxIdx])
	         maxIdx = j;

        // swap elements
        if( maxIdx != i )
	{
		T temp = target[i];
		target[i] = target[maxIdx];
		target[maxIdx] = temp;
	}
    }    
    return;
}

int main()
{
   srand(time(NULL));
   unsigned int i;
   
   vector<int> nums;
   
   for(i = 0; i < 10; i++)
       nums.push_back(rand()%10 + 1);   
   
   cout<<"The array before sorting: ";           
   for(i = 0; i<nums.size(); i++)
       cout << nums[i] << " ";

   vector<int> sortedNums;
   insertSort( nums, sortedNums );// passing both by reference
   
   cout<<endl<<"A sorted copy of the array: ";           
   for(i = 0; i<sortedNums.size(); i++)
       cout <<  sortedNums[i] << " ";   

   cout << endl;
   return 0;
}

[Osmar]

Hello everyone!
This is my very first post and I don't want to be obnoxious right away. Your codes are all fine. The one i'm posting next is just for illustration purposes on some new features of C++ (C++0x: well in march the standard at long last reached FDIS (Final Draft international Standard) status so we can call it C++11 or C++0B :) ) and how such features can reduce coding... So I hope u find it at least informative.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

template<typename Container>
Container insert_sort(const Container &con) 
//Not really insert sort; it depends on the implementacion of the sort algorithm
//in algorithm header. What I wanted to show with this is code reuse
//note that type Container can be any container i.e vector, deque that supports
//bidirectional iteratios. Note also that with this construct u cam pass 
// vector<int>, vector<double>, etc without needing to overload the function for
//each posible data of your container

{
	Container con_copy = con;
	sort(con_copy.begin(), con_copy.end()); // find sort in algorithm header
	return con_copy;
}

int main()
{      //in C++ is always prefered 0 instead of NULL, but nullptr is the way to do it for the
        //new standard
	srand(static_cast<unsigned>(time(nullptr))); 

	vector<int> nums;

	for(int i(0); i < 10; ++i)
		nums.push_back(rand()%10+1);

	cout << "Vector before sorting!" << endl;
	for(auto it = nums.begin(); it != nums.end(); ++it)
		cout << *it << ' ';
        //auto is a new keyword for type deduction
	auto nums_copy = insert_sort(nums);

	cout << "\nVector after sorting!" << endl;
	for(auto it = nums_copy.begin(); it != nums_copy.end(); ++it)
		cout << *it << ' ';

}

Any question, comments so welcomed.