1
#include <iostream>
2
#include <fstream>
3
#include <ctime>
4
using namespace std;
5
 
6
// Function to generate a random array
7
void generateRandomArray(int arr[], int n) {
8
    srand(time(0));
9
    for (int i = 0; i < n; ++i) {
10
        arr[i] = rand() % 100; // Random numbers between 0 and 99
11
    }
12
}
13
 
14
// Function to display the array
15
void displayArray(int arr[], int n) {
16
    for (int i = 0; i < n; ++i) {
17
        cout << arr[i] << " ";
18
    }
19
    cout << endl;
20
}
21
 
22
// Function to manually sort the array using Bubble Sort
23
void manualSort(int arr[], int n) {
24
    for (int i = 0; i < n - 1; ++i) {
25
        for (int j = 0; j < n - i - 1; ++j) {
26
            if (arr[j] > arr[j + 1]) {
27
                // Manual swap
28
                int temp = arr[j];
29
                arr[j] = arr[j + 1];
30
                arr[j + 1] = temp;
31
            }
32
        }
33
    }
34
}
35
 
36
// Function to display the menu
37
void displayMenu() {
38
    cout << "\nMenu:\n";
39
    cout << "1. Insert Element\n";
40
    cout << "2. Delete Element\n";
41
    cout << "3. Search Element\n";
42
    cout << "4. Display Array\n";
43
    cout << "5. Save to File\n";
44
    cout << "6. Exit\n";
45
    cout << "Enter your choice: ";
46
}
47
 
48
// Function to find the position for insertion or deletion using binary search
49
int binarySearch(int arr[], int n, int target, bool findLast = false) {
50
    int low = 0, high = n - 1, result = -1;
51
    while (low <= high) {
52
        int mid = (low + high) / 2;
53
        if (arr[mid] == target) {
54
            result = mid;
55
            if (findLast) {
56
                low = mid + 1; // Search to the right for last occurrence
57
            } else {
58
                high = mid - 1; // Search to the left for first occurrence
59
            }
60
        } else if (arr[mid] < target) {
61
            low = mid + 1;
62
        } else {
63
            high = mid - 1;
64
        }
65
    }
66
    return result == -1 ? low : result; // Return position for insertion
67
}
68
 
69
// Function to insert an element into the array
70
void insertElement(int arr[], int& n, int value) {
71
    if (n >= 100) {
72
        cout << "Overflow: Cannot insert more elements.\n";
73
        return;
74
    }
75
    int pos = binarySearch(arr, n, value, true) + 1; // Insert after last occurrence
76
    for (int i = n; i > pos; --i) {
77
        arr[i] = arr[i - 1]; // Shift elements to the right
78
    }
79
    arr[pos] = value;
80
    ++n; // Increase array size
81
    cout << "Element inserted successfully.\n";
82
}
83
 
84
// Function to delete an element from the array
85
void deleteElement(int arr[], int& n, int value) {
86
    int pos = binarySearch(arr, n, value, true); // Find last occurrence
87
    if (pos >= 0 && pos < n && arr[pos] == value) {
88
        cout << "Deleting element at position: " << pos + 1 << endl;
89
        for (int i = pos; i < n - 1; ++i) {
90
            arr[i] = arr[i + 1]; // Shift elements to the left
91
        }
92
        --n; // Decrease array size
93
        cout << "Element deleted successfully.\n";
94
    } else {
95
        cout << "Item not found.\n";
96
    }
97
}
98
 
99
// Function to search for an element in the array
100
void searchElement(int arr[], int n, int value) {
101
    int pos = binarySearch(arr, n, value);
102
    if (pos < n && arr[pos] == value) {
103
        cout << "Element found at position (first occurrence): " << pos + 1 << endl;
104
    } else {
105
        cout << "Element not found.\n";
106
    }
107
}
108
 
109
// Function to save the array to a file
110
void saveToFile(int arr[], int n) {
111
    ofstream outFile("sorted_array.txt");
112
    if (outFile.is_open()) {
113
        for (int i = 0; i < n; ++i) {
114
            outFile << arr[i] << " ";
115
        }
116
        outFile.close();
117
        cout << "Array saved to file 'sorted_array.txt'.\n";
118
    } else {
119
        cout << "Error: Unable to save to file.\n";
120
    }
121
}
122
 
123
// Main function
124
int main() {
125
    int arr[100];
126
    int n = 10; // Initial size of the array
127
    generateRandomArray(arr, n);
128
    cout << "Original Array: ";
129
    displayArray(arr, n);
130
 
131
    manualSort(arr, n);
132
    cout << "Sorted Array: ";
133
    displayArray(arr, n);
134
 
135
    while (true) {
136
        displayMenu();
137
        int choice;
138
        cin >> choice;
139
 
140
        switch (choice) {
141
        case 1: {
142
            cout << "Enter element to insert: ";
143
            int value;
144
            cin >> value;
145
            insertElement(arr, n, value);
146
            break;
147
        }
148
        case 2: {
149
            cout << "Enter element to delete: ";
150
            int value;
151
            cin >> value;
152
            deleteElement(arr, n, value);
153
            break;
154
        }
155
        case 3: {
156
            cout << "Enter element to search: ";
157
            int value;
158
            cin >> value;
159
            searchElement(arr, n, value);
160
            break;
161
        }
162
        case 4:
163
            cout << "Current Array: ";
164
            displayArray(arr, n);
165
            break;
166
        case 5:
167
            saveToFile(arr, n);
168
            break;
169
        case 6:
170
            cout << "Exiting program.\n";
171
            return 0;
172
        default:
173
            cout << "Invalid choice. Try again.\n";
174
        }
175
    }
176
    return 0;
177
}