Arrays//Vectors:

In C++, both vectors and arrays are used to store sequences of elements, but
they have significant differences in terms of flexibility, functionality, and use
cases. Here's a comparison of the two:

1. **Size and Flexibility**

- **Array**:
- **Fixed Size**: The size of an array must be specified at compile time and
cannot be changed during runtime.
- **Static Allocation**: Arrays can be statically or dynamically allocated, but their
size remains constant after allocation.

- **Vector**:
- **Dynamic Size**: Vectors can change size dynamically. You can add or
remove elements, and the vector will automatically adjust its size.
- **Dynamic Allocation**: Vectors handle dynamic memory allocation internally
and can grow or shrink as needed.

2. **Memory Management**

- **Array**:
- **Manual Management**: If you use dynamically allocated arrays, you must
manually manage the memory (using `new` and `delete`).

- **Vector**:
- **Automatic Management**: Vectors automatically manage their own memory.
When elements are added or removed, vectors handle memory allocation and
deallocation automatically.

3. **Functionality**

- **Array**:
 - **Limited Functionality**: Arrays provide basic functionality for storing and
accessing elements.
- **No Built-in Methods**: Arrays do not have built-in methods for operations like
adding, removing, or searching for elements.

- **Vector**:
- **Rich Functionality**: Vectors provide a wide range of built-in methods (e.g.,
`push_back`, `pop_back`, `insert`, `erase`, `clear`).
- **STL Integration**: Vectors are part of the Standard Template Library (STL)
and can be used with other STL algorithms and containers.

4. **Performance**

- **Array**:
- **Better Cache Locality**: Because arrays are contiguous in memory, they
often have better cache performance.
- **Lower Overhead**: Arrays have less overhead because they do not manage
dynamic memory or additional metadata.

- **Vector**:
- **Slight Overhead**: Vectors may have a slight performance overhead due to
dynamic memory management and additional metadata (like capacity and size).

5. **Syntax and Usage**

- **Array**:
```cpp
int arr[5]; // Statically allocated array
int* arr = new int[5]; // Dynamically allocated array
arr[0] = 1; // Accessing an element
```

- **Vector**:
```cpp
#include <vector>
std::vector<int> vec; // Dynamic vector
vec.push_back(1); // Adding an element
 int firstElement = vec[0]; // Accessing an element
```

6. **Safety and Convenience**

- **Array**:
- **Less Safe**: Manual memory management with dynamic arrays can lead to
memory leaks and pointer errors.
- **No Bounds Checking**: Accessing elements outside the bounds of the array
is undefined behavior and can cause crashes.

- **Vector**:
- **Safer**: Automatic memory management reduces the risk of memory leaks
and pointer errors.
- **Bounds Checking**: The `at` method provides bounds checking, throwing an
exception if you access out-of-bounds elements.

Summary

- Use **arrays** when you need a fixed-size sequence and performance is

critical, and you are confident in managing memory manually.
- Use **vectors** when you need a dynamic sequence that can grow or shrink,
and you prefer the convenience and safety of automatic memory management
and built-in methods.

In most cases, vectors are preferred due to their flexibility and ease of use.
Arrays are typically used in performance-critical code or where fixed-size
collections are required.

FILE HANDLING
We can access various file handling methods in C++ by importing the <fstream>
class.

#include <fstream>
<fstream> includes two classes for file handling:

● ifstream - to read from a file.

● ofstream - to create/open and write to a file.

For example, here's how we can open a file using ofstream:

std::ofstream my_file("example.txt");
Here,

my_file - the name of the object of the ofstream class.

example.txt - the name and extension of the file we want to open.
Note: We can also use the open() function to open a file. For example,

std::ofstream my_file.open("example.txt");

FILE WRITING:
We can then write to the file by using the insertion operator << with the ofstream
object my_file. For example:

// write multiple lines to the file

my_file << "Line 1" << endl;
my_file << "Line 2" << endl;
my_file << "Line 3" << endl;

// close the file

my_file.close();

