Can someone help me with a Recusive Insertion Sort problem
Hello there, before you say it I know, pointless!
I have been asked to write two insertion sort functions.
One that uses Iteration and another that uses Recursion, At first I had no problems writing the function in its iterative form, as you can see if you compile the code.
However Im having difficulty trying to write the recursive function.. I just cannot get my head around the function as a whole. I understand I have to call the function in itself.. but from there I kinda get lost. :(
I have been working on this for the past few days, I have asked the tutor for help however when he explained it to me I thought i had it.. once I got home however and went to write it.. I made a mess of it and im completely lost once again!
here is my code, if there is anyone that can point me in the right direction or maybe show me how to do this with pseudo code that would be greatly appreciated! I want to learn how to do this.. so I know for myself!!!!
the problem function is at the bottom of the code :)
Code:
////////////////////////////////////////////////////////////////////////////////
//
// Author:
// name: #######, ID Number: #######
// Year: 2008, Course: #######
//
// Program Name:
// Description:
//
////////////////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
//constant size N used on arrays
const int N = 10;
//Prints author details
void detials (void);
/*printArray prints the values of the array sorted by ether the
insSortItr fuction or the insSortRec function*/
void printArray (int dat[], int n);
/*insSorItr sorts data in ascending order of the array
[a[first]...[last]] using itteration (while and for loops).*/
void insSortItr (int a[], int first, int last);
/*insSortRec sorts data in ascending order of the array
[a[first]...[last]]using recursion.*/
void insSortRec (int b[], int c[], int index, int len);
int main (){
// array of numbers to sort for the insSortItr function
int dataA[N] = {26,5,26,1,61,11,59,15,11,19};
/* array of unsorted numbers that insSortRec function will read
and sort into final array */
int dataB[N] = {26,5,26,1,61,11,59,15,11,19};
/*final will be the final sorted array of numbers from dataB unsortted
array, they will be sorted by the recursive insSortRec insertion sort
function and stored*/
int final[N];
/*final will be the final sorted array of numbers from dataB unsortted
array, they will be sorted by the recursive insSortRec insertion sort
function and stored*/
detials ();
insSortItr (dataA,0,N);
cout << "After iterative insertion sort finished:\n";
printArray (dataA,N);
cout << "\n\n";
cout << "Part B: Initial array:\n";
printArray (dataB,N);
cout << "\n\n";
insSortRec (final,dataB,0,N);
//cout << "After recursive insertion sort finished:\n";
//printArray (final,N);
//end - clearscreen
}
//////////////////////////////////////////////////////////////////////
//////////////// voids functions
//////////////////////////////////////////////////////////////////////
//A fuction that displaying all Author names and Ids
void detials(void){
cout << "159.201 Assingment 1\n";
cout << "Smith C, ID:07199104\n\n";
}
/* PrintArray function prints the array values supplied to it
when calling it at any time*/
void printArray (int dat[], int n){
for (int k = 0; k < n; ++k){
cout << dat[k] << " ";
}
}
/*iterative insertion sort - insSortItr takes array input value
iterates through the loop preforming insertion sort algorithum
and printing values out at each itteration using the printArray
function*/
void insSortItr (int a[], int first, int last){
cout << "Part A: Initial array:\n";
printArray(a,last);
cout << "\n\n";
for (int j = first+1 ; j <=last ; ++j){
int kti = a[j];
int i = j-1;
//cout << a[1] << "\n";
while (i >= first && a[i] > kti){
a[i+1] = a[i];
i = i-1;
a[i+1] = kti;
}
printArray(a,last); // displays content of a each iteration
cout << "\n";
}
cout << "\n";
}
//recursive insertion sort - insSortRec
//display all intermediate results
void insSortRec (int b[], int c[], int index, int len){
int temp = c[index];
/* need to figure out how to insert contence in temp
into the final array then display it like insSortItr*/
if(index < len -1){
index++;
insSortRec(b,c,index,len); // This is the recursive part
}
//printArray (c,N);
//cout << "\n";
}
