KEMBAR78
DSA Lab-03 | PDF | Algorithms And Data Structures | Information Retrieval
Scribd
Upload
62 views23 pages

DSA Lab-03

The document contains code snippets for implementing various data structures and algorithms such as quicksort, radix sort, interpolation search, exponential search, and binary search trees. It includes functions for operations on each data structure like insertion, deletion, finding minimum/maximum elements, and traversing trees. Test code is provided to take input, call the functions, and output the results.

Uploaded by

sujithvarman46
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
62 views23 pages

DSA Lab-03

The document contains code snippets for implementing various data structures and algorithms such as quicksort, radix sort, interpolation search, exponential search, and binary search trees. It includes functions for operations on each data structure like insertion, deletion, finding minimum/maximum elements, and traversing trees. Test code is provided to take input, call the functions, and output the results.

Uploaded by

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

DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

1.Ans:

#include <iostream>
#include <vector>

using namespace std;

//function perform the array into two segments


int partesian(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++;
swap(arr[i],arr[j]);
}
}
swap(arr[i+1], arr[high]);
return i+1;
}

//function to perform quick sort


void quicksort(int arr[], int low, int high)
{
if(low<high){
int pivotIndex = partesian(arr, low, high);

//recursively sort elements before and after the pivot


quicksort(arr, low, pivotIndex-1);
quicksort(arr, pivotIndex+1, high);
}
}

int main()
{
int n;
cin>>n;
int arr[n];

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


cin>>arr[i];
}

quicksort(arr,0,n-1);
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

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


cout<<arr[i]<<" ";
}

return 0;
}

1. Q
#include <iostream>
#include <vector>

using namespace std;

// A utility function to get the maximum value in arr[]


int getMax(vector<int>& arr) {
int max = arr[0];
for (size_t i = 1; i < arr.size(); i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}

// A counting sort of arr[] based on the digit represented by exp.


void countingSort(vector<int>& arr, int exp) {
const int n = arr.size();
vector<int> output(n);
vector<int> count(10, 0);

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


count[(arr[i] / exp) % 10]++;
}

for (int i = 1; i < 10; i++) {


count[i] += count[i - 1];
}

for (int i = n - 1; i >= 0; i--) {


output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

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


arr[i] = output[i];
}
}
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Main Radix Sort function


void radixSort(vector<int>& arr) {
int max = getMax(arr);

for (int exp = 1; max / exp > 0; exp *= 10) {


countingSort(arr, exp);
}
}

int main() {
int n;
cin >> n;

vector<int> arr(n);

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


cin >> arr[i];
}

radixSort(arr);

cout << "";


for (int num : arr) {
cout << num << " ";
}

return 0;
}

3.Q

#include <iostream>

using namespace std;

int interpolationSearch(int arr[], int n, int key) {

//for sorted array

int low = 0;

int high = n - 1;

//cout << "\nKey: " <<key<< endl;

//cout << "\nlow: " <<low<< endl;

//cout << "\nhigh: " <<high<< endl;


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

while (low <= high && key >= arr[low] && key <= arr[high]) {

if (low == high) {

if (arr[low] == key)

return low;

return -1;

// Interpolation formula to estimate the position

int pos = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low]));

//cout << "\npos: " <<pos;

//cout << "\narr["<<pos<<"]: " <<arr[pos]<< endl;

if (arr[pos] == key)

return pos;

else if (arr[pos] < key)

low = pos + 1;

else

high = pos - 1;

return -1;

