error: expression must have a class type

[2kaud]

My new problem is with my bubble sort function

I'm not quite sure how your bubble sort is supposed to work but a simple implementation of a bubble sort is

void bubbleSort(int arr[], int n)
{
	for (size_t i = 0; i < n - 1; ++i)
		for (size_t j = 0; j < n - i - 1; ++j)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

There is also a 'modified bubble sort' which uses a flag to indicate whether a swap has happened or not and terminating if no swap occurred.

void bubbleSort(int arr[], int n)
{
bool swapped = true;

	for (size_t i = 0; swapped & i < n - 1; ++i) {
		swapped = false;
		for (size_t j = 0; j < n - i - 1; ++j)
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
				swapped = true;
			}
	}
}

The outer for loop can also be replaced with a simple do loop with swapped as the termination condition

void bubbleSort(int myarr[], int n)
{
bool swapped;

	do {
		swapped = false;
		for (size_t i = 0; i < n - 1; ++i)
			if (myarr[i] > myarr[i + 1]) {
				swap(myarr[i], myarr[i + 1]);
				swapped = true;
			}
	} while (swapped);
}

[2kaud]

Exactly. Notice that the two examples are effectively the same: other than in the first line, every instance of the name arrCopy from example 1 has been substituted with arrOrg in example 2, and every instance of the name arrOrg from example 1 has been substituted with arrCopy in example 2. There is no substantive difference in the algorithm, but rather the difference lies in what you name arrOrg and what you name arrCopy, but you could have very well named them x and y instead.

Yes.

[2kaud]

Your insertion sort seems overly complicated. Try

void insertionSort(int myarr[], int n)
{
	for (size_t i = 1; i < n; ++i)
		for (size_t j = i; j > 0 && myarr[j - 1] > myarr[j]; --j)
			swap(myarr[j], myarr[j - 1]);
}

[UncleBazerko]

I'm not quite sure how your bubble sort is supposed to work but a simple implementation of a bubble sort is

void bubbleSort(int arr[], int n)
{
	for (size_t i = 0; i < n - 1; ++i)
		for (size_t j = 0; j < n - i - 1; ++j)
			if (arr[j] > arr[j + 1])
				swap(arr[j], arr[j + 1]);
}

That worked beautifully, but could you please explain these two statements?

[laserlight]

The comparison should be quite simple: at the core of bubble sort is the comparison of adjacent elements, and that comparison does precisely that.

The loop condition might be a little harder to understand, but what you can do is to try a few concrete examples for yourself. You will notice that the largest element gets "bubbled" to the end, and as you keep iterating, the next largest gets "bubbled" to its final place, then the one that is next largest again... therefore, you can cut down on the number of iterations.

[2kaud]

Whilst knowing the various sorting algorithms is important, the interesting part is the different number of comparisons and data swaps that the various algorithms undertake with different types of data.

Eg, for a particular set of 2000 random numbers, the results were

Selection sort
1999000 comparisons
12176 swaps

Insertion sort
1002532 comparisons
1000533 swaps

Bubble sort
3828085 comparisons
1000533 swaps
These will vary depending upon the data set

For an already sorted set,
selection sort
1999000 comparisons
0 swaps

insertion sort
1999 comparisons
0 swaps

bubble sort
1999 comparisons
0 swaps

For a sorted set in the wrong order
selection sort
1999000 comparisons
1000000 swaps

insertion sort
2000999 comparisons
1999000 swaps

bubble sort
3998000 comparisons
1999000 swaps

[UncleBazerko]

The comparison should be quite simple: at the core of bubble sort is the comparison of adjacent elements, and that comparison does precisely that.

The loop condition might be a little harder to understand, but what you can do is to try a few concrete examples for yourself. You will notice that the largest element gets "bubbled" to the end, and as you keep iterating, the next largest gets "bubbled" to its final place, then the one that is next largest again... therefore, you can cut down on the number of iterations.

