menuDrivenArrayImplementation.cpp

#include <bits/stdc++.h>

using namespace std;

const int maxArraySize = 10;
bool checkSpace(int size, int arr[])
{
    if (size > maxArraySize)
        return true;
    return false;
}
void traverseArray(int iArray[], int arraySize)
{
    for (int i = 0; i < arraySize; i++)
    {
        cout << iArray[i] << " ";
    }
    cout << endl;
}

void mainMenu()
{
    cout << "Select What operation you want to perform." << endl;
    cout << "\t 1.Traverse" << endl;
    cout << "\t 2.Insertion" << endl;
    cout << "\t 3.Deletion" << endl;
    cout << "\t 4.Linear search" << endl;
    cout << "\t 5.Binary search" << endl;
    cout << "\t 6.Recursive binary search" << endl;
    cout << "\t 7.Insertion Sort" << endl;
    cout << "\t 10.Exit" << endl;
    cout << "\n Enter your choice:";
}
void insertionMenu()
{
    cout << "\t 1.Insertion at Beginning" << endl;
    cout << "\t 2.Insertion at Specific Position" << endl;
    cout << "\t 3.Insertion at End" << endl;
    cout << "\t 0.Main Menu" << endl;
}
void deletionMenu()
{
    cout << "\t 1.Deletion at Beginning" << endl;
    cout << "\t 2.Deletion at Specific Position" << endl;
    cout << "\t 3.Deletion at End" << endl;
    cout << "\t 0.Main Menu" << endl;
}
void insertionSort(int inputArray[], int arraySize)
{
    for (int i = 1; i < arraySize; i++)
    {
        int j = i;
        while (j > 0 && inputArray[j - 1] > inputArray[j])
        {
            int temp = inputArray[j];
            inputArray[j] = inputArray[j - 1];
            inputArray[j - 1] = temp;
            j--;
        }
    }
}
void insertionSubMenu(int inputArray[], int &arraySize, int userInput)
{
    switch (userInput)
    {
        int insertingInt;

    case 0:
        cout << "Going back to main menu." << endl;
        break;
    case 1: // insertion at start
        cout << "Enter the integer to you want to insert at start:";
        cin >> insertingInt;
        cout << endl;

        arraySize++;
        if (checkSpace(arraySize, inputArray))
        {
            cout << "Overflow, array is already full" << endl;
            break;
        };

        for (int i = arraySize; i > 0; i--)
        {
            inputArray[i] = inputArray[i - 1];
        }
        inputArray[0] = insertingInt;
        cout << "New Array is: ";
        traverseArray(inputArray, arraySize);
        break;
    case 2: // inserting at mid position
        int position;
        cout << "Enter the position to you want to insert at and then integer:";
        cin >> position >> insertingInt;
        arraySize++;
        if (checkSpace(arraySize, inputArray))
        {
            arraySize--;
            cout << "Overflow, array is already full" << endl;
            break;
        };
        if (position > arraySize || position > maxArraySize)
        {
            cout << "Invalid Position going back to main menu" << endl;
            arraySize--;
            break;
        }
        if (position == arraySize)
        {
            inputArray[position - 1] = insertingInt;
            cout << "New Array is: ";
            traverseArray(inputArray, arraySize);
            break;
        }
        for (int i = arraySize; i >= position; i--)
        {
            inputArray[i] = inputArray[i - 1];
        }
        inputArray[position - 1] = insertingInt;
        cout << "New Array is: ";
        traverseArray(inputArray, arraySize);

        break;
    case 3: // insertion at end
        arraySize++;
        if (checkSpace(arraySize, inputArray))
        {
            cout << "Sorry Array is full" << endl;
            break;
        };
        cout << "Enter the integer to you want to insert at end:";
        cin >> insertingInt;
        cout << endl;

        inputArray[arraySize - 1] = insertingInt;
        cout << "New Array is: ";
        traverseArray(inputArray, arraySize);

        break;

    default:
        cout << "Invalid choice going back to main menu";
        break;
    }
}
void deletionSubMenu(int inputArray[], int &arraySize, int userInput)
{
    switch (userInput)
    {
        int removingPosition;

    case 0:
        cout << "Going back to main menu." << endl;

        break;
    case 1: // deletion at start
        for (int i = 0; i < arraySize - 1; i++)
        {
            inputArray[i] = inputArray[i + 1];
        }
        cout << "New Array is: ";
        arraySize--;
        traverseArray(inputArray, arraySize);

        break;
    case 2:
        cout << "Enter the positon where you want to delete the number:";
        cin >> removingPosition;
        if (removingPosition > arraySize)
        {
            cout << "Invalid Position going back to main menu" << endl;
            break;
        }
        for (int i = removingPosition - 1; i < arraySize - 1; i++)
        {
            inputArray[i] = inputArray[i + 1];
        }
        cout << "New Array is: ";
        arraySize--;
        traverseArray(inputArray, arraySize);

        break;
    case 3: // deletion at end
        arraySize--;
        cout << "New Array is: ";
        traverseArray(inputArray, arraySize);

        break;
    default:
        cout << "Invalid choice going back to main menu";
        break;
    }
}

