ds_lab

// Quicksort
#include <iostream>
using namespace std;

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

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

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

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

    cout << "Original array: ";
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    printArray(arr, size);

    return 0;
}

//Mergesort
#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = new int[n1];
    int *R = new int[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2)
    {
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    }

    while (i < n1)
        arr[k++] = L[i++];
    while (j < n2)
        arr[k++] = R[j++];
}

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);
    }
}

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

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

    cout << "Original array: ";
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted array: ";
    printArray(arr, size);

    return 0;
}

//Queue
#include <bits/stdc++.h>
using namespace std;

class Queue
{
private:
    int *arr;
    int frontIndex;
    int rearIndex;
    int capacity;
    int count;

public:
    Queue(int size)
    {
        capacity = size;
        arr = new int[capacity];
        frontIndex = 0;
        rearIndex = -1;
        count = 0;
    }

    void enqueue(int item)
    {
        if (count == capacity)
        {
            cout << "Queue is full\n";
            return;
        }
        rearIndex = (rearIndex + 1) % capacity;
        arr[rearIndex] = item;
        count++;
    }

    void dequeue()
    {
        if (isEmpty())
        {
            cout << "Queue is empty\n";
            return;
        }
        frontIndex = (frontIndex + 1) % capacity;
        count--;
    }

    int front()
    {
        if (isEmpty())
        {
            cout << "Queue is empty\n";
            return -1;
        }
        return arr[frontIndex];
    }

    bool isEmpty()
    {
        return (count == 0);
    }

    int size()
    {
        return count;
    }
};

int main()
{
    Queue q(5);

    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);

    cout << "Front: " << q.front() << endl; // Should print 10

    q.dequeue();
    cout << "Front after dequeue: " << q.front() << endl; // Should print 20

    cout << "Size: " << q.size() << endl;

    return 0;
}

//Linearprobe
#include <iostream>
using namespace std;

const int TABLE_SIZE = 10;

class HashTable
{
private:
    int *table;
    bool *occupied;

public:
    HashTable()
    {
        table = new int[TABLE_SIZE];
        occupied = new bool[TABLE_SIZE];

        for (int i = 0; i < TABLE_SIZE; i++)
        {
            table[i] = -1;
            occupied[i] = false;
        }
    }

    int hash(int key)
    {
        return key % TABLE_SIZE;
    }

    void insert(int key)
    {
        int index = hash(key);
        int startIndex = index;

        while (occupied[index])
        {
            index = (index + 1) % TABLE_SIZE;
            if (index == startIndex)
            {
                cout << "Hash table is full!\n";
                return;
            }
        }

        table[index] = key;
        occupied[index] = true;
    }

    bool search(int key)
    {
        int index = hash(key);
        int startIndex = index;

        while (occupied[index])
        {
            if (table[index] == key)
                return true;
            index = (index + 1) % TABLE_SIZE;
            if (index == startIndex)
                break;
        }
        return false;
    }

    void display()
    {
        cout << "Hash Table:\n";
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            if (occupied[i])
                cout << i << " => " << table[i] << endl;
            else
                cout << i << " => [empty]" << endl;
        }
    }
};

int main()
{
    HashTable ht;
    ht.insert(5);
    ht.insert(15);
    ht.insert(25);
    ht.insert(35);
    ht.insert(8);

    ht.display();

    cout << "\nSearching for 25: " << (ht.search(25) ? "Found" : "Not found") << endl;
    cout << "Searching for 9: " << (ht.search(9) ? "Found" : "Not found") << endl;

    return 0;
}

//ChainProbe
#include <iostream>
#include <string>
using namespace std;

const int TABLE_SIZE = 10;

struct Node
{
    string key;
    Node *next;
    Node(string k) : key(k), next(nullptr) {}
};

class HashTable
{
private:
    Node *table[TABLE_SIZE];

    int hash(string key)
    {
        int hashValue = 0;
        for (char c : key)
            hashValue = (hashValue * 31 + c) % TABLE_SIZE;
        return hashValue;
    }

public:
    HashTable()
    {
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i] = nullptr;
    }

    void insert(string key)
    {
        int index = hash(key);
        Node *newNode = new Node(key);

        newNode->next = table[index];
        table[index] = newNode;
    }

    bool search(string key)
    {
        int index = hash(key);
        Node *curr = table[index];
        while (curr)
        {
            if (curr->key == key)
                return true;
            curr = curr->next;
        }
        return false;
    }

    void display()
    {
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            cout << i << " -> ";
            Node *curr = table[i];
            while (curr)
            {
                cout << curr->key << " -> ";
                curr = curr->next;
            }
            cout << "NULL\n";
        }
    }
};

int main()
{
    HashTable ht;

    ht.insert("apple");
    ht.insert("banana");
    ht.insert("grape");
    ht.insert("orange");
    ht.insert("mango");
    ht.insert("lemon");

    ht.display();

    cout << "\nSearch 'banana': " << (ht.search("banana") ? "Found" : "Not Found") << endl;
    cout << "Search 'peach': " << (ht.search("peach") ? "Found" : "Not Found") << endl;

    return 0;
}

//isBST
#include <bits/stdc++.h>

using namespace std;

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

int isBST(NODE *root)
{
    if (root == NULL)
    {
        return 1;
    }
    if (root->left != NULL && root->left->data > root->data)
    {
        return 0;
    }
    if (root->right != NULL && root->right->data < root->data)
    {
        return 0;
    }
    return isBST(root->left) * isBST(root->right);
}

int main()
{

    struct NODE *root = new NODE;
    root->data = 10;
    root->left = new NODE;
    root->left->data = 20;
    root->right = new NODE;
    root->right->data = 15;

    if (isBST(root))
    {
        cout << "The tree is a BST" << endl;
    }
    else
    {
        cout << "The tree is not a BST" << endl;
    }

    return 0;
}

//AVL
#include <iostream>
using namespace std;

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
};

int height(Node* node) {
    return node ? node->height : 0;
}

int getBalance(Node* node) {
    return node ? height(node->left) - height(node->right) : 0;
}

Node* createNode(int key) {
    Node* node = new Node();
    node->key = key;
    node->left = node->right = nullptr;
    node->height = 1;
    return node;
}

int max(int a, int b) {
    return (a > b) ? a : b;
}

Node* rightRotate(Node* y) {
    Node* x = y->left;
    Node* 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;
}

Node* leftRotate(Node* x) {
    Node* y = x->right;
    Node* 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;
}

Node* insert(Node* node, int key) {
    if (!node)
        return createNode(key);

    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
    else
        return node; // Duplicates not allowed

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

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

void inorder(Node* root) {
    if (root != nullptr) {
        inorder(root->left);
        cout << root