Data Structure-Online Job 04

void shellSort(int arr[], int n) {
    // Start with a big gap, then reduce the gap
    for (int gap = n/2; gap > 0; gap /= 2) {
        // Do a gapped insertion sort for this gap size.
        // The first gap elements a[0..gap-1] are already in gapped order
        // keep adding one more element until the entire array is gap sorted
        for (int i = gap; i < n; i += 1) {
            // add a[i] to the elements that have been gap sorted
            // save a[i] in temp and make a hole at position i
            int temp = arr[i];

            // shift earlier gap-sorted elements up until the correct location for a[i] is found
            int j;           
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
           
            // put temp (the original a[i]) in its correct location
            arr[j] = temp;
        }
    }
}

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high) {
    int pivot = arr[high]; 
    int i = (low - 1); 

    for (int j = low; j <= high - 1; 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 pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;

        // If the element is present at the middle itself
        if (arr[mid] == x)
            return mid;

        // If element is smaller than mid, then it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);

        // Else the element can only be present in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }

    // We reach here when the element is not present in array
    return -1;
}

class Node {
public:
    int key;
    Node* left;
    Node* right;
};

// Function to create a new node
Node* newNode(int item) {
    Node* temp = new Node();
    temp->key = item;
    temp->left = temp->right = nullptr;
    return temp;
}

// Function to insert a new node with given key in BST
Node* insert(Node* node, int key) {
    // If the tree is empty, assign a new node address
    if (node == nullptr) return newNode(key);

    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    // return the (unchanged) node pointer
    return node;
}

class AVLNode {
public:
    int key;
    AVLNode* left;
    AVLNode* right;
    int height;
};

// Function to create a new node
AVLNode* newAVLNode(int item) {
    AVLNode* temp = new AVLNode();
    temp->key = item;
    temp->left = temp->right = nullptr;
    temp->height = 1;  // new node is initially added at leaf
    return temp;
}

// Function to get the height of the tree
int height(AVLNode* N) {
    if (N == nullptr)
        return 0;
    return N->height;
}

// Function to get maximum of two integers
int max(int a, int b) {
    return (a > b) ? a : b;
}

// Function to right rotate subtree rooted with y
AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    // Perform rotation
    x->right = y;
    y->left = T2;

    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    // Return new root
    return x;
}

// Function to left rotate subtree rooted with x
AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    // Perform rotation
    y->left = x;
    x->right = T2;

    // Update heights
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    // Return new root
    return y;
}

// Function to get Balance factor of node N
int getBalance(AVLNode* N) {
    if (N == nullptr)
        return 0;
    return height(N->left) - height(N->right);
}

// Function to insert a node
AVLNode* insertAVL(AVLNode* node, int key) {
    // Perform the normal BST insertion
    if (node == nullptr)
        return (newAVLNode(key));

    if (key < node->key)
        node->left = insertAVL(node->left, key);
    else if (key > node->key)
        node->right = insertAVL(node->right, key);
    else  // Equal keys are not allowed in BST
        return node;

    // Update height of this ancestor node
    node->height = 1 + max(height(node->left), height(node->right));

    // Get the balance factor
    int balance = getBalance(node);

    // If this node becomes unbalanced, then there are 4 cases

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

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

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

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

    // return the (unchanged) node pointer
    return node;
}

#include <iostream>
#include <unordered_map>

int main() {
    // Create a hash table
    std::unordered_map<std::string, int> hashTable;

    // Insert elements
    hashTable["apple"] = 1;
    hashTable["banana"] = 2;
    hashTable["cherry"] = 3;

    // Access elements
    std::cout << "apple: " << hashTable["apple"] << std::endl;
    std::cout << "banana: " << hashTable["banana"] << std::endl;
    std::cout << "cherry: " << hashTable["cherry"] << std::endl;

    // Check if an element exists
    if (hashTable.find("apple") != hashTable.end()) {
        std::cout << "apple exists in the hash table" << std::endl;
    } else {
        std::cout << "apple does not exist in the hash table" << std::endl;
    }

    // Erase an element
    hashTable.erase("apple");

    // Check if an element exists
    if (hashTable.find("apple") != hashTable.end()) {
        std::cout << "apple exists in the hash table" << std::endl;
    } else {
        std::cout << "apple does not exist in the hash table" << std::endl;
    }

    return 0;
}