Skip to content

Instantly share code, notes, and snippets.

@SibTiger

SibTiger/DecreaseByOneAndConquer.cpp

Created May 8, 2018 19:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SibTiger/f1fdf91f6304c6e3430fa461d06646cc to your computer and use it in GitHub Desktop.
Save SibTiger/f1fdf91f6304c6e3430fa461d06646cc to your computer and use it in GitHub Desktop.
Download ZIP
Demonstration of 'Decrease by one and Conquer' sorting algorithms in Algorithm Analysis
Raw
DecreaseByOneAndConquer.cpp
// =====================================================
// Programmer: Nicholas Gautier
// Class: CS3713; Algorithm Analysis
// Assignment #: 3
// Due Date: 15. April. 2018
// Instructor: Mr. Moinian, Feridoon
// Description: This particular homework assignment can
// be able to perform various functionalities
// relating to the 'Decrease-by-one-and-conquer'
// topics. When loaded, the user will be presented
// with a menu of what tasks to perform within
// the program using the same one 1D Array.
//
// NOTE: I am using Visual Studio 2017.
// ----
// COMPILING NOTES FOR G++
// - NOTHING YET -
// ----
// Return Codes:
// 0 = Successful Operation
// !0 = See Operating System Documentation
// =====================================================
#pragma region Inclusions
#include <iostream> // For input and output
#include <stdio.h> // Used for the 'NULL' macro
#include <stdlib.h> // Used for random seed and random.
#include <time.h> // Time function
#pragma endregion
// ----
#pragma region Function Prototypes
void Print(int[], int, int); // Print all elements within the array.
int Largest(int[], int, int); // Find the largest element within the array.
int Sum(int[], int, int); // Find the sum by adding all of the elements within the array.
int Count(int[], int, int, int); // Count how many times a key has been found within the array.
bool SortedAscending(int[], int, // Determine if the array has been sorted into increasing order.
int);
bool SortedDescending(int[], int, // Determine if the array has been sorted into decreasing order.
int);
void Reverse(int[], int, int); // This will take the array (sorted ascending) and will reverse its contents.
// ----
// NOT IN REQUIREMENTS
void Fill(int[], int, int); // Fill the array with data.
void QuickSort(int[], int, int, // Quick Sort Algorithm (Divide and Conquer)
bool);
int QuickSortPartitionAscending( // Quick Sort: Partitioning for Ascending
int[], int, int);
int QuickSortPartitionDescending( // Quick Sort: Partitioning for Descending
int[], int, int);
void DrawHeader(); // Draw the program's header information into the terminal buffer
void DrawAbout(); // Draw the About section within the terminal buffer
void DrawInstructions(); // Draw the Instructions section within the terminal buffer.
void DrawMenu(); // Draw the menu screen
bool UserChoice(char); // Fetches and inspects the user input to assure that the input provided was legal.
void DisplayPrompt(); // This function will merely display the prompt message on the screen.
char MenuWrapper(); // This function will execute the menu protocol - simply for simplicity.
#pragma endregion
// ----
#pragma region Macros
#define _NAME_ "Decrease and Conquer" // Program Name
#define _VERSION_ "1.0" // Program Version
#define _VERSION_NAME_ "TROY" // Version Name
#define _ARRAY_SIZE_ 100 // Size of the array
// Max possible (atleast tested) is 4000.
// If going beyond 4000, we could run out
// of Stack space, thus causing the program
// to throw an exception.
// Extreme Testing: 4000
// Default Testing: 100
#define _ARRAY_MAX_RNG_NUM_ 100 // Maximum limit number for the RNG
#define _ARRAY_MIN_RNG_NUM_ 1 // Minimum limit number for the RNG
#define _STDIN_PROMPT_ ">>>>>> " // Prompt message; Python'ish prompt
#pragma endregion
// ----
#pragma region Speceial String Macros
// This error message is to be shown when a user has yet generated the array, but chooses to execute a specialized
// instruction within the array - that has never been initialized.
#define _STR_NOT_GENERATED_ "Array has not been generated! Please generate the array first before executing this algorithm."
// This error message is to be shown when a user has not yet sorted the array in ascending order.
#define _STR_NOT_SORTED_ASCENDING_ "The array has not yet been sorted in ascending order! Please sort the array in ascending order first before using this algorithm."
#pragma endregion
// ----
#pragma region Global Variables
bool isGenerated = false; // A helpful variable to determine if the array has been generated.
#pragma endregion
// ----
// Main Program Entry
// ----------------------------
// The main entry point of the program
int main()
{
// Initialization and Declarations
// ================================
int numArray[_ARRAY_SIZE_]; // Declare the main array that
// we will be using through out
// this entire program.
char userChoice = ' '; // User navigation within the program
int numericSearchKey; // Search Key for the Count() function;
// holds key-value to find in array
// ================================
// Generate a new seed for the RNG functionality
srand(time(NULL));
// Program Information and Details
// ================================
// Display the program header
DrawHeader();
// Provide some spacing on the terminal buffer
std::cout << std::endl;
// Display the program's about message
DrawAbout();
// Provide some spacing on the terminal buffer
std::cout << std::endl;
// Display the instructions
DrawInstructions();
// Provide some spacing on the terminal buffer
std::cout << std::endl;
// --------------------------------
do
{
userChoice = MenuWrapper(); // Execute the menu functionality.
std::cout << std::endl; // Provide an extra space
switch (userChoice)
{
case '1':
// Generate the array
std::cout << "Generating the array. . ." << std::endl;
Fill(numArray, // Array to be generated
0, // Starting Point
_ARRAY_SIZE_ // Ending Point
);
std::cout << "Finished!" << std::endl;
isGenerated = true; // Array has been generated.
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '2':
// Print the array
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Displaying array contents. . ." << std::endl;
Print(numArray, // Array to be displayed
0, // Starting Point
_ARRAY_SIZE_ // Ending Point
);
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '3':
// Find the largest number
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Finding the largest number within the array. . ." << std::endl;
std::cout << "Largest Value is: "
<< Largest(numArray, 0, _ARRAY_SIZE_)
<< std::endl;
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '4':
// Sum of all numbers within the array
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Finding the sum within the array. . ." << std::endl;
std::cout << "Summation is: "
<< Sum(numArray, 0, _ARRAY_SIZE_)
<< std::endl;
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '5':
// Search and Count
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Enter a number to find in array list: " << std::endl;
DisplayPrompt();
std::cin >> numericSearchKey;
std::cout << "Finding the sum within the array. . ." << std::endl;
std::cout << "Search key [ " << numericSearchKey << " ] was found in array list [ " << Count(numArray, 0, _ARRAY_SIZE_, numericSearchKey) << " ] times." << std::endl;
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '6':
// Is array sorted (Ascending)?
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Determining if array has been sorted in ascending order. . ." << std::endl;
if (SortedAscending(numArray, 0, _ARRAY_SIZE_))
std::cout << "The array list is currently sorted in ascending order." << std::endl;
else
std::cout << "The array list is not currently sorted in ascending order." << std::endl;
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '7':
// Is array sorted (Descending)?
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Determining if array has been sorted in descending order. . ." << std::endl;
if (SortedDescending(numArray, 0, _ARRAY_SIZE_))
std::cout << "The array list is currently sorted in descending order." << std::endl;
else
std::cout << "The array list is not currently sorted in descending order." << std::endl;
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '8':
// Sort array (1 ==> infinite)
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Sorting the array in ascending order. . ." << std::endl;
QuickSort(numArray, 0, _ARRAY_SIZE_ - 1, false);
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '9':
// Sort Array (infinite ==> 1)
if (!isGenerated) // Check if the array has been generated.
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
std::cout << "Sorting the array in descending order. . ." << std::endl;
QuickSort(numArray, 0, _ARRAY_SIZE_ - 1, true);
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
// ########################################################################################
case '0':
// Sort the Array (infinite ==> 1) [USING LOOPS]
if (!isGenerated)
{
// Display an error message.
std::cout << _STR_NOT_GENERATED_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Yet Generated
// Make sure that the array is sorted in ascending order.
if (!SortedAscending(numArray, 0, _ARRAY_SIZE_))
{
// Display an error message.
std::cout << _STR_NOT_SORTED_ASCENDING_ << std::endl << std::endl << std::endl;
// Leave, do not execute the algorithm.
break;
} // IF: Not Sorted Ascendingly
// Perform the algorithm
std::cout << "Sorting the array in descending order [USING LOOPS]. . ." << std::endl;
Reverse(numArray, 0, _ARRAY_SIZE_);
std::cout << "Finished!" << std::endl;
std::cout << std::endl << std::endl; // Provide some extra spaces for easy reading
break;
case 'x':
case 'X':
// User requested to quit the program
break;
default:
// It worked with Microsoft, why can't I use it as well? ;)
std::cout << "Something Happened" << std::endl
<< "Google 'something happened'" << std::endl
<< std::endl;
break;
} // Switch
} while (tolower(userChoice) != 'x');
// Prepare the termination process
std::cout << std::endl << "Terminating program. . ." << std::endl;
return 0;
} // Main()
// ----
// Draw Header
// ------------------------------------
// This function will provide a header to the top-most space on
// the terminal buffer.
void DrawHeader()
{
std::cout << _NAME_ << " - Version: " << _VERSION_ << std::endl
<< "Version Name: " << _VERSION_NAME_ << std::endl
<< "--------------------------------------------" << std::endl;
} // DrawHeader()
// ----
// Draw Instructions
// ------------------------------------
// This function will provide instructions to the end-user, along
// with how this program works.
void DrawInstructions()
{
std::cout << "Instructions" << std::endl
<< "-----------------------------" << std::endl
<< "Select a option from the menu to execute an operation." << std::endl
<< "=========================================" << std::endl;
} // DrawInstructions()
// ----
// Draw About
// ------------------------------------
// This function is merely designed to display what this program is about and its primary purpose.
void DrawAbout()
{
std::cout << "This program will allow the end-user to perform various Decrease-By-One-And-Conquer operations supported within this program. "
<< "Once the program is executed, a new array will be generated with a size of [ " << _ARRAY_SIZE_ << " ] indexes, but NOT initialized! "
<< "Because the array is not initialized, it is recommended that the array is generated with random data. This can be done by selecting the appropriate option from the menu. "
<< "Once the array has been generated with random data, you may then play around with all of the options available to you."
<< std::endl
<< std::endl
<< "NOTE: Please generate the array if not already done so!"
<< std::endl;
} // DrawAbout()
// ----
// Dray Menu
// ------------------------------------
// This function will display the program menu to the user,
// thus providing what operations are available to the user
// in regards to Decrease-By-One-And-Conquer or other special
// functionality.
void DrawMenu()
{
std::cout << "PROGRAM MENU"
<< std::endl
<< std::endl
<< "Select an option from the menu:" << std::endl
<< "---------------------------------"
<< std::endl
<< std::endl
<< " [1] - Generate the array" << std::endl
<< " [2] - Print the array" << std::endl
<< " [3] - Find the largest number" << std::endl
<< " [4] - Sum of all numbers in the array" << std::endl
<< " [5] - Search and Count" << std::endl
<< " [6] - Is the array sorted? (Small --> Largest)" << std::endl
<< " [7] - Is the array sorted? (Largest --> Small)" << std::endl
<< " [8] - Sort the array (Small --> Largest)" << std::endl
<< " [9] - Sort the array (Largest --> Small)" << std::endl
<< " [0] - Sort the array (Largest --> Small) [USING LOOP]" << std::endl
<< std::endl
<< "Other Options:" << std::endl
<< "---------------" << std::endl
<< " [X] - Exit this program"
<< std::endl
<< std::endl;
} // DrawMenu()
// ----
// User Choice
// ------------------------------------
// This function is designed to assure that the user selects the
// correct option from the menu. Despite this is probably not the
// efficient way to handle this approach, we are going to merely
// do this in a Quick-and-Dirty way to expedite the development time.
// -----------------------
// Parameters
// selectedOption (CHAR)
// This will be used for inspecting the user's choice reflected
// upon from the menu.
// -----------------------
// Output
// [Bool]
// When false, the user selected a legal option from the menu.
// When true, the user selected an option that is not supported
// from the menu.
bool UserChoice(char selectedOption)
{
// Check the user's input and assure that it is valid with the
// menu. Because we are not working with Dynamic menu's, we
// will merely hard-code the checks. Again, we are expediting
// the work - thus less on quality internally.
// Inspect the input from the user
switch(selectedOption)
{
case '1':
// Generate the array
case '2':
// Print the array
case '3':
// Find the largest number
case '4':
// Sum of all numbers within the array
case '5':
// Search and Count
case '6':
// Is array sorted (1 ==> infinite)?
case '7':
// Is array sorted (infinite ==> 1)?
case '8':
// Sort array (1 ==> infinite)
case '9':
// Sort Array (infinite ==> 1)
case '0':
// Sort Array (infinite ==> 1) [USING LOOPS]
return false;
break;
case 'x':
case 'X':
// Exit
return false;
break;
default:
// Bad input
return true;
break;
} // Switch
} // UserChoice()
// ----
// Display Prompt
// ------------------------------------
// This function will merely display the prompt message on the screen.
// This is useful for showing that the program is waiting for input
// from the user.
void DisplayPrompt()
{
std::cout << _STDIN_PROMPT_;
} // DisplayPrompt()
// ----
// Menu Wrapper
// ------------------------------------
// This function will display the menu on the screen and provide
// the necessary protocols to assure that the user selects the
// right option from the menu. This was designed to reduce
// some code overhead in the main() function.
// -----------------------
// Output
// [CHAR]
// Returns the valid selected option back to the calling
// function.
char MenuWrapper()
{
// Initialization and Declarations
// ================================
char userChoice = ' '; // User requested option
bool choicePassed = false; // This variable will determine if
// the user selected the appropriate
// option from the list.
// ================================
// This loop is to assure that the user selects the
// appropriate option provided within the menu.
do
{
// Draw the menu on the screen
DrawMenu();
// Display the prompt on the screen
DisplayPrompt();
// Fetch the input from the user
std::cin >> userChoice;
// Check if the input was valid
choicePassed = UserChoice(userChoice);
// Display an error on the screen that
// the input was invalid.
if (choicePassed)
std::cout << "ERROR: Bad Input!"
<< std::endl
<< std::endl
<< std::endl;
} while (choicePassed);
// Return the selected option to the calling function
return userChoice;
} // MenuWrapper()
// ----
// Fill
// ------------------------------------
// This function will merely populate the array with
// randomized numbers using the Random Number Generator.
// -----------------------
// Parameters
// numArray [INTEGER - ARRAY]
// This will hold the number array that will be used
// during the population phase.
// leftPos [Integer]
// Left most position of the array, or the
// starting point of the array.
// rightPos [Integer]
// Right most position of the array, or the
// ending point of the array.
void Fill(int numArray[], int leftPos, int rightPos)
{
if (leftPos >= rightPos)
return; // Avoid Overflow; when we have passed the maximum size length, we're finished.
else
{
// Set the value within the index
numArray[leftPos] =
_ARRAY_MIN_RNG_NUM_ + rand() % _ARRAY_MAX_RNG_NUM_;
// Go to the next index and change its value, recursive call
Fill(numArray, leftPos + 1, rightPos);
} // else - conditional
} // Fill()
// ----
// Print
// ------------------------------------
// This function will print all of the indexes within the
// array, recursively.
// Decrease-by-One-and-Conquer Technique
// -----------------------
// Parameters
// numArray [INTEGER - ARRAY]
// This holds the array that we want to output to
// the screen.
// leftPos [Integer]
// Left most position of the array, or the
// starting point of the array.
// rightPos [Integer]
// Right most position of the array, or the
// ending point of the array.
void Print(int numArray[], int leftPos, int rightPos)
{
if (leftPos >= rightPos) // Base Case; Overflow Protection
return; // Avoid Overflow; when we have passed the maximum size length, we're finished.
else // Print the Array
{
// Output the content within the array
std::cout << "Index: " << leftPos
<< "\t" << "Data: " << numArray[leftPos]
<< std::endl;
// Jump to the next index within the array, recursive call
Print(numArray, leftPos + 1, rightPos);
} // else - condition
} // Print()
// ----
// Quick Sort
// ------------------------------------
// The Quick Sort Algorithm
// This algorithm will sort the array as needed within the requested
// direction.
// I originally wanted to use the Merge Sort algorithm, but I couldn't
// get it to dynamic arrays to work within Visual Studio. I could've
// used Vectors or pointers, but I have little desire to go that far.
// Instead, I decided to just use the Quick Sort algorithm.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to sort.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// sortDirection [BOOLEAN]
// Direction of how the array is to be sorted.
// True = Descending
// False = Ascending
void QuickSort(int numArray[], int leftPos, int rightPos, bool sortDirection = false)
{
// Initialization and Declarations
// ================================
int partition; // Use for partitioning the array; sorting technique
// ================================
// Do not bother if there exists only one element within the array AND assure
// that the left and the right have not crossed.
if (leftPos < rightPos)
{
// Find the partition within the array.
if (sortDirection)
partition = QuickSortPartitionDescending(numArray, leftPos, rightPos);
else
partition = QuickSortPartitionAscending(numArray, leftPos, rightPos);
// Sort the halves
QuickSort(numArray, leftPos, partition - 1, sortDirection); // Sort the lower half
QuickSort(numArray, partition + 1, rightPos, sortDirection); // Sort the upper half
} // if
} // QuickSort()
// ----
// Quick Sort: Partitioning (Ascending)
// ------------------------------------
// This function is designed to find the partition within the array
// and sort it by taking small pieces of the array.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to sort.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
// Output
// Partition Index [INTEGER]
// The index of where the partition lies within the array.
int QuickSortPartitionAscending(int numArray[], int leftPos, int rightPos)
{
// Initialization and Declarations
// ================================
int pivot = numArray[rightPos]; // Pivot Value
int i = (leftPos - 1); // Left-most Index
// ================================
for (int j = leftPos; j <= rightPos - 1; j++)
if (numArray[j] <= pivot)
{
i++; // Update the left side index
std::swap(numArray[i],
numArray[j]); // Swap the content within the array indexes.
} // If
// Move the Pivot
std::swap(numArray[i + 1], numArray[rightPos]);
// Return the Pivot
return (i + 1);
} // QuickSortPartitionAscending()
// ----
// Quick Sort: Partitioning (Descending)
// ------------------------------------
// This function is designed to find the partition within the array
// and sort it by taking small pieces of the array.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to sort.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
// Output
// Partition Index [INTEGER]
// The index of where the partition lies within the array.
int QuickSortPartitionDescending(int numArray[], int leftPos, int rightPos)
{
// Initialization and Declarations
// ================================
int pivot = numArray[rightPos]; // Pivot Value
int i = (leftPos - 1); // Left-most Index
// ================================
for (int j = leftPos; j <= rightPos - 1; j++)
if (numArray[j] >= pivot)
{
i++; // Update the left side index
std::swap(numArray[i],
numArray[j]); // Swap the content within the array indexes.
} // If
// Move the Pivot
std::swap(numArray[i + 1], numArray[rightPos]);
// Return the Pivot
return (i + 1);
} // QuickSortPartitionDescending()
// ----
// Find Largest Number
// ------------------------------------
// This function will find the largest number within the
// array and return it to the calling function.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to scan.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
// Output
// Largest Numeric Value [INTEGER]
// The largest value that exists within the array.
int Largest(int numArray[], int leftPos, int rightPos)
{
// Initialization and Declarations
// ================================
int max; // Used for storing the max value.
// ================================
// Base Case
if (leftPos == rightPos - 1)
// If we reached the left pointer and the right pointer match, than just return the value.
return numArray[leftPos];
else
{
// Recursively go to the next index and locate the next value
max = Largest(numArray, leftPos + 1, rightPos);
// Determine if the 'max' variable has the greater value or if the array[low] has the greatest value.
// Return the results
if (numArray[leftPos] > max)
return numArray[leftPos];
else
return max;
} // ELSE
} // Largest()
// ----
// Summation of Array Contents
// ------------------------------------
// This function will find the sum of all numeric
// numbers within the given array and return it.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to scan.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
// Output
// Summation [INTEGER]
// The summation of all numeric values within the array.
int Sum(int numArray[], int leftPos, int rightPos)
{
// Base Case; if the left index matches with the right index, than just return the left index value.
if (leftPos == rightPos - 1)
return numArray[leftPos];
else
// Return the sum of all numeric values
return (Sum(numArray, leftPos + 1, rightPos) + numArray[leftPos]);
} // Sum()
// ----
// Search Count
// ------------------------------------
// This function is designed to scan the array
// and count how many times a search key has been
// found within the array.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to scan.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
// Output
// Summation Count [INTEGER]
// How many times the search key has been found within the array.
int Count(int numArray[], int leftPos, int rightPos, int searchKey)
{
if (leftPos == rightPos - 1 && numArray[leftPos] != searchKey)
return 0;
else if (leftPos == rightPos - 1 && numArray[leftPos] == searchKey)
return 1;
// ----
if (numArray[leftPos] == searchKey)
return 1 + Count(numArray, leftPos + 1, rightPos, searchKey);
else
return Count(numArray, leftPos + 1, rightPos, searchKey);
} // Count()
// ----
// Is Sorted Ascending?
// ------------------------------------
// This function is designed to scan the array
// and determine if the array's contents has been
// sorted already in ascending order.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to scan.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
// Output
// Is the Array Sorted (Ascending)? [BOOLEAN]
// True = The array is sorted (ascending)
// False = The array is not sorted
bool SortedAscending(int numArray[], int leftPos, int rightPos)
{
// Base Case
if (leftPos == rightPos - 1)
return true;
// Check if the elements are in order
if (numArray[leftPos] > numArray[leftPos + 1])
return false;
// Advance to the next index position.
return SortedAscending(numArray, leftPos + 1, rightPos);
} // SortedAscending()
// ----
// Is Sorted Descending?
// ------------------------------------
// This function is designed to scan the array
// and determine if the array's contents has been
// sorted already in descending order.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to scan.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
// Output
// Is the Array Sorted (Descending)? [BOOLEAN]
// True = The array is sorted (descending)
// False = The array is not sorted
bool SortedDescending(int numArray[], int leftPos, int rightPos)
{
// Base Case
if (leftPos == rightPos - 1)
return true;
// Check if the elements are in order
if (numArray[leftPos] < numArray[leftPos + 1])
return false;
// Advance to the next index position.
return SortedDescending(numArray, leftPos + 1, rightPos);
} // SortedDescending()
// ----
// Reverse
// ------------------------------------
// This function is designed to sort the array in descending order,
// but unlike the Quick Sort algorithm that utilizes recursion,
// we will just use a standard For-Loop.
// -----------------------
// Parameters
// numArray [INTEGER]
// The numeric array we want to scan.
// leftPos [INTEGER]
// The minimum range of the array that is available
// rightPos [INTEGER]
// The maximum range of the array that is available
// -----------------------
void Reverse(int numArray[], int leftPos, int rightPos)
{
// Is there only one item in the array?
if (leftPos == rightPos - 1)
return; // Only one item; nothing todo
// Swap the data within the array
// [1, 4, 5, 13] ==>> [13, 5, 4, 1]
for (int i = 0; i < rightPos / 2; i++)
std::swap(numArray[i], numArray[(rightPos - 1) - i]);
} // Reverse()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment