Not sure if this is an Insertion Sort or...

[Khatzu]

I've been struggling so understand algorithms. I tend to write my own code based on spoken instructions or visual cues rather than pseudo code, which usually leaves me hopelessly confused.

Well, after hours of failing around I came up with this monstrosity after struggling to wrap my head around the Insertion Sort:

#include <iostream>
#include <array>
#include <algorithm>

using namespace std;

int main()
{
	const int arraySize = 5;
	
	int anArray[arraySize];

	for (int m = 0; m < arraySize; m++)
	{
		cout << "Enter a number: ";
		cin >> anArray[m];
		cout << endl;
	}
	
	int cPos = 0; // Current position in the array (one in front)
	int nPos = 0; // Last position in the array (behind current)

	for (cPos = 1; cPos < arraySize; cPos++)
	{
		nPos = cPos - 1; // Always makes sure nPos is behind cPos
		while (nPos >= 0 && anArray[cPos] < anArray[nPos]) // Is triggered when the front number is less than the rear, as long as the rear number is >= 0
		{
			swap(anArray[cPos],anArray[nPos]);
			cPos--; // Decrement the index position of cPos
			nPos--; // Decrement the index position of nPos
		}
	}


	cout << "Values sorted: \n";

	for (int n = 0; n < arraySize; n++)
	{
		cout << anArray[n] << " ";
	}

	cout << "\n\n";

	system("pause");
	
	return 0;
}

I'm not sure if this is a good implementation. I looked at tutorials, articles, and videos all over the web. The code looks sort of similar to mine, and they seem to accomplish the same thing (at least, I think so). Any comments regarding your thoughts would be much appreciated.

[Peter87]

I think it sorts correctly but it is a bit inefficient. You should not decrement cPos in the loop because then you will have to scan some of the sorted elements again unnecessary. Instead of using swap you can store the value of anArray[cPos] before the inner loop and just move the values one position higher and after the loop you can just assign the stored value to anArray[nPos].

You should practice to read pseudocode because pseudocode is often easier to read to understand the algorithm because it doesn't care about all the implementation details that often differ between different languages. The pseudocode at http://en.wikipedia.org/wiki/Insertion_sort at the end of the Algorithm section is quite clear.

[jwroblewski]

int main()
{
cout << "\t\t\tPancake Analyzer!!" << endl;

int pancakes[9],i=0,j=0,max=0;

while(i<10)
{
   cout << "Enter how many pancakes person number " << i+1 << " ate: " << endl;
   cin >> pancakes[i];
   i++;
};

for(i=0;i<10;i++)
{
   for(j=0;j<10;j++)
   {
      if(pancakes[j]>pancakes[max])
         max=j;
   };
   cout << "Person " << max+1 << ": " << pancakes[max] << " pancakes!" << endl;
   pancakes[max]=0;
};


return 0;
}

here is a code sample of mine that insertion sorts a list and outputs to the screen.... could easily push into new array instead

[Peter87]

jwroblewski, what you have there is not insertion sort. Also the size of the pancakes array is one too small.