C++ Insertion Sort with Arrays

Page 1 of 1

7 Replies - 33136 Views - Last Post: 29 January 2011 - 05:34 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=212475&amp;s=39aed89220a3dbf5e4a3179b00b0f61c&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 JerseyDevil101

Reputation: 1
• Posts: 58
• Joined: 27-January 11

C++ Insertion Sort with Arrays

Posted 27 January 2011 - 06:15 PM

Hello guys this is my first post on these forums, and I'm a bit stuck as to what to do with this program.

- I need to create an insertion sort within an array of integers. These integers are drawn from a random integer from a range (0,499). The integer will be inserted in the correct position of the array and sorted.

This next step is where I'm having trouble understanding it.
-Insert 100 integers into the array (one per iteration), which will begin with a size of 1. When the
array is fi lled up, a new array of twice the size is created and the contents of the existing array is copied into the new array and the algorithm will continue.

For example the output will give me a sorted array with 1 element and print out that value as the output. I will then increase this array by 2*(the last array size) until it reaches 128 elements.

I'm am able to implement the 100 integers and sort it to correctly output the contents. I'm just not sure how I would copy an array and display 1 element or 2 elements or 4 elements etc.. Each time it iterates.

I hope this makes sense please ask if i need to clarify something.

```#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int main()
{
srand((unsigned)time(NULL));
int i, key;
int num[100] = {0};

cout << "Unsorted Array:" << endl;

for (i=1; i<101;i++)
{

num[i] = (rand())%499;
cout << i << ":" << num[i] << endl;
}
for (int j=1; j<101; j++)          //Insertion Sort
key = num[j];
while (i>=0 && num[i]>key)
{
num[i+1] = num [i];
i--;
}
num[i+1] = key;
}
cout << endl << "Sorted Array:\t" << endl;
for (i=1;i<101;i++)
{
cout << i << ":" << num[i]<< endl;

}
int newArray[1] = {0};
return 0;
}

```

Thanks guys. I may be thinking too hard on this. From what I can understand I have to create a for loop that will keep going until there's 128 elements. This first array only has 1 element and is displayed and the next element displays the 2 elements. I can't seem to figure out how to copy the first array into this new array because I keep getting index out of bounds error since the array size can't support it.

Is This A Good Question/Topic? 0

Replies To: C++ Insertion Sort with Arrays

#2 eker676

• Software Engineer

Reputation: 379
• Posts: 1,833
• Joined: 18-April 09

Re: C++ Insertion Sort with Arrays

Posted 27 January 2011 - 06:27 PM

Arrays are ZERO based in C++. You are trying to access an element at the index 100. However your array only contains indices from 0-99.

As for creating a new array every time. Sounds stupid to me. Just populate the array with random numbers and sort in place.

The wikipedia page actually has a nice explanation.
http://en.wikipedia..../Insertion_sort

If this is an assignment could you post the exact text because I'm not really understanding "display 1 element or 2 elements or 4 elements".

#3 JerseyDevil101

Reputation: 1
• Posts: 58
• Joined: 27-January 11

Re: C++ Insertion Sort with Arrays

Posted 27 January 2011 - 06:32 PM

sure.

You will implement a simple variant of an insertion sort within an array of integers; integers will be drawn from a
random number generator (use java.util.Random in Java, or drand48() in C++), with values scaled to the range
(0, 499). The drawn integer will be inserted into its correct position in the array, after shifting all the elements
from the insertion point onwards by 1 position.
You will insert 100 integers into the array (one per iteration), which will begin with a size of 1. When the
array is lled up, a new array of twice the size is created and the contents of the existing array is copied into the
new array and the algorithm will continue.

Input: 100 Integers from a random number generator, scaled between 0 and 499, duplicates are ok.
 Output: Each time the array is lled up, you will output the array contents, and a string indicating the
new size; your nal output will look like this:
Sorted Values[1]: 4
Array Size Increased to 2 values.
Sorted Values[2]: 4 18
Array Size Increased to 4 values.
Sorted Values[4]: 4 18 22 30

#4 eker676

• Software Engineer

Reputation: 379
• Posts: 1,833
• Joined: 18-April 09

Re: C++ Insertion Sort with Arrays

Posted 27 January 2011 - 07:07 PM

What I don't get is why you need two arrays. It overcomplicates the problem.

I could write the program but then you don't learn anything and I'm don't feel like thinking right now.

Try using two arrays, arrayOne, and arrayTwo. They will have to be dynamic
```int* arrayOne = new int[size];
int* arrayTwo = new int[size*2];
```

When arrayOne is filled. Recreate two and copy in the elements. Then Recreate arrayOne to be twice the size of arrayTwo. Fill up arrayTwo. Copy back to arrayOne. REPEAT.

