Insertion Sort of an Array

[WakeofMisery]

I am given instructions to "Write a sort function that takes an array and sorts the values." I believe I have the gist of it here, but I forced myself to increment 'i' even further (i++) within the loop instead of letting it do its thing in order to allow the algorithm to work. I'm thinking I can just get rid of my FOR LOOP and increment 'i' a second time in the first WHILE LOOP? What do you guys think? I'm trying to create an insertion sort algorithm.

  #include <iostream>
using namespace std;

int main() 
{
	int input, size, temp1, temp2;
	int *arr;
	cout << "Please enter your desired array size: " << endl;
	cin >> size;
	arr = new int[size];
	for (int i = 0; i < size; i++) 
	{
		cout << "Please enter your array values: " << endl;
		while (i < size)
		{
			cin >> input;
			arr[i] = input;
			temp1 = arr[i];
			i++;
			cin >> input;
			arr[i] = input;
			temp2 = input;
                 }
			while (i > 0 && arr[i - 1] > arr[i])
			{ //If first number is larger than second number, insert second number infront of first number. Second number = first number's index value, First number = second number's index value.
			  /*delete[] arr;*/
				arr[i] = temp1;
				arr[i - 1] = temp2;
			}
			cout << "The value at index " << i - 1 << " is " << arr[i - 1] << endl;
			cout << "The value at index " << i << " is " << arr[i] << endl;
		//}
	}
	system("pause");
	return 0;
}

[2UD8vCM9]

I think you're approaching this the wrong way. Your instructions are to write a sort function that takes an array and sorts the values. I would recommend using an approach like this and all you have to do from here is figure up the logic that needs to go into the SortArray function.

#include <iostream>
using namespace std;

void SortArray(int * arr, int size)
{
	//Sort Logic here
}

int main()
{
	int input, size;
	int *arr;
	cout << "Please enter your desired array size: " << endl;
	cin >> size;
	arr = new int[size];

	cout << "Please enter your array values: ";
	for (int i = 0; i < size; i++)
	{
		cin >> arr[i];
	}

	SortArray(arr, size); //Call function to sort array

	for (int i = 0; i < size; i++)
	{
		cout << "The value at index " << i << " is: " << arr[i] << endl;
	}

	delete[] arr; //<--Call delete when we are done using the memory since we used new to allocate that memory. If we don't clean up the memory, we will have a memory leak.
	system("pause");
	return 0;
}

Let me know if you're still confused.

Edit: Just read you were expected to use an insertion sort algorithm.

Try to mimic this logic

void insertion_sort (int arr[], int length){
	 	int j, temp;
		
	for (int i = 0; i < length; i++){
		j = i;
		
		while (j > 0 && arr[j] < arr[j-1]){
			  temp = arr[j];
			  arr[j] = arr[j-1];
			  arr[j-1] = temp;
			  j--;
			  }
		}
}

I obtained that code from http://cforbeginners.com/insertionsort.html if you need a reference. I didn't verify that this code worked.

[keskiverto]

You have forgotten this part: "Write a function that takes an array".
You have everything in the main() and you interlace input with sorting.


The code below is irrelevant to the sorting, but emphasizes "other things to remember":

#include <iostream>
int main() {
  int size = 0;
  if ( std::cin >> size && 0 < size ) { // input can fail
    int * arr = new int [size]; // I would use std::vector

    // input
    int value = 0;
    int index = 0;
    while ( index < size && std::cin >> value ) {
      arr[index] = value;
      ++index;
    }

    // sort
    // call here the sort function that you will write

    // show result
    for ( int i = 0; i < index; ++i ) {
      std::cout << ' ' << arr[i];
    }
    std::cout << '\n';

    // deallocate what you have allocated
    delete [] arr;
  }
  return 0;
}

Once you have the sorting (and only the sorting) in separate function we can look at it in more detail.

[WakeofMisery]

You both have a point about the separate function... I will code the algorithm in a separate function and call it within main. So, as both of you are saying, I am to deallocate the memory of the array at the end of the program, right before it returns 0... To prevent memory leaks. I don't fully understand why there would potentially be a memory leak when the program deletes it upon exit, right?


EDIT: WOW. I was so close looking at it now... My algorithm that I had originally written for my sorting was:

temp1 = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp1;

All I needed to do was put this in a separate function, create a variable 'j', and decrement it so that the loop continues??? The frustration is real.

Also, I appreciate the help a lot. You've made me realize how much easier this was than what I was doing... I created too many variables and the actual program requires much less lines of code than expected. Thanks guys!


I have another program that I coded last week and was wondering if you guys would be willing to help me with it as well. The issue that I'm having with this one is that it randomly triggers breakpoints after '-1' is entered, or even sometimes when just inputting values into array indexes.

//Objective:  Create an array of numbers based upon user input.
//
//	Program logic :
//			Ask the user for how big to initially size the array. CHECK
//			Create an array based upon that size. CHECK
//			Ask for a number, insert that number into the next unused place in the array. CHECK
//			Repeat inserting and resizing the array as needed or until they enter -1 for the number. CHECK
//			Print the list. CHECK

#include <iostream>

using namespace std;

int main() {
	int size, num = 0, inc = 0;
	int *arr;
	cout << "Please enter your desired array size: " << endl;
	cin >> size;
	arr = new int[size];
	cout << "Please enter your array index values: " << endl;

	while (num != -1) {
		cin >> num;
		if (num == -1) {
			int x = 0;
			for (x; x < inc; x++) {
				cout << "The value stored at index " << x << " is: " << arr[x] << endl;
			}
		}

		else {
			arr[inc] = num;
			inc++;
			if (inc == size) {
				size += size;
				cout << "The size of your array is now: " << size << endl;
			}
		}
	}
	delete[] arr;
	system("pause");
	return 0;
}

[keskiverto]

Again, keep things simple. You have your output inside the input loop. Do one thing at a time. First all input, then output.

Your real problem is at line 35. It does not resize the dynamically allocated array. It simply changes the value of variable size.

Furthermore, your attempt to resize after the current array is full, but before you know whether you need any more space.

// input
while ( std::cin >> num && -1 != num ) {
  // append num to array
}

// output
for ( int x=0; x < inc; ++x) {
  std::cout << "The value stored at index " << x << " is: " << arr[x] << '\n';
}