To add/append to the existing content of a file, you need to open the file in
append mode.

In C++, you can achieve this by using the ios::app flag when opening the file:
ofstream my_file("example.txt", ios::app);

ios::in Opens the file to read (default for ifstream).

 ios::out Opens the file to write (default for ofstream).

ios::app Opens the file and appends new content to itat the end.

Why are constructors important?

Constructors are necessary because they automate the initialization of objects,
ensuring consistency, encapsulation, and proper resource management. They
make it easier and safer to create and use objects, reducing the likelihood of
errors related to uninitialized or improperly initialized objects.

LINKED LIST
● Singly linked list
● Doubly linked list

Singly Linked List:

Stack Data Structure

A Stack is a linear data structure that follows a particular order in which the
operations are performed. The order may be LIFO(Last In First Out) or
FILO(First In Last Out). LIFO implies that the element that is inserted last,
comes out first and FILO implies that the element that is inserted first, comes out
last.
QUEUE
Queues are a fundamental data structure in computer science which works on
the principle of FIFO (First In, First Out). They can be implemented using both
array and linked list. A circular queue is a type of queue in which the last element
is connected to the first element, forming a circular structure.
deQueue() This function is used to delete an element from the circular queue. In
a circular queue, the element is always deleted from the front position
enQueue(value) This function is used to insert an element into the circular
queue. In a circular queue, the new element is always inserted at the rear
position.

FRONT IS THE OLDEST ELEMENT AND REAR IS THE NEWEST ELEMENT

CODE:

#include <iostream>
#include <vector>
using namespace std;
class CircularQueue
{
// int *data;
vector<int> data; // using vectors to dynamically alocate the size of the array
int s; // initializing size of the array/vector
int front, rear;
public:
 CircularQueue(int s) : s(s), data(s) // discovered new method to initialise and is called
'INITIALISER LIST'
{
front = rear = -1; // setting both front and rear at the start
};
void isfull()
{
if (front == (rear + 1) % s)
{
cout << "Queue is full" << endl;
}
else
{
cout << "Queue is not full" << endl;
}
}
void Enqueue()
{
if (front == (rear + 1) % s)
{
cout << "Queue is full" << endl;
}
else
{
int item;
cout << "Enter the item to be inserted: ";
cin >> item;
rear = (rear + 1) % s;
data[rear] = item;
 if (front == -1) // incrementing front after inserting element, this only happens for the
first element inserted
{
front = 0;
}
cout << "Item inserted successfully" << endl;
}
}
void Dequeue()
{
if (rear == -1)
{
cout << "Empty" << endl;
return;
}
int temp = data[front]; //retrives the first element
if (front == rear) //only one element present in the queue
{
rear = -1;
front = -1;
}
else
{
int temp = data[front];
front = (front + 1) % s;
}
}
void display()
{
if (front == -1)
 {
cout << "Queue is empty" << endl;
}
else
{
for (int i = front; i <= rear; i++)
{
cout << data[i] << " ";
}
}
}
};
int main()
{
int s;
cout << "Enter the length of the vector: \n";
cin >> s;
CircularQueue q(s);
int user = 0;
do
{
cout << endl;
cout << "Choose the task: " << endl;
cout << "1)Display Queue" << endl;
cout << "2)Enqueue" << endl;
cout << "3)Dequeue" << endl;
cout << "4)Is empty?" << endl;
cout << "0)Exit" << endl;
cout << "------------------------------------------------------------------"
"------------------------------------------"
 << endl;
cin >> user;
switch (user)
{
case 1:
cout << "\nQueue:\n";
q.display();
// cout <<
//
"------------------------------------------------------------------------------------------------------------"
// << endl;
break;
case 2:
cout << "\nInsert data:\n";
q.Enqueue();
// cout <<
//
"------------------------------------------------------------------------------------------------------------"
// << endl;
cout << endl;
break;
case 3:
cout << "\nRemove data:\n";
q.display();
cout << endl;
q.Dequeue();
cout << endl;
cout << endl;
// cout <<
//
"------------------------------------------------------------------------------------------------------------"
 // << endl;
break;
case 4:
cout << "\nIs queue empty?\n";
q.isfull();
cout << "----------------------------------------------------------------"
"--------------------------------------------"
<< endl;
break;
default:
cout << "Thank you!" << endl;
break;
}
} while (user != 0);
return 0;
}

