// If you are not sure what some lines of code do, try looking back at
// previous example programs, notes, or ask a question.
 
#include <iostream>
#include <cstdlib>
#include <ctime>
 
using namespace std;
 
// Sorting function prototypes
void bubbleSort(int[],int);
void selectionSort(int[],int);
void quickSort(int[],int,int);
 
// Will put random values between 10 and to into an array
void randomize(int[],int);
 
// Shows how to pass a two dimensional array to a function
void func(int[][10]);
 
int main() {
 
	srand(time(NULL));
 
	// MULTIDIMENTIONAL ARRAYS	
 
	// Declares a two dimensional array of integers of sizes 10 and 10, so it
	// can store up to 100 integers in total.
	int array2D[10][10];
 
	// Declares a tree dimensional array of integers of sizes 10, 10, and 10, so it
	// can store up to 1000 integers in total.
	int array3D[10][10][10];
 
	// Passing a multidimensional array is the same as a one dimensional array
	func(array2D);
 
	// Loop though all three dimensions of the 3D array using three nested loops
	for(int i = 0; i < 10; i++)
		for(int j = 0; j < 10; j++)
			for(int k = 0; k < 10; k++)
				array3D[i][j][k] = 0;
 
	// Output each value in the 3D Array
	cout << "3D Array: " << endl;
	for(int i = 0; i < 10; i++) {
		for(int j = 0; j < 10; j++) {
			for(int k = 0; k < 10; k++)
				cout << array3D[i][j][k];
			cout << " ";
		}
		cout << endl;
	}
	cout << endl;
 
 
	// SORTING
 
	int sortArray[10];
 
 
	// Demonstrate Bubble Sort
	randomize(sortArray,10);
 
	cout << "Array: ";
	for(int i = 0; i < 10; i++)
		cout << sortArray[i] << " ";
 
	bubbleSort(sortArray,10);
 
	cout << endl << "Bubble Sort: ";
	for(int i = 0; i < 10; i++)
		cout << sortArray[i] << " ";
	cout << endl << endl;
 
 
	// Demonstrate selection sort
	randomize(sortArray,10);
 
	cout << "Array: ";
	for(int i = 0; i < 10; i++)
		cout << sortArray[i] << " ";
 
	selectionSort(sortArray,10);
 
	cout << endl << "Selection Sort: ";
	for(int i = 0; i < 10; i++)
		cout << sortArray[i] << " ";
	cout << endl << endl;
 
 
	// Demonstrate quick sort
	randomize(sortArray,10);
 
	cout << "Array: ";
	for(int i = 0; i < 10; i++)
		cout << sortArray[i] << " ";
 
	quickSort(sortArray,0,10);
 
	cout << endl << "Quick Sort: ";
	for(int i = 0; i < 10; i++)
		cout << sortArray[i] << " ";
	cout << endl << endl;
 
 
	// End program
	cout << endl;
	system("pause");
 
	return 0;
}
 
void func(int array[][10]) {
	// Do stuff with array
}
 
void bubbleSort(int array[], int size) {
 
	int temp;
 
	// See notes
	for(int i = 0; i < size; i++)
		for(int j = 0; j < size - 1; j++)
			if(array[j] > array[j+1]) {
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
}
 
void selectionSort(int array[], int size) {
 
	int temp, lowest;
 
	// See notes
	for(int i = 0; i < size - 1; i++) {
		lowest = i;
		for(int j = i; j < size; j++)
			if(array[j] < array[lowest])
				lowest = j;
		temp = array[i];
		array[i] = array[lowest];
		array[lowest] = temp;
	}
}
 
void quickSort(int arr[], int left, int right) {
 
	int i = left, j = right;
	int tmp;
	int pivot = arr[(left + right) / 2];
 
 	// See notes
	while (i <= j) {
		while (arr[i] < pivot)
			i++;
		while (arr[j] > pivot)
				j--;
		if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
			j--;
		}
	}
 
	if (left < j)
		quickSort(arr, left, j);
	if (i < right)
		quickSort(arr, i, right);
}
 
void randomize(int array[], int size) {
	for(int i = 0; i < size; i++)
		array[i] = rand() % 10;
}
 