Write some code. If you have problems just post them.

#5 JerseyDevil101

Reputation: 1
• Posts: 58
• Joined: 27-January 11

Re: C++ Insertion Sort with Arrays

Posted 27 January 2011 - 07:13 PM

Ok thanks that actually really clears things up for me I think I can do it now. I was thinking of something completely different. I haven't done any c++ in about a year so I'm a bit rusty. I have no idea why i created the array like that before where the index was out of bounds I completely forgot about the index starting at 0.

#6 JerseyDevil101

Reputation: 1
• Posts: 58
• Joined: 27-January 11

Re: C++ Insertion Sort with Arrays

Posted 29 January 2011 - 03:55 PM

Ok I finished the code. I was wondering if this is the ideal way of doing it or not. If you guys can point me in the right direction that would be great. My code compiles and does what it needs to do, but I'm just thinking if there's a better way to do it.

```//Include preprocessors for print statements, random, and standard library.
#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

//function prototypes.
int populate(int array[], int limt);
void spit(int array[], int n);
void ins_srt(int array[],int length);

int main()
{
srand((unsigned)time(NULL)); //used to create a new random seed.
int *array1; //first dynamic array is created.
int *array2; //second dynamic array is created.

//declare and initialize variables.
int i=0;
int n=1;

array1= new int[100]; //creates a new array with a size of 100 (0-99).
array2 = new int[n]; //creates a new array with a size of n

populate(array1,100); //calls the populate function.
ins_srt(array1,100); //calls the ins_srt function to sort array1.
cout << "The 100 integers are: " << endl; //prints this line to console.
spit(array1,100); //calls the spit method for array 1.
array2=array1; //copies the contents of array1 to array2.

for(int n=1; n<=128; n)
{
cout <<"\nSorted values [" << n << "]: " << endl; //prints out what n is.
spit(array2,n);//calls spit function for array2 with n elements.

//if loop to determine if the array should increase.
if(n<128)
{
cout <<"\nThe array has increased to " << n*2 << endl; //prints out that the array has increased.
}
n=n*2; //n is multiplied by 2 everytime the loop iterates.
}

return 0;
}

//creates a function, populate that takes an array and an integer as parameters.
int populate(int array[], int limit)
{
//declares variables inside populate function.
int temp;
int i;
//for loop that will iterate and populate an array with random numbers.
for(i=0;i<limit;i++)
{
temp = rand()%499; //the temp variable is equal to a random number(0-499).

/*each time the for loop iterates it copies the temp variable into the
array to the ith position.*/

array[i] = temp;
}
return i; //returns i.
}

//function that will print out an array's contents.
void spit(int array[], int v) //takes an array and an integer as parameters.
{
//for loop that will iterate until it's greater than v variable
for(int i=0;i<v;i++)
{
cout  << array[i] <<" "; //prints out what is in array at position i.
}
cout << endl; //endls the line.
}

//function that will sort an array by insertion sort.
void ins_srt(int array[],int len) //takes an array and an integer as paramters.
{
//declare local variables.
int n,i;

//for loop that will start at 1 until it's greater than len
for(int j=1;j<len;j++)
{
n=array[j]; //n = to w/e is in array[j]'s position at the time. holding place.
i=j-1; //holding place for i to determine what value was before j.

//while loop that will run when contents of array[i] is greater than variable n.
// and when i is greater than or equal to 0.
while(array[i]>n && i>=0)
{
array[i+1]=array[i]; //takes contents of position i and moves it up by 1.
i--; // increments to i-1.
}
array[i+1]=n; //sets array in position i to w/e is in n and moves it up 1 position.
}
}

```

Thanks guys

#7 eker676

• Software Engineer

Reputation: 379
• Posts: 1,833
• Joined: 18-April 09

Re: C++ Insertion Sort with Arrays

Posted 29 January 2011 - 05:24 PM

If it works and the teacher says it looks fine then I wouldn't change it.

Overall, I'd say the code looks nice enough. Some of your comments explain the obvious though.

```// takes an array and integer as parameters
// endls the line
// decrements i-1

```

In a class setting this may be what your teacher wants. However, in the real world, a comment at the beginning of the function explaining what it does and a comment by tricky blocks of code will usually suffice. Maybe a comment for variables that are used often would be good as well.

#8 JerseyDevil101

Reputation: 1
• Posts: 58
• Joined: 27-January 11

Re: C++ Insertion Sort with Arrays

Posted 29 January 2011 - 05:34 PM

Thanks for the help. Yea I wrote those comments like 3 in the morning so I wasn't really paying attention to what they were. I just wanted to know the logic to what I was writing before I went to bed.