SEARCHING AND SORTING

● LINEAR SEARCH
Start from the leftmost element of arr[] and one by one compare x with
each element of arr[]
If x matches with an element, return the index.
If x doesn’t match with any of the elements, return -1.
Most simple and have the highest time complexity.
● BINARY SEARCH
Binary Search is a search algorithm that is faster than the linear search
algorithm. Binary Search is used to search the position of the target
element in a sorted array by repeatedly dividing the search space in half.
Binary search eliminates half portion of the array with each comparison.
Working: The idea is to compare the middle element with the target value,
if the middle element is equal to the target value, the index of the middle
element is the position of the target value.
If the target value is smaller than the middle element, the target value is
searched in the left half of the current space and If the target value is
greater than the middle element, the target value is searched in the right
half of the current space. This is done until the target element is found if
the element is present in the array.
● BUBBLE SORT
Bubble Sort Algorithm is the simplest sorting algorithm that works by
repeatedly swapping the adjacent elements if they are in the wrong order.
This algorithm is not suitable for large data sets as its average and worst-
case time complexity is quite high.
Example:

arr[] = {5, 1, 4, 2, 8}

Bubble sort starts with the very first two elements, comparing them to
check which one is greater.

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two

elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in
order (8 > 5), the algorithm does not swap them.
 Second Traversing
Now, during second iteration it should look like this:

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Third Traversing
Now, the array is already sorted, but our algorithm does not know if it is
completed.
The algorithm needs one whole pass without any swap to know it is sorted.

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Output:
// Sorted
arr=[1,2,4,5,8]

● INSERTION SORT
Insertion sort is a simple sorting algorithm that builds the sorted array one
element at a time.
● The first element of the array is assumed to be a sorted subarray.
● Start with the element at index 1 and store it in a variable key.
● Compare the current element key with the elements in the sorted
subarray from right to left (elements at indices from j = i-1 to j = 0).
● Shift elements greater than the key one position to the right to make
space for the current element until it finds a smaller element than the
key and j is not zero.
● When the correct position for the key is found, it is inserted at arr[j +
1].
 ● Repeat these steps for the remaining elements of the unsorted
subarray until the complete array is sorted.

● QUICK SORT [sabse difficult yhi lagta hai]

The key process in quickSort is the partition() process. The aim of the
partition() function is to receive an array and an element x of the array as a
pivot, put x at its correct position in a sorted array, and then put all smaller
elements (smaller than x) before x, and put all greater elements (greater
than x) after x.

CODE:
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

struct SE9
{
int roll_no;
string name;
float cgpa;
};

class SE9IT
{
private:
vector<SE9> students;

public:
void get_data(int n);
void display();
void Linear_search(float key);
void Binary_search(string key);
void Bubble_sort();
void insertion_sort();
void quick_sort(int, int);
int partition(int, int);
};

void SE9IT::get_data(int n)
{
students.resize(n);
for (int i = 0; i < n; i++)
{
cout << "Enter the roll no: ";
cin >> students[i].roll_no;
cout << "Enter the name: ";
cin >> students[i].name;
cout << "Enter the cgpa: ";
cin >> students[i].cgpa;
}
}

void SE9IT::display()
{
cout << "\tRoll No" << setw(10) << "Name" << setw(10) << "CGPA" << endl;
for (int i = 0; i < students.size(); i++)
{
cout << i + 1 << setw(10) << students[i].roll_no << setw(15)
<< students[i].name << setw(10) << students[i].cgpa << endl;
}
}

void SE9IT::Linear_search(float key)