Ly8gSWYgeW91IGFyZSBub3Qgc3VyZSB3aGF0IHNvbWUgbGluZXMgb2YgY29kZSBkbywgdHJ5IGxvb2tpbmcgYmFjayBhdAovLyBwcmV2aW91cyBleGFtcGxlIHByb2dyYW1zLCBub3Rlcywgb3IgYXNrIGEgcXVlc3Rpb24uCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3RpbWU+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gU29ydGluZyBmdW5jdGlvbiBwcm90b3R5cGVzCnZvaWQgYnViYmxlU29ydChpbnRbXSxpbnQpOwp2b2lkIHNlbGVjdGlvblNvcnQoaW50W10saW50KTsKdm9pZCBxdWlja1NvcnQoaW50W10saW50LGludCk7CgovLyBXaWxsIHB1dCByYW5kb20gdmFsdWVzIGJldHdlZW4gMTAgYW5kIHRvIGludG8gYW4gYXJyYXkKdm9pZCByYW5kb21pemUoaW50W10saW50KTsKCi8vIFNob3dzIGhvdyB0byBwYXNzIGEgdHdvIGRpbWVuc2lvbmFsIGFycmF5IHRvIGEgZnVuY3Rpb24Kdm9pZCBmdW5jKGludFtdWzEwXSk7CgppbnQgbWFpbigpIHsKCglzcmFuZCh0aW1lKE5VTEwpKTsKCgkvLyBNVUxUSURJTUVOVElPTkFMIEFSUkFZUwkKCgkvLyBEZWNsYXJlcyBhIHR3byBkaW1lbnNpb25hbCBhcnJheSBvZiBpbnRlZ2VycyBvZiBzaXplcyAxMCBhbmQgMTAsIHNvIGl0CgkvLyBjYW4gc3RvcmUgdXAgdG8gMTAwIGludGVnZXJzIGluIHRvdGFsLgoJaW50IGFycmF5MkRbMTBdWzEwXTsKCgkvLyBEZWNsYXJlcyBhIHRyZWUgZGltZW5zaW9uYWwgYXJyYXkgb2YgaW50ZWdlcnMgb2Ygc2l6ZXMgMTAsIDEwLCBhbmQgMTAsIHNvIGl0CgkvLyBjYW4gc3RvcmUgdXAgdG8gMTAwMCBpbnRlZ2VycyBpbiB0b3RhbC4KCWludCBhcnJheTNEWzEwXVsxMF1bMTBdOwoKCS8vIFBhc3NpbmcgYSBtdWx0aWRpbWVuc2lvbmFsIGFycmF5IGlzIHRoZSBzYW1lIGFzIGEgb25lIGRpbWVuc2lvbmFsIGFycmF5CglmdW5jKGFycmF5MkQpOwoKCS8vIExvb3AgdGhvdWdoIGFsbCB0aHJlZSBkaW1lbnNpb25zIG9mIHRoZSAzRCBhcnJheSB1c2luZyB0aHJlZSBuZXN0ZWQgbG9vcHMKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJCWZvcihpbnQgaiA9IDA7IGogPCAxMDsgaisrKQoJCQlmb3IoaW50IGsgPSAwOyBrIDwgMTA7IGsrKykKCQkJCWFycmF5M0RbaV1bal1ba10gPSAwOwoKCS8vIE91dHB1dCBlYWNoIHZhbHVlIGluIHRoZSAzRCBBcnJheQoJY291dCA8PCAiM0QgQXJyYXk6ICIgPDwgZW5kbDsKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKSB7CgkJZm9yKGludCBqID0gMDsgaiA8IDEwOyBqKyspIHsKCQkJZm9yKGludCBrID0gMDsgayA8IDEwOyBrKyspCgkJCQljb3V0IDw8IGFycmF5M0RbaV1bal1ba107CgkJCWNvdXQgPDwgIiAiOwoJCX0KCQljb3V0IDw8IGVuZGw7Cgl9Cgljb3V0IDw8IGVuZGw7CgoKCS8vIFNPUlRJTkcKCglpbnQgc29ydEFycmF5WzEwXTsKCgoJLy8gRGVtb25zdHJhdGUgQnViYmxlIFNvcnQKCXJhbmRvbWl6ZShzb3J0QXJyYXksMTApOwoKCWNvdXQgPDwgIkFycmF5OiAiOwoJZm9yKGludCBpID0gMDsgaSA8IDEwOyBpKyspCgkJY291dCA8PCBzb3J0QXJyYXlbaV0gPDwgIiAiOwoKCWJ1YmJsZVNvcnQoc29ydEFycmF5LDEwKTsKCgljb3V0IDw8IGVuZGwgPDwgIkJ1YmJsZSBTb3J0OiAiOwoJZm9yKGludCBpID0gMDsgaSA8IDEwOyBpKyspCgkJY291dCA8PCBzb3J0QXJyYXlbaV0gPDwgIiAiOwoJY291dCA8PCBlbmRsIDw8IGVuZGw7CgoKCS8vIERlbW9uc3RyYXRlIHNlbGVjdGlvbiBzb3J0CglyYW5kb21pemUoc29ydEFycmF5LDEwKTsKCgljb3V0IDw8ICJBcnJheTogIjsKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJCWNvdXQgPDwgc29ydEFycmF5W2ldIDw8ICIgIjsKCglzZWxlY3Rpb25Tb3J0KHNvcnRBcnJheSwxMCk7CgoJY291dCA8PCBlbmRsIDw8ICJTZWxlY3Rpb24gU29ydDogIjsKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJCWNvdXQgPDwgc29ydEFycmF5W2ldIDw8ICIgIjsKCWNvdXQgPDwgZW5kbCA8PCBlbmRsOwoKCgkvLyBEZW1vbnN0cmF0ZSBxdWljayBzb3J0CglyYW5kb21pemUoc29ydEFycmF5LDEwKTsKCgljb3V0IDw8ICJBcnJheTogIjsKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJCWNvdXQgPDwgc29ydEFycmF5W2ldIDw8ICIgIjsKCglxdWlja1NvcnQoc29ydEFycmF5LDAsMTApOwoKCWNvdXQgPDwgZW5kbCA8PCAiUXVpY2sgU29ydDogIjsKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgaSsrKQoJCWNvdXQgPDwgc29ydEFycmF5W2ldIDw8ICIgIjsKCWNvdXQgPDwgZW5kbCA8PCBlbmRsOwoKCgkvLyBFbmQgcHJvZ3JhbQoJY291dCA8PCBlbmRsOwoJc3lzdGVtKCJwYXVzZSIpOwoJCglyZXR1cm4gMDsKfQoKdm9pZCBmdW5jKGludCBhcnJheVtdWzEwXSkgewoJLy8gRG8gc3R1ZmYgd2l0aCBhcnJheQp9Cgp2b2lkIGJ1YmJsZVNvcnQoaW50IGFycmF5W10sIGludCBzaXplKSB7CgoJaW50IHRlbXA7CgoJLy8gU2VlIG5vdGVzCglmb3IoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQoJCWZvcihpbnQgaiA9IDA7IGogPCBzaXplIC0gMTsgaisrKQoJCQlpZihhcnJheVtqXSA+IGFycmF5W2orMV0pIHsKCQkJCXRlbXAgPSBhcnJheVtqXTsKCQkJCWFycmF5W2pdID0gYXJyYXlbaisxXTsKCQkJCWFycmF5W2orMV0gPSB0ZW1wOwoJCQl9Cn0KCnZvaWQgc2VsZWN0aW9uU29ydChpbnQgYXJyYXlbXSwgaW50IHNpemUpIHsKCglpbnQgdGVtcCwgbG93ZXN0OwoKCS8vIFNlZSBub3RlcwoJZm9yKGludCBpID0gMDsgaSA8IHNpemUgLSAxOyBpKyspIHsKCQlsb3dlc3QgPSBpOwoJCWZvcihpbnQgaiA9IGk7IGogPCBzaXplOyBqKyspCgkJCWlmKGFycmF5W2pdIDwgYXJyYXlbbG93ZXN0XSkKCQkJCWxvd2VzdCA9IGo7CgkJdGVtcCA9IGFycmF5W2ldOwoJCWFycmF5W2ldID0gYXJyYXlbbG93ZXN0XTsKCQlhcnJheVtsb3dlc3RdID0gdGVtcDsKCX0KfQoKdm9pZCBxdWlja1NvcnQoaW50IGFycltdLCBpbnQgbGVmdCwgaW50IHJpZ2h0KSB7CgoJaW50IGkgPSBsZWZ0LCBqID0gcmlnaHQ7CglpbnQgdG1wOwoJaW50IHBpdm90ID0gYXJyWyhsZWZ0ICsgcmlnaHQpIC8gMl07CiAKIAkvLyBTZWUgbm90ZXMKCXdoaWxlIChpIDw9IGopIHsKCQl3aGlsZSAoYXJyW2ldIDwgcGl2b3QpCgkJCWkrKzsKCQl3aGlsZSAoYXJyW2pdID4gcGl2b3QpCgkJCQlqLS07CgkJaWYgKGkgPD0gaikgewogICAgICAgICAgICB0bXAgPSBhcnJbaV07CiAgICAgICAgICAgIGFycltpXSA9IGFycltqXTsKICAgICAgICAgICAgYXJyW2pdID0gdG1wOwogICAgICAgICAgICBpKys7CgkJCWotLTsKCQl9Cgl9CiAKCWlmIChsZWZ0IDwgaikKCQlxdWlja1NvcnQoYXJyLCBsZWZ0LCBqKTsKCWlmIChpIDwgcmlnaHQpCgkJcXVpY2tTb3J0KGFyciwgaSwgcmlnaHQpOwp9Cgp2b2lkIHJhbmRvbWl6ZShpbnQgYXJyYXlbXSwgaW50IHNpemUpIHsKCWZvcihpbnQgaSA9IDA7IGkgPCBzaXplOyBpKyspCgkJYXJyYXlbaV0gPSByYW5kKCkgJSAxMDsKfQo=