Well it doesn't cut down the number of iterations. It just shortens them so that we don't unnecessarily iterate over elements that have already been sorted (bubbled) on the right hand side of the arr[] array in their final and proper place. In any case, I have a new problem:

I don't understand why it would be complaining about scope. j is already declared and initialized in the inner for loop statement of the bubble function. Here's the code again:

/*
This program observes the running time for 4 different sorting algorithms:
(Selection sort, Bubble sort, Insertion sort, Quick sort).
Author: Sam Peterson
Date Created: 04/16/2015
Date Modified: 04/xx/2015
*/
#include <cstdlib>
#include <iostream>
using namespace std;

void selectionSort(int arr[], int n, int cmpCount, int moveCount);
void bubbleSort(int arr[], int n, int cmpCount, int moveCount);
void insertionSort(int arr[], int n, int cmpCount, int moveCount);

void swap(int arr[], int low, int high);
int partition(int arr[], int low, int high, int cmpCount, int moveCount);
void quickSort(int arr[], int low, int high, int cmpCount, int moveCount);

void copyArray(int arr[], int arrCopy[], int n);
void printArray(const int arr[], int n);

int main()
{
	int arr[] = {3, 5, 4, 4, 13, 8, 2, 6, 12, 10, 17, 7, 9, 11, 1 };
	const size_t n = sizeof(arr) / sizeof(arr[0]);//should be 15
	
	int arrCopy[n];//I will need a fresh copy of array arr to test each sorting algorithm.
	
	int low = 0;
	int high = n-1;
	int cmpCount = 0;
	int moveCount = 0;
	
	cout << "\n---------------------------------------------------\n";
	cout << "Original array:";
	printArray(arr, n);	
	copyArray(arr, arrCopy, n);	
	selectionSort(arrCopy, n, cmpCount, moveCount);
	cout << "our new\n array is now sorted by the selection sort algorithm:";	
	printArray(arrCopy, n);
	cout << "\n---------------------------------------------------\n";
	
	cout << "Original array:";
	printArray(arr, n);
	copyArray(arr, arrCopy, n);
	bubbleSort(arrCopy, n, cmpCount, moveCount);
	cout << "our new\n array is now sorted by the bubble sort algorithm:";
	printArray(arrCopy, n);
	cout << "\n---------------------------------------------------\n";
	
	cout << "Original array:";
	printArray(arr, n);
	copyArray(arr, arrCopy, n);
	insertionSort(arrCopy, n, cmpCount, moveCount);
	cout << "our new\n array is now sorted by the insertion sort algorithm:";
	printArray(arrCopy, n);
	cout << "\n---------------------------------------------------\n";
	
	
	cout << "Original array:";
	printArray(arr, n);
	cout << "\n\nWill now be sorted by the quick sort algorithm:";
	copyArray(arr, arrCopy, n);
	partition(arrCopy, low, high, cmpCount, moveCount);
	quickSort(arrCopy, low, high, cmpCount, moveCount);	
	printArray(arrCopy, n);
	cout << "\n---------------------------------------------------\n";
	
	return 0;
}

void copyArray(int arr[], int arrCopy[], int n)//make a fresh copy of array arr[]
{
	for (int i = 0; i < n; i++)
	{
		arrCopy[i] = arr[i];
	}
	//cout << "\nArray arr[] copied successfully.\n";
}

void printArray(const int arrCopy[], int n)
{
	int linecount = 0;
	for (int i = 0; i < n; i++)
	{
		if (linecount % 15 == 0)
		{
			cout << endl;
		}
		cout << arrCopy[i] << " ";
		linecount++;		
	}
	//cout << "\n\nArray arr[] printed successfully.\n";
}