{
bool found = false;
cout << "Enter the CGPA to be searched: ";
cin >> key;
cout << "\tRoll No" << setw(10) << "Name" << setw(10) << "CGPA" << endl;
for (int i = 0; i < students.size(); i++)
{
if (key == students[i].cgpa)
{
found = true;
cout << i + 1 << setw(10) << students[i].roll_no << setw(10)
<< students[i].name << setw(10) << students[i].cgpa << endl;
}
}
if (!found)
{
cout << "CGPA not found" << endl;
}
}

void SE9IT::Bubble_sort() //used here for roll numbers

{

for (int i = 0; i < students.size() - 1; i++)

{
for (int j = 0; j < students.size() - i - 1; j++)
{
if (students[j].roll_no > students[j + 1].roll_no)
{
// swaping
SE9 temp = students[j];
 students[j] = students[j + 1];
students[j + 1] = temp;
}
}
}
}

void SE9IT::Binary_search(string key)

{
insertion_sort();
cout << "Enter student name to be searched: " << endl;
cin >> key;
int low = 0;
int high = students.size() - 1; // array length - 1

while (low <= high)

{
int mid = (low + high) / 2;
if (students[mid].name == key)
{
cout << "Roll No" << setw(15) << "Name" << setw(10) << "CGPA" << endl;
cout << students[mid].roll_no << setw(15) << students[mid].name
<< setw(10) << students[mid].cgpa << endl;

break;
}
if (key > students[mid].name)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
}

void SE9IT::insertion_sort()
{
int n = students.size();
for (int i = 1; i < n; i++)
 {
SE9 temp = students[i]; // Store the current element
int j = i - 1;
while (j >= 0 && students[j].name > temp.name) //Compares the ASCII values
(lexicography)
{
students[j + 1] = students[j];
j--;
}

students[j + 1] = temp; // Place temp in its correct position

}
}

void SE9IT::quick_sort(int start, int end)

{
if (start < end)
{
int pivot = partition(start, end);
quick_sort(start, pivot - 1);
quick_sort(pivot + 1, end);
}
}

int SE9IT::partition(int start, int end)

{
float pivot = students[end].cgpa;
int i = start - 1;

for (int j = start; j < end; j++)

{
if (students[j].cgpa > pivot)
{
i++;
swap(students[i], students[j]);
}
}
swap(students[i + 1], students[end]);
return i + 1;
}
int main()
{
SE9IT s;
int n;
cout << "Enter number of students: " << endl;
cin >> n;
s.get_data(n);

float search_key = 0;
string key;

int user = 0;
do
{
cout << endl;
cout << "Choose the task: " << endl;
cout << "1)Display without Sorting" << endl;
cout << "2)Search CGPA" << endl;
cout << "3)Bubble Sort" << endl;
cout << "4)Binary Search" << endl;
cout << "5)Insertion Sort" << endl;
cout << "6)Quick Sort" << endl;
cout << "0)Exit" << endl;
cout << "------------------------------------------------------------------"
"------------------------------------------"
<< endl;

cin >> user;

switch (user)
{
case 1:
cout << "\nStudent List before sorting:\n";
s.display();
cout << "----------------------------------------------------------------"
"--------------------------------------------"
<< endl;

break;

case 2:
 cout << "\nStudent List by CGPA:\n";
s.Linear_search(search_key);
cout << "----------------------------------------------------------------"
"--------------------------------------------"
<< endl;
break;

case 3:
cout << "\nStudent List after sorting by Roll number:\n";
s.Bubble_sort();
s.display();
cout << "----------------------------------------------------------------"
"--------------------------------------------"
<< endl;
break;

case 4:
cout << "\nName Search\n";
s.insertion_sort();
s.Binary_search(key);
cout << "----------------------------------------------------------------"
"--------------------------------------------"
<< endl;
break;

case 5:
cout << "\nStudent List after sorting by Name:\n"
<< endl;
s.insertion_sort();
s.display();
break;

case 6:
cout << "\nStudent List after sorting by CGPA:\n";
s.quick_sort(0, n - 1);
s.display();

default:
cout << "Thank you!" << endl;
break;
}
 } while (user != 0);

return 0;
}