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