Scribd
Upload
8 views

Final File Dsa

Uploaded by

Nishita Karda
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views

Final File Dsa

Uploaded by

Nishita Karda
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Searching:

1:Linear Search

#include <iostream>

int linearSearch(int arr[], int size, int target) {


for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}

int main() {
int arr[] = {5, 3, 8, 4, 2};
int size = arr.size();
int target = 4;
int result = linearSearch(arr, size, target);

if (result != -1) {
std::cout << "Element found at index: " << result << endl;
} else {
std::cout << "Element not found in the array." << endl;
}

return 0;
}
2:Binary Search
#include <iostream>

int binarySearch(int arr[], int size, int target) {


int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;

if (arr[mid] == target) {
return mid; }
else if (arr[mid] < target) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 5, 8}; // Must be sorted for binary search
int size = sizeof(arr) );
int target = 5;
int result = binarySearch(arr, size, target);

if (result != -1) {
cout << "Element found at index: " << result << endl;
} else {
cout << "Element not found in the array." << endl;
}

return 0;

}
Sorting Techniques
1,Bubble Sort
#include <iostream>

void bubbleSort(int arr[], int size) {


for (int i = 0; i < size - 1; ++i) {
for (int j = 0; j < size - i - 1; ++j) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) ;

bubbleSort(arr, size);

:cout << "Sorted array: ";


for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
cout << endl;

return 0;
}
2,Selection Sort
#include <iostream>

void selectionSort(int arr[], int size) {


for (int i = 0; i < size - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < size; ++j) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap arr[i] with arr[minIndex]
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int size = sizeof(arr[0]);

selectionSort(arr, size);

cout << "Sorted array: ";


for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
:cout << endl;

return 0;
}
3,Insertion Sort
#include <iostream>

void insertionSort(int arr[], int size) {


for (int i = 1; i < size; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

int main() {
int arr[] = {12, 11, 13, 5, 6};
int size = sizeof(arr) ;

insertionSort(arr, size);

std::cout << "Sorted array: ";


for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
cout << :endl;

return 0;
}
4,Quick sort
#include <iostream>

int partition(int arr[], int low, int high) {


int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;

int temp = arr[i];


arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}

void quickSort(int arr[], int low, int high) {


if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);


quickSort(arr, pi + 1, high);
}
}

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int size = sizeof(arr);

quickSort(arr, 0, size - 1);

cout << "Sorted array: ";


for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout <<endl;

return 0;
}
5,Merge Sort
#include <iostream>

void merge(int arr[], int left, int mid, int right) {


int n1 = mid - left + 1;
int n2 = right - mid;
int* leftArr = new int[n1];
int* rightArr = new int[n2];

for (int i = 0; i < n1; i++) {


leftArr[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
rightArr[j] = arr[mid + 1 + j];
}

int i = 0, j = 0, k = left;

while (i < n1 && j < n2) {


if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}

while (i < n1) {


arr[k] = leftArr[i];
i++;
k++;
}

while (j < n2) {


arr[k] = rightArr[j];
j++;
k++;
}

delete[] leftArr;
delete[] rightArr;
}
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}

int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);

for (int i = 0; i < size; ++i) {


printf("%d ", arr[i]);
}
printf("\n");

return 0;
}
Binary Search Tree:
#include <iostream>

struct Node {
int data;
Node* left;
Node* right;
};

Node* createNode(int data) {


Node* newNode = new Node();
newNode->data = data;
newNode->left = nullptr;
newNode->right = nullptr;
return newNode;
}

Node* insert(Node* root, int data) {


if (root == nullptr) {
return createNode(data);
}
if (data < root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}

void inOrderTraversal(Node* root) {


if (root != nullptr) {
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}

Node* search(Node* root, int data) {


if (root == nullptr || root->data == data) {
return root;
}
if (data < root->data) {
return search(root->left, data);
}
return search(root->right, data);
}

int main() {
Node* root = nullptr;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

printf("In-order traversal: ");


inOrderTraversal(root);
printf("\n");

int searchValue = 40;


Node* foundNode = search(root, searchValue);
if (foundNode != nullptr) {
printf("Node with value %d found.\n", searchValue);
} else {
printf("Node with value %d not found.\n", searchValue);
}

return 0;
}

You might also like