Daily Archives: February 11, 2012
C++ || Class – A Simple Calculator Implementation Using A Class, Enum List, Typedef & Header Files
The following is another homework assignment which was presented in a programming class, that was used to introduce the concept of the class data structure, which is very similar to the struct data structure.
REQUIRED KNOWLEDGE FOR THIS PROGRAM
Header Files - How To Use Them
Class - Data Structure
Enumerated List
Typedef
Do/While Loop
Passing a Value By Reference
Constant Variables
Atoi - Convert String To Int Value
This is an interactive program which simulates a basic arithmetic calculator, where the user has the option of selecting from 9 modes of operation. Of those modes, the user has the option of adding, subtracting, multiplying, and dividing two numbers together. Also included in the calculator is a mode which deducts percentages from any given variable the user desires, so for example, if the user wanted to deduct 23% from the number 87, the program would display the reduced value of 66.99.
A sample of the menu is as followed:
(Where the user would enter numbers 1-9 to select a choice)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Calculator Options: 1) Clear Calculator 2) Set Initial Calculator Value 3) Display The Current Value 4) Add 5) Subtract 6) Divide 7) Multiply 8) Percentage Calculator 9) Quit Please enter a selection: |
This program was implemented into 3 different files (two .cpp files, and one header file .h). So the code for this program will be broken up into 3 sections, the main file (.cpp), the header file (.h), and the implementation of the functions within the header file (.cpp).
NOTE: On some compilers, you may have to add #include < cstdlib> in order for the code to compile.
======== File #1 Main.cpp ========
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 |
// ============================================================================ // This program tests the CCalc class. A loop is entered where the user is // prompted for a simple mathematical operation to be performed by the CCalc // class. The user is allowed to manipulate the calculator until they // indicate they wish to quit. // ============================================================================ #include <iostream> #include <iomanip> #include "CCalc.h" using namespace std; // defined constants const int LENGTH = 81; // function prototypes void DisplayMenu(); void HandleMenuSelection(CCalc &calcObject, int menuItem); // enumerated list enum MenuChoice { ITEM_CLEAR = 1 , ITEM_SET_VALUE = 2 , ITEM_DISPLAY_VALUE = 3 , ITEM_ADD = 4 , ITEM_SUBTRACT = 5 , ITEM_DIVIDE = 6 , ITEM_MULTIPLY = 7 , ITEM_PERCENT = 8 , ITEM_QUIT = 9}; // ==== main ================================================================== // // ============================================================================ int main() { // variable declarations CCalc calculator; // 'calculator' is an accessor to the 'CCalc' class char myString[LENGTH]; int menuItem=0; // initialize the calculator calculator.SetCurrentValue(0); // loop and let the user manipulate the calculator do{ // display the menu and get the user selection DisplayMenu(); cout << "nPlease enter a selection: "; cin.getline(myString, LENGTH); // convert the ascii string into an integer menuItem = atoi(myString); // creates a line seperator after each task is executed cout<<setfill('-'); cout<<left<<setw(30)<<""<<right<<setw(30)<<""<<endl; // handle the menu selection HandleMenuSelection(calculator, menuItem); cout <<endl; // creates a line seperator after each task is executed cout<<setfill('-'); cout<<left<<setw(30)<<""<<right<<setw(30)<<""<<endl; // ensures the menu isnt displayed twice on the screen if(menuItem!=1 && menuItem!=3 && menuItem!=9) { cin.ignore(); } }while(menuItem!=ITEM_QUIT); cout << "nBye....n"; return 0; } // end of "main" // ==== DisplayMenu =========================================================== // // This function displays the menu of options to stdout. // // Input: nothing // // Output: nothing // // ============================================================================ void DisplayMenu() { cout << "Calculator Options:" << endl; cout << " 1) Clear Calculator" << endl; cout << " 2) Set Initial Calculator Value" << endl; cout << " 3) Display The Current Value" << endl; cout << " 4) Add" << endl; cout << " 5) Subtract" << endl; cout << " 6) Divide" << endl; cout << " 7) Multiply" << endl; cout << " 8) Percentage Calculator" << endl; cout << " 9) Quit" << endl; } // end of "DisplayMenu" // ==== HandleMenuSelection =================================================== // // This function handles the menu selection by examining the input integer // value and calling the appropriate function. // // Input: // calculator -- a reference to the CCalc class // // menuItem -- an integer representing the current menu selection // // Output: // The desired user selection // // ============================================================================ void HandleMenuSelection(CCalc &calculator, int menuItem) { double currentValue = 0; double prevNum = calculator.GetPreviousValue(); // checks to see which user defined selection the calculator will execute // as defined in the enum list located above the main function. // A switch would be more practical to be used here, but i wasnt // comfortable yet using switches when this program was initially made if (menuItem == ITEM_CLEAR) { cout << "nThe current value is " << calculator.Clear() << endl; } // set a initial value else if (menuItem == ITEM_SET_VALUE) { cout << "nPlease enter a new value to assign: "; cin >> currentValue; calculator.SetCurrentValue(currentValue); } // display current value else if (menuItem == ITEM_DISPLAY_VALUE) { cout << "nThe current value is: "<< calculator.DisplayCurrentValue() <<endl; } // add current number by another number else if (menuItem == ITEM_ADD) { cout << "nThe current value is: "<< prevNum <<endl; cout << "nPlease enter a number to be added to "<<prevNum<<": "; cin >> currentValue; calculator.Add(currentValue); cout << "n"<<prevNum<<" + "<<currentValue<<" = "<< calculator.DisplayCurrentValue() <<endl; } // subtract current number by another number else if (menuItem == ITEM_SUBTRACT) { cout << "nThe current value is: "<< prevNum <<endl; cout << "nPlease enter a number to be subtracted from "<<prevNum<<": "; cin >> currentValue; calculator.Subtract(currentValue); cout << "n"<<prevNum<<" - "<<currentValue<<" = " << calculator.DisplayCurrentValue() <<endl; } // divide current value by another number else if (menuItem == ITEM_DIVIDE) { cout << "nThe current value is: "<< prevNum <<endl; cout << "nPlease enter a divisor to be divided by "<<prevNum<<": "; cin >> currentValue; if (currentValue == 0) { cout << "nSorry, division by zero is not allowed...nPlease press ENTER to continue..."; cin.get(); } else { calculator.Divide(currentValue); cout << "n"<<prevNum<<" "<<char(246)<<" "<<currentValue<<" = " << calculator.DisplayCurrentValue() <<endl; } } // multiply current value by another number else if (menuItem == ITEM_MULTIPLY) { cout << "nThe current value is: "<< prevNum <<endl; cout << "nPlease enter a number to be multiplied by "<<prevNum<<": "; cin >> currentValue; calculator.Multiply(currentValue); cout << "n"<<prevNum<<" x "<<currentValue<<" = " << calculator.DisplayCurrentValue() <<endl; } // convert value to decimal percent else if (menuItem == ITEM_PERCENT) { cout << "nThe current value is: "<< prevNum <<endl; cout << "nPlease enter a percentage to be deducted from "<<prevNum<<": "; cin >> currentValue; cout << "n"<<currentValue<<"% off of "<<prevNum<<" is " << calculator.GetPercentage(currentValue) <<endl; } // quit program else if (menuItem == ITEM_QUIT) { cout << "nCalculator will now quit"; } // user entered an invalid choice else { cout << "nYou have entered an invalid command...nPlease press ENTER to try again."; } } // http://programmingnotes.org/ |
======== File #2 CCalc.h. ========
Remember, you need to name the header file the same as the #include from the main.cpp file. This file contains the function declarations, but no implementation of those functions takes place here.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// ============================================================================ // File: CCalc.h // ============================================================================ // This is the header file for the CCalc class. // ============================================================================ #ifndef CCALC_HEADER #define CCALC_HEADER // a typedef statement to create a synonym for // the 'double' data type named "CCalcType" typedef double CCalcType; class CCalc // this is the 'CCalc' class declaration { public: // constructor CCalc(); // initializes variables // member functions void Add(CCalcType value); // adds numbers together CCalcType Clear(); // clears the current number in the calculator void Divide(CCalcType value); // divides numbers together CCalcType DisplayCurrentValue(); // displays the current value in the calculator CCalcType GetPreviousValue(); // returns the previous value in the calculator CCalcType GetPercentage(CCalcType value); // deducts a user specified percentage of a given value void Multiply(CCalcType value); // multiplies numbers together void SetCurrentValue(CCalcType value); // set a current value in the calculator void Subtract(CCalcType value); // subtracts two numbers together // destructor ~CCalc(); // deletes any variables contained in the class private: CCalcType m_total; // private variable used within the program }; #endif // CCALC_HEADER -- http://programmingnotes.org/ |
======== File #3 CCalc.cpp. ========
This is the function implementation file for the CCalc.h class. This file can be named anything you wish as long as you #include “CCalc.h”
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
// ============================================================================ // File: CCalc.cpp // ============================================================================ // This is the function implementation file for the CCalc.h class. // ============================================================================ #include <iostream> #include "CCalc.h" using namespace std; CCalc::CCalc() // this is the constructor { m_total = 0; }// end of CCalc void CCalc::Add(CCalcType value) { m_total += value; }// end of Add CCalcType CCalc::Clear() { m_total = 0; return m_total; }// end of Clear void CCalc::Divide(CCalcType value) { m_total /= value; }// end of Divide CCalcType CCalc::DisplayCurrentValue() { return m_total; }// end of DisplayCurrentValue CCalcType CCalc::GetPreviousValue() { return m_total; }// end of GetPreviousValue void CCalc::Multiply(CCalcType value) { m_total *= value; }// end if Multiply void CCalc::SetCurrentValue(CCalcType value) { m_total = value; }// end of SetValue void CCalc::Subtract(CCalcType value) { m_total -= value; }// end of Subtract CCalcType CCalc::GetPercentage(CCalcType value) { CCalcType percent= value/100; CCalcType tempTotal = m_total; tempTotal *= percent; m_total -= tempTotal; return m_total; }// end of GetPercentage CCalc::~CCalc() // this is the destructor { m_total = 0; }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 0
------------------------------------------------------------You have entered an invalid command...
Please ENTER to try again.
------------------------------------------------------------Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 2
------------------------------------------------------------Please enter a new value to assign: 2
------------------------------------------------------------
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 3
------------------------------------------------------------The current value is: 2
------------------------------------------------------------
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 4
------------------------------------------------------------The current value is: 2
Please enter a number to be added to 2: 2
2 + 2 = 4
------------------------------------------------------------
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 5
------------------------------------------------------------The current value is: 4
Please enter a number to be subtracted from 4: 6
4 - 6 = -2
------------------------------------------------------------
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 6
------------------------------------------------------------The current value is: -2
Please enter a divisor to be divided by -2: -2
-2 ÷ -2 = 1
------------------------------------------------------------
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 7
------------------------------------------------------------The current value is: 1
Please enter a number to be multiplied by 1: 87
1 x 87 = 87
------------------------------------------------------------
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 8
------------------------------------------------------------The current value is: 87
Please enter a percentage to be deducted from 87: 23
23% off of 87 is 66.99
------------------------------------------------------------
Calculator Options:
1) Clear Calculator
2) Set Initial Calculator Value
3) Display The Current Value
4) Add
5) Subtract
6) Divide
7) Multiply
8.) Percentage Calculator
9) QuitPlease enter a selection: 9
------------------------------------------------------------Calculator will now quit
------------------------------------------------------------Bye....
C++ || Snippet – Bubble Sort, Selection Sort, Insertion Sort, Quick Sort & Merge Sort Sample Code For Integer Arrays
This page consists of algorithms for sorting integer arrays. Highlighted on this page are Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, and Merge Sort.
In terms of performance and speed, the sorting algorithms on this page will be listed from the (on average) worst, to best case implementations.
Selection sort and Insertion sort are two simple sorting algorithms which are often more efficient than Bubble Sort, though all three techniques aren’t the top of the class algorithmically for sorting large data sets.
====== BUBBLE SORT ======
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: bubbleSort.cpp // Description: Demonstrates how to sort an array using bubble sort // ============================================================================ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototype void BubbleSort(int arry[], int arraySize); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for (int x = 0; x < NUM_INTS; ++x) { arry[x] = rand() % 100 + 1; } cout << "Original array values" << endl; // output the original array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "\n--------------------------------------------------------\n"; BubbleSort(arry, NUM_INTS); cout << "The current sorted array" << endl; // output the current sorted array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout << endl; cin.get(); return 0; }// end of main void BubbleSort(int arry[], int arraySize) { bool sorted = false; do { sorted = true; for (int x = 0; x < arraySize - 1; ++x) { if (arry[x] > arry[x + 1]) { int temp = arry[x]; arry[x] = arry[x + 1]; arry[x + 1] = temp; sorted = false; } }// end of for loop --arraySize; } while (!sorted); }// http://programmingnotes.org/ |
SAMPLE OUTPUT:
Original array values
91 65 53 93 54 41 69 76 55 90 10 62
--------------------------------------------------------
The current sorted array
10 41 53 54 55 62 65 69 76 90 91 93
====== SELECTION SORT ======
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: selectionSort.cpp // Description: Demonstrates how to sort an array using selection sort // ============================================================================ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototype void SelectionSort(int arry[], int arraySize); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for (int x = 0; x < NUM_INTS; ++x) { arry[x] = rand() % 100 + 1; } cout << "Original array values" << endl; // output the original array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "\n--------------------------------------------------------\n"; SelectionSort(arry, NUM_INTS); cout << "The current sorted array" << endl; // output the current sorted array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout << endl; cin.get(); return 0; }// end of main void SelectionSort(int arry[], int arraySize) { for (int currentNumber = 0; currentNumber < arraySize; ++currentNumber) { int index_of_min = currentNumber; for (int previousNumber = currentNumber + 1; previousNumber < arraySize; ++previousNumber) { if (arry[index_of_min] > arry[previousNumber]) { index_of_min = previousNumber; } } int temp = arry[currentNumber]; arry[currentNumber] = arry[index_of_min]; arry[index_of_min] = temp; } }// http://programmingnotes.org/ |
SAMPLE OUTPUT:
Original array values
87 74 58 64 4 43 23 16 3 93 9 80
--------------------------------------------------------
The current sorted array
3 4 9 16 23 43 58 64 74 80 87 93
====== INSERTION SORT ======
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: insertionSort.cpp // Description: Demonstrates how to sort an array using insertion sort // ============================================================================ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototype void InsertionSort(int arry[], int arraySize); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for (int x = 0; x < NUM_INTS; ++x) { arry[x] = rand() % 100 + 1; } // output the original array values cout << "Original array values" << endl; for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "\n--------------------------------------------------------\n"; InsertionSort(arry, NUM_INTS); // display sorted values cout << "The current sorted array" << endl; // output the current sorted array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout << endl; cin.get(); return 0; }// end of main void InsertionSort(int arry[], int arraySize) { int previousIndex = 0; int currentValue = 0; // iterate through entire list for (int index = 1; index < arraySize; ++index) { currentValue = arry[index]; previousIndex = index - 1; while (previousIndex >= 0 && arry[previousIndex] > currentValue) { arry[previousIndex + 1] = arry[previousIndex]; previousIndex = previousIndex - 1; }// end while loop arry[previousIndex + 1] = currentValue; }// end for loop }// http://programmingnotes.org/ |
SAMPLE OUTPUT:
Original array values
97 80 94 74 10 38 87 7 87 14 3 97
--------------------------------------------------------
The current sorted array
3 7 10 14 38 74 80 87 87 94 97 97
====== QUICK SORT ======
Quicksort is one of the fastest sorting algorithms, and is often the best practical choice for sorting, as its average expected running time for large data sets is more efficient than the previously discussed methods.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: quickSort.cpp // Description: Demonstrates how to sort an array using quick sort // ============================================================================ #include <iostream> #include <ctime> #include <iomanip> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototypes void QuickSort(int arry[], int arraySize); void QuickSort(int arry[], int start, int end); int Partition(int arry[], int start, int end); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for (int x = 0; x < NUM_INTS; ++x) { arry[x] = rand() % 100 + 1; } cout << "Original array values" << endl; // output the original array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "\n--------------------------------------------------------\n"; QuickSort(arry, NUM_INTS); cout << "The current sorted array" << endl; // output the current sorted array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout << endl; cin.get(); return 0; }// end of main // the initial function call and initiates the sort void QuickSort(int arry[], int arraySize) { QuickSort(arry, 0, arraySize - 1); }// end of QuickSort // recursive call that carries out the sort void QuickSort(int arry[], int start, int end) { if (start < end) { // partition the arry and get the new pivot position int newPiviotIndex = Partition(arry, start, end); // quick sort the first part QuickSort(arry, start, newPiviotIndex); // quick sort the second part QuickSort(arry, newPiviotIndex + 1, end); } }// end of QuickSort int Partition(int arry[], int start, int end) { // choose a random pivot int pivotIndex = start + rand() % (end - start + 1); std::swap(arry[end], arry[pivotIndex]); // swap pivot with last element int left = start; // left index int right = end; // right index // compare and select smallest from the subarray for (int index = start; index <= right; ++index) { if (arry[index] < arry[right]) { std::swap(arry[index], arry[left]); ++left; } } // move pivot to its final place std::swap(arry[right], arry[left]); return left; // return the position of the new pivot }// http://programmingnotes.org/ |
SAMPLE OUTPUT:
Original array values
50 94 1 16 51 63 41 17 70 28 6 34
--------------------------------------------------------
The current sorted array
1 6 16 17 28 34 41 50 51 63 70 94
====== MERGE SORT ======
Merge sort is a fast, stable sorting routine which, in the worst case, does about (on average) 39% fewer comparisons than quick sort.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
// ============================================================================ // Author: Kenneth Perkins // Date: Feb 11, 2012 // Taken From: http://programmingnotes.org/ // File: mergeSort.cpp // Description: Demonstrates how to sort an array using merge sort // ============================================================================ #include <iostream> #include <iomanip> #include <ctime> #include <cstdlib> using namespace std; // const int const int NUM_INTS = 12; // function prototypes void MergeSort(int arry[], int arraySize); void MergeSort(int arry[], int start, int end); void Merge(int arry[], int start, int midPt, int end); int main() { // variable declarations int arry[NUM_INTS]; srand(time(NULL)); // place random numbers into the array for (int x = 0; x < NUM_INTS; ++x) { arry[x] = rand() % 100 + 1; } cout << "Original array values" << endl; // output the original array values for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } // creates a line seperator cout << "\n--------------------------------------------------------\n"; MergeSort(arry, NUM_INTS); cout << "The current sorted array" << endl; // output the current sorted for (int x = 0; x < NUM_INTS; ++x) { cout << setw(4) << arry[x]; } cout << endl; cin.get(); return 0; }// end of main // the initial function call and initiates the sort void MergeSort(int arry[], int arraySize) { MergeSort(arry, 0, arraySize - 1); }// end of MergeSort // recursive call that carries out the sort void MergeSort(int arry[], int start, int end) { // no significant comparisons are done during splitting if (start < end) { int midPt = (start + end) / 2; MergeSort(arry, start, midPt); MergeSort(arry, midPt + 1, end); Merge(arry, start, midPt, end); } }// end of MergeSort // sorts the sub array void Merge(int arry[], int start, int midPt, int end) { int leftFirst = start; int leftLast = midPt; int rightFirst = midPt + 1; int rightLast = end; int* tempArray = new int[rightLast + 1]; int index = leftFirst; int saveFirst = leftFirst; while ((leftFirst <= leftLast) && (rightFirst <= rightLast)) {// compare and select smallest from two subarrays if (arry[leftFirst] < arry[rightFirst]) { tempArray[index] = arry[leftFirst]; // smallest assigned to temp ++leftFirst; } else { tempArray[index] = arry[rightFirst]; ++rightFirst; } ++index; } while (leftFirst <= leftLast) { tempArray[index] = arry[leftFirst]; ++leftFirst; ++index; } while (rightFirst <= rightLast) { tempArray[index] = arry[rightFirst]; ++rightFirst; ++index; } for (index = saveFirst; index <= rightLast; ++index) {// copies from temp array to the initial array arry[index] = tempArray[index]; } delete[] tempArray; }// http://programmingnotes.org/ |
SAMPLE OUTPUT:
Original array values
18 46 41 30 84 97 54 49 19 32 70 30
--------------------------------------------------------
The current sorted array
18 19 30 30 32 41 46 49 54 70 84 97
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