int main() {

int n;

//cout << "Enter the number of elements: ";

cin >> n;

int arr[n+1];

//cout << "Enter the elements in sorted order: ";

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


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

cin >> arr[i];

int key, position;

//cout << "Enter the key element to search: ";

cin >> key;

//cout << "\ninput Key: " <<key<< endl;

position = interpolationSearch(arr, n+1, key);

//cout << "\nPosition: " <<position<< endl;

if (position == -1) {

cout << "Key not found" << endl;

else {

cout << "Element " << key << " found in position " << position+1<< endl;

return 0;

4.Q

#include <iostream>

using namespace std;

int min(int a, int b)

return(a<b?a:b);

}
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

int binarySearch(int arr[], int low, int high, int key) {

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == key)

return mid;

else if (arr[mid] < key)

low = mid + 1;

else

high = mid - 1;

return -1;

int exponentialSearch(int arr[], int n, int key) {

if (arr[0] == key)

return 0;

int i = 1;

while (i < n && arr[i] <= key)

i *= 2;

return binarySearch(arr, i / 2, std::min(i, n - 1), key); // Use std::min from the <algorithm> header

int main() {

int n;

//cout << "Enter the number of elements: ";

cin >> n;

int arr[n+1];

//cout << "Enter the elements in sorted order: ";


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

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

cin >> arr[i];

int key;

//cout << "Enter the key element to search: ";

cin >> key;

int position = exponentialSearch(arr, n+1, key);

if (position != -1) {

cout << "Element " << key << " found in position " << position << endl;

} else {

cout << "Key not found" << endl;

return 0;

4.Q

#include <iostream>

using namespace std;

int min(int a, int b)

return(a<b?a:b);

int binarySearch(int arr[], int low, int high, int key) {

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == key)

return mid;
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

else if (arr[mid] < key)

low = mid + 1;

else

high = mid - 1;

return -1;

int exponentialSearch(int arr[], int n, int key) {

if (arr[0] == key)

return 0;

int i = 1;

while (i < n && arr[i] <= key)

i *= 2;

return binarySearch(arr, i / 2, std::min(i, n - 1), key); // Use std::min from the <algorithm> header

int main() {

int n;

//cout << "Enter the number of elements: ";

cin >> n;

int arr[n+1];

//cout << "Enter the elements in sorted order: ";

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

cin >> arr[i];

int key;
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

//cout << "Enter the key element to search: ";

cin >> key;

int position = exponentialSearch(arr, n+1, key);

if (position != -1) {

cout << "Element " << key << " found in position " << position << endl;

} else {

cout << "Key not found" << endl;

return 0;

5.q

#include <iostream>

using namespace std;

// Definition of a Binary Search Tree node

struct Node {

int data;

Node* left;

Node* right;

Node(int val) : data(val), left(nullptr), right(nullptr) {}

};

// Function to insert a new node into the BST

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

if (root == nullptr) {

return new Node(val);


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

if (val < root->data) {

root->left = insert(root->left, val);

} else if (val > root->data) {

root->right = insert(root->right, val);

return root;

// Function to find the minimum value node in a BST

Node* findMin(Node* root) {

while (root->left != nullptr) {

root = root->left;

return root;

// Function to delete a node with a given key from the BST

Node* deleteNode(Node* root, int key) {

if (root == nullptr) {

return root;

if (key < root->data) {

root->left = deleteNode(root->left, key);

} else if (key > root->data) {

root->right = deleteNode(root->right, key);

} else {

if (root->left == nullptr) {

Node* temp = root->right;

delete root;

return temp;
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

} else if (root->right == nullptr) {

Node* temp = root->left;

delete root;

return temp;

Node* temp = findMin(root->right);

root->data = temp->data;

root->right = deleteNode(root->right, temp->data);

return root;

// Function to perform in-order traversal

void inOrder(Node* root) {

if (root == nullptr) return;

inOrder(root->left);

cout << root->data << " ";

inOrder(root->right);

// Function to perform pre-order traversal

void preOrder(Node* root) {

if (root == nullptr) return;

cout << root->data << " ";

preOrder(root->left);

preOrder(root->right);

// Function to perform post-order traversal

void postOrder(Node* root) {

if (root == nullptr) return;


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

postOrder(root->left);

postOrder(root->right);

cout << root->data << " ";

int main() {

Node* root = nullptr;

int n;

cin >> n;

cout << "";

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

int val;

cin >> val;

root = insert(root, val);

cout << "";

inOrder(root);

cout << endl;

cout << "";

preOrder(root);

cout << endl;

cout << "";

postOrder(root);

cout << endl;

// Delete 6 and perform in-order traversal


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

root = deleteNode(root, 6);

cout << "";

inOrder(root);

cout << endl;

// Insert 8 and perform in-order traversal

root = insert(root, 8);

cout << "";

inOrder(root);

cout << endl;

// Delete 5 and perform in-order traversal

root = deleteNode(root, 5);

cout << "";

inOrder(root);

cout << endl;

return 0;

6.q

#include <iostream>

using namespace std;

// Definition of a Binary Search Tree node

struct Node {

int data;

Node* left;

Node* right;

Node(int val) : data(val), left(nullptr), right(nullptr) {}

};
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Function to insert a new node into the BST

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

if (root == nullptr) {

return new Node(val);

if (val < root->data) {

root->left = insert(root->left, val);

} else if (val > root->data) {

root->right = insert(root->right, val);

return root;

// Function to find the minimum value node in a BST

Node* findMin(Node* root) {

while (root->left != nullptr) {

root = root->left;

return root;

// Function to perform in-order traversal

void inOrder(Node* root) {

if (root == nullptr) return;

inOrder(root->left);

cout << root->data << " ";

inOrder(root->right);

int main() {
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

Node* root = nullptr;

int n;

cin >> n;

cout << "";

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

int val;

cin >> val;

root = insert(root, val);

cout << "";

inOrder(root);

cout << endl;

return 0;

7.q

#include <iostream>

using namespace std;

// Structure for an AVL tree node

struct AVLNode {

int data;

AVLNode* left;

AVLNode* right;

int height;

};

// Function to calculate the height of a node

int height(AVLNode* node) {


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

if (node == nullptr) return 0;

return node->height;

// Function to calculate the balance factor of a node

int balanceFactor(AVLNode* node) {

if (node == nullptr) return 0;

return height(node->left) - height(node->right);

// Function to create a new AVL tree node

AVLNode* createNode(int key) {

AVLNode* newNode = new AVLNode;

newNode->data = key;

newNode->left = newNode->right = nullptr;

newNode->height = 1;

return newNode;

// Function to perform a right rotation

AVLNode* rightRotate(AVLNode* y) {

AVLNode* x = y->left;

AVLNode* T2 = x->right;

x->right = y;

y->left = T2;

y->height = max(height(y->left), height(y->right)) + 1;

x->height = max(height(x->left), height(x->right)) + 1;

return x;
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Function to perform a left rotation

AVLNode* leftRotate(AVLNode* x) {

AVLNode* y = x->right;

AVLNode* T2 = y->left;

y->left = x;

x->right = T2;

x->height = max(height(x->left), height(x->right)) + 1;

y->height = max(height(y->left), height(y->right)) + 1;

return y;

// Function to insert a key into the AVL tree

AVLNode* insert(AVLNode* root, int key) {

if (root == nullptr) return createNode(key);

if (key < root->data) {

root->left = insert(root->left, key);

} else if (key > root->data) {

root->right = insert(root->right, key);

} else {

return root;

root->height = 1 + max(height(root->left), height(root->right));

int balance = balanceFactor(root);


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

if (balance > 1) {

if (key < root->left->data) {

return rightRotate(root);

} else if (key > root->left->data) {

root->left = leftRotate(root->left);

return rightRotate(root);

if (balance < -1) {

if (key > root->right->data) {

return leftRotate(root);

} else if (key < root->right->data) {

root->right = rightRotate(root->right);

return leftRotate(root);

return root;

// Function to perform in-order traversal

void inOrderTraversal(AVLNode* root) {

if (root == nullptr) return;

inOrderTraversal(root->left);

cout << root->data << " ";

inOrderTraversal(root->right);

}
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

// Function to perform pre-order traversal

void preOrderTraversal(AVLNode* root) {

if (root == nullptr) return;

cout << root->data << " ";

preOrderTraversal(root->left);

preOrderTraversal(root->right);

// Function to perform post-order traversal

void postOrderTraversal(AVLNode* root) {

if (root == nullptr) return;

postOrderTraversal(root->left);

postOrderTraversal(root->right);

cout << root->data << " ";

int main() {

AVLNode* root = nullptr;

int n, num;

cin >> n;

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

cin >> num;

root = insert(root, num);

preOrderTraversal(root);

cout << endl;


DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

inOrderTraversal(root);

cout << endl;

postOrderTraversal(root);

cout << endl;

return 0;

8.Q

#include <iostream>

using namespace std;

const int ORDER = 3;

// Structure for a B-tree node

struct BTreeNode {

int keys[ORDER - 1]; // Data elements

BTreeNode* children[ORDER]; // Child pointers

int numKeys; // Number of keys

};

// Function to create a new B-tree node

BTreeNode* createNode(int key) {

BTreeNode* newNode = new BTreeNode;

newNode->keys[0] = key;

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

newNode->children[i] = nullptr;

}
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

newNode->numKeys = 1;

return newNode;

// Function to insert a key into the B-tree

BTreeNode* insert(BTreeNode* root, int key) {

if (root == nullptr) {

return createNode(key);

if (root->numKeys < ORDER - 1) {

int i = root->numKeys - 1;

while (i >= 0 && key < root->keys[i]) {

root->keys[i + 1] = root->keys[i];

i--;

root->keys[i + 1] = key;

root->numKeys++;

} else {

int i = root->numKeys - 1;

while (i >= 0 && key < root->keys[i]) {

i--;

if (root->children[i + 1] != nullptr) {

root->children[i + 1] = insert(root->children[i + 1], key);

} else {

root->children[i + 1] = createNode(key);

}
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

return root;

// Function to traverse the B-tree and display the contents

void traverseBTree(BTreeNode* root) {

if (root != nullptr) {

for (int i = 0; i < root->numKeys; i++) {

cout << root->keys[i] << " ";

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

traverseBTree(root->children[i]);

int main() {

BTreeNode* root = nullptr;

int n, key;

n = 10;

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

cin >> key;

root = insert(root, key);

traverseBTree(root);

cout << endl;

return 0;

}
DATA STRUCTURE AND ALGORITHM LAB ASSESSMENT-03

You might also like