// // main.cpp // class11 // // Created by Chad Spensky on 7/26/16. // Copyright © 2016 Chad Spensky. All rights reserved. // #include #include using namespace std; // Swap values a and b void swap(int& a, int& b) { int tmp = b; b = a; a = tmp; } // Get the index with the smallest value starting at start_idx int get_smallest_index(int array_param[], int start_idx, int array_length) { // Assume the current position is the smallest int min_idx = start_idx; // Compare this value with all other values and see if there are any smaller values for (int i = start_idx+1; i < array_length; i++) { if (array_param[i] < array_param[min_idx]) { min_idx = i; } } return min_idx; } void selection_sort(int array_param[], int array_length) { // Go over each position and swap the smallest remaining element into it's place for (int i = 0; i < array_length; i++) { // Get the smallest index in the remaining elements int smallest_idx = get_smallest_index(array_param, i, array_length); // Swap the smallest element with this one swap(array_param[i], array_param[smallest_idx]); } } // Implementation of bubble sort // Ref: https://en.wikipedia.org/wiki/Bubble_sort void bubble_sort(int array_param[], int array_length) { // Start at the end (right) and always move the largest value into this position for (int i = array_length-1; i > 0; i--) { // Starting from the begginning, keep swapping the largest value to the right // This will ensure that the largest value ends up in position i for (int j = 0; j < i; j++) { if (array_param[j] > array_param[j+1]) { swap(array_param[j], array_param[j+1]); } } } } // Sort an array using insertion_sort // Ref: https://en.wikipedia.org/wiki/Insertion_sort void insertion_sort(int array_param[], int array_length) { // Go over each position and swap the smallest remaining element into it's place for (int i = 1; i < array_length; i++) { // Starting at the end of the array, keep swapping the element left until the element to the left is no longer smaller int j = i; while (j > 0 && array_param[j] < array_param[j-1]) { swap(array_param[j],array_param[j-1]); // move our j index to the left j--; } } } int main(int argc, const char * argv[]) { // Initialize a simple array int array_len = 5; int array[array_len]; // Get our inputs cout << "Give me " << array_len << " numbers:"; for (int i = 0; i < array_len; i++) { cin >> array[i]; } // Lets sort our array! // Insertion sort // insertion_sort(array,array_len); // Selection sort // selection_sort(array, array_len); // Bubble sort bubble_sort(array, array_len); // Print our sorted results cout << "Results (Sorted): "; for (int x: array) { cout << x << " "; } cout << endl; // Let's play with multidimensional arrays! int rows = 3; int columns = 2; // This can be thought of a matrix with 3 rows and 2 columns int array2[rows][columns]; // Initialize a value to store in our array elements int value = 1; // initialze all of our values for (int row = 0; row < rows; row++) { for (int column = 0; column < columns; column++) { array2[row][column] = value++; } } // Let's print the raw memory of array2 cout << "Raw memory of array2: " << endl; for (int i = 0; i < rows*columns; i++) { cout << "array2[" << i << "] @ " << hex << *array2+i << " = " << dec << *(*array2+i) << endl; } // The computer will let us write to indicies that don't exist! // This is becasue of how it stores the array values in memory array2[0][2] = 100; // Actually changes [1][0] // Let's print the raw memory of array2 cout << "Raw memory of array2: " << endl; for (int i = 0; i < rows*columns; i++) { cout << "array2[" << i << "] @ " << hex << *array2+i << " = " << dec << *(*array2+i) << endl; } // Print the array 1 row at a time for (int row = 0; row < rows; row++) { cout << "Row " << row << ": "; for (int column = 0; column < columns; column++) { cout << array2[row][column] << " "; } cout << endl; } return 0; }