void selectionSort(int arr[], int n, int cmpCount, int moveCount)
{
	int smallestIndex;
	int smallest, saved;

	for (int i = 0; i < n - 1; i++) {
		// Find smallest element
		smallest = arr[i];
		smallestIndex = i;
		cmpCount++;
		
		for (int j = i + 1; j < n; j++) {
			if (arr[j] < smallest) 
			{
				smallest = arr[j];
				smallestIndex = j;
			}
			moveCount++;
		}
		// Swap with smallest element
		saved = arr[i];
		arr[i] = arr[smallestIndex];
		arr[smallestIndex] = saved;
		moveCount = (moveCount+3);
	}
	cout << "\n\nAfter " << cmpCount << " comparisons, and " << moveCount << " data movements, ";
}


void bubbleSort(int arr[], int n, int cmpCount, int moveCount)
{
	for (size_t i = 0; i < n - 1; ++i)
	{
		for (size_t j = 0; j < n - i - 1; ++j)
		/*the "- i" in the "n - i - 1" condition of the inner for loop statement 
		shrinks the iteration each time the outer for loop iteration executes,
		because the largest values that have already been moved to the right don't 
		need to be moved again, making a full iteration unnecessary. For example:
		
		In the int array "3 2 1 4 5", 4 and 5 don't need to be compared or swapped.
		Therefore, only the first three values need to be iterated.
		*/
		
		cmpCount++;
		if (arr[j] > arr[j + 1])
		{
			swap(arr[j], arr[j + 1]);
			moveCount++;
		}
	}
	cout << "\n\nAfter " << cmpCount << " comparisons, and " << moveCount << " data movements, ";
}
				

void insertionSort(int arr[], int n, int cmpCount, int moveCount)
{
	int firstOOO, j, temp;//firstOOO is short for "first out of order", j = element loc
	
	for(firstOOO = 1; firstOOO < n; firstOOO++)
	{
		if(arr[firstOOO] < arr[firstOOO - 1])
		{
			temp = arr[firstOOO];
			j = firstOOO;
			
			do
			{
				arr[j] = arr[j - 1];
				j--;
			}
			while(j > 0 && arr[j - 1] > temp);
			arr[j] = temp;
		}		
	}
	cout << "\n\nAfter " << cmpCount << " comparisons, and " << moveCount << " data movements, ";
}//end of insertion sort

void swap(int arr[], int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

int partition(int arr[], int low, int high, int cmpCount, int moveCount)
{
	int i = low;
	int j = high;
	int x = arr[low];
	while(i < j)
	{
		while(i < j && arr[j] > x)
			j--;
		swap(arr, i, j);

		while(i < j && arr[i] <= x)
			i++;
		swap(arr, i, j);
	}
	return i;
}

void quickSort(int arr[], int low, int high, int cmpCount, int moveCount)
{
	if(low >= high || low < 0)
	{
		return;
	}
	int x = partition(arr, low, high, cmpCount, moveCount);
	quickSort(arr, low, x-1, cmpCount, moveCount);
	quickSort(arr, x+1, high, cmpCount, moveCount);
}

[2kaud]

I don't understand why it would be complaining about scope.

Because what you have is this

for (size_t j = 0; j < n - i - 1; ++j)
     cmpCount++;


if (arr[j] > arr[j + 1])
{
     swap(arr[j], arr[j + 1]);
     moveCount++;
}

Where the loop only controls cmpCount++ and not the if statement!

I suspect you mean this

for (size_t j = 0; j < n - i - 1; ++j) {
		cmpCount++;
		if (arr[j] > arr[j + 1])
		{
			swap(arr[j], arr[j + 1]);
			moveCount++;
		}
}

[laserlight]

Well it doesn't cut down the number of iterations. It just shortens them so that we don't unnecessarily iterate over elements that have already been sorted (bubbled) on the right hand side of the arr[] array in their final and proper place.

Yes, that would be a correct way of describing it. I probably meant "comparisons" instead.

I don't understand why it would be complaining about scope. j is already declared and initialized in the inner for loop statement of the bubble function.

You forgot to use braces for the inner loop body, therefore the scope of j does not extend to that point.