int linearSearch(int iArray[], int sizeOfArray, int key)
{
    for (int i = 0; i < sizeOfArray; i++)
    {
        if (iArray[i] == key)
            return i;
    }
    return -1;
}
int binarySearch(int inputArray[], int &arraySize, int key)
{
    cout << "If your array is not sorted then element position will be wrong in array" << endl;
    insertionSort(inputArray, arraySize);
    int start = 0;
    int end = arraySize - 1;
    while (start <= end)
    {
        int mid;
        mid = start + (end - start) / 2;
        if (inputArray[mid] == key)
        {
            return mid;
        }
        if (inputArray[mid] < key)
        {
            start = mid + 1;
        }
        if (inputArray[mid] > key)
        {
            end = mid - 1;
        }
    }
    return -1;
}
int recursiveBinarySearch(int array[], int start, int end, int key)
{
    cout << "If your array is not sorted then element position will be wrong in array" << endl;
    if (start <= end)
    {

        int mid = start + (end - start) / 2;
        if (array[mid] == key)
            return mid;
        if (array[mid] < key)
            return recursiveBinarySearch(array, mid + 1, end, key);
        if (array[mid] > key)
            return recursiveBinarySearch(array, start, mid - 1, key);
    }

    return -1;
}

int main()
{
    cout << "Please enter number of element you want to add." << endl;

    int arraySize = 0;
    cin >> arraySize;
    cout << endl;
    cout << "Please enter " << arraySize << " integer digit to view all opertations which can be performed." << endl;
    int inputArray[maxArraySize];

    // getting array values
    for (int i = 0; i < arraySize; i++)
    {
        cin >> inputArray[i];
        cout << endl;
    }
    int userInput = 0;

    while (userInput != 10)
    {

        mainMenu();

        cin >> userInput;
        cout << endl;

        switch (userInput)
        {
        case 1:
        { // traverse the array
            traverseArray(inputArray, arraySize);
            break;
        }
        case 2:
        {
            insertionMenu();

            cin >> userInput;
            cout << endl;

            insertionSubMenu(inputArray, arraySize, userInput);
            break;
        }

        case 3:
        {
            deletionMenu();

            cin >> userInput;
            cout << endl;

            deletionSubMenu(inputArray, arraySize, userInput);
            break;
        }
        case 4:
        {
            int searchingElement;
            cout << "Enter Number you want to search:";
            cin >> searchingElement;
            cout << endl;
            int linearsearchResult = linearSearch(inputArray, arraySize, searchingElement);
            linearsearchResult == -1 ? cout << "Element not found" << endl : cout << "Element found at " << linearsearchResult + 1 << endl;
            break;
        }
        case 5:
        {
            int searchingElement;
            cout << "Enter Number you want to search:";
            cin >> searchingElement;
            cout << endl;
            int binarySearchResult = binarySearch(inputArray, arraySize, searchingElement);
            binarySearchResult == -1 ? cout << "Element not found" << endl : cout << "Element found at " << binarySearchResult + 1 << endl;
            break;
        }
        case 6:
        {
            int searchingElement;
            cout << "Enter Number you want to search:";
            cin >> searchingElement;
            cout << endl;
            insertionSort(inputArray, arraySize); // sorting before sending array for binary search
            int recursiveBinarySearchResult = recursiveBinarySearch(inputArray, 0, arraySize - 1, searchingElement);
            recursiveBinarySearchResult == -1 ? cout << "Element not found" << endl : cout << "Element found at " << recursiveBinarySearchResult + 1 << endl;
            break;
        }
        case 7:
            insertionSort(inputArray, arraySize);
            traverseArray(inputArray, arraySize);
            break;
        case 10:
            cout << "Exiting program";
            break;
        default:
            cout << "Wrong input please choose another input" << endl;
            break;
        }
    }
    return 0;
}