#include <stdio.h>
#include <stdlib.h>

// Create a node
struct Node {
  int data;
  struct Node* next;
};

// Insert at the beginning
void insertAtBeginning(struct Node** head_ref, int new_data) {
  // Allocate memory to a node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Insert the data
  new_node->data = new_data;

  // Set the next pointer of the new node to the current head
  new_node->next = (*head_ref);

  // Move head to the new node
  (*head_ref) = new_node;
}

// Insert a node after a given node
void insertAfter(struct Node* prev_node, int new_data) {
  // Check if the previous node is NULL
  if (prev_node == NULL) {
    printf("The given previous node cannot be NULL");
    return;
  }

  // Allocate memory to a new node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Insert the data
  new_node->data = new_data;

  // Adjust the pointers to insert the new node
  new_node->next = prev_node->next;
  prev_node->next = new_node;
}

// Insert at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
  // Allocate memory to a new node
  struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

  // Assign the data to the new node
  new_node->data = new_data;

  // Set the next pointer of the new node to NULL
  new_node->next = NULL;

  // Check if the linked list is empty
  if (*head_ref == NULL) {
    // If the linked list is empty, make the new node the head
    *head_ref = new_node;
    return;
  }

  // Traverse to the last node
  struct Node* last = *head_ref;
  while (last->next != NULL)
    last = last->next;

  // Set the next pointer of the last node to the new node
  last->next = new_node;
}

// Delete a node
void deleteNode(struct Node** head_ref, int key) {
  // Store the head node
  struct Node* temp = *head_ref;
  struct Node* prev = NULL;

  // Check if the head node itself holds the key
  if (temp != NULL && temp->data == key) {
    // Change the head
    *head_ref = temp->next;

    // Free the old head
    free(temp);
    return;
  }

  // Search for the key to be deleted
  while (temp != NULL && temp->data != key) {
    prev = temp;
    temp = temp->next;
  }

  // If the key was not present in the linked list
  if (temp == NULL)
    return;

  // Unlink the node from the linked list
  prev->next = temp->next;

  // Free the memory allocated for the node
  free(temp);
}

// Search for a node
int searchNode(struct Node** head_ref, int key) {
  // Start from the head node
  struct Node* current = *head_ref;

  // Traverse the linked list
  while (current != NULL) {
    // If the key is found, return 1
    if (current->data == key)
      return 1;

    // Move to the next node
    current = current->next;
  }

  // Key not found
  return 0;
}

// Sort the linked list in ascending order
void sortLinkedList(struct Node** head_ref) {
  // Initialize current and index nodes
  struct Node* current = *head_ref;
  struct Node* index = NULL;

  // Temporary variable for swapping data
  int temp;

  // Check if the linked list is empty or has only one node
  if (head_ref == NULL)
    return;

  // Perform bubble sort on the linked list
  while (current != NULL) {
    // Set the index node to the node next to the current node
    index = current->next;

    while (index != NULL) {
      // Swap the data if the current node's data is greater than the index node's data
      if (current->data > index->data) {
        temp = current->data;
        current->data = index->data;
        index->data = temp;
      }

      // Move to the next index node
      index = index->next;
    }

    // Move to the next current node
    current = current->next;
  }
}

// Print the linked list
void printList(struct Node* node) {
  while (node != NULL) {
    printf(" %d ", node->data);
    node = node->next;
  }
}

// Driver program
int main() {
  // Initialize the head node
  struct Node* head = NULL;

  // Insert nodes into the linked list
  insertAtEnd(&head, 1);
  insertAtBeginning(&head, 2);
  insertAtBeginning(&head, 3);
  insertAtEnd(&head, 4);
  insertAfter(head->next, 5);

  printf("Linked list: ");
  printList(head);

  printf("\nAfter deleting an element: ");
  deleteNode(&head, 3);
  printList(head);

  int item_to_find = 3;
  if (searchNode(&head, item_to_find)) {
    printf("\n%d is found", item_to_find);
  } else {
    printf("\n%d is not found", item_to_find);
  }

  // Sort the linked list
  sortLinkedList(&head);
  printf("\nSorted List: ");
  printList(head);

  return 0;
}

// Circular Queue implementation in C

#include <stdio.h>


int items[5];
int front = -1, rear = -1;

// Check if the queue is full
int isFull() {
  if ((front == rear + 1) || (front == 0 && rear == 5 - 1)) 
return 1;
  return 0;
}

// Check if the queue is empty
int isEmpty() {
  if (front == -1) return 1;
  return 0;
}

// Adding an element
void enQueue(int element) {
  if (isFull())
    printf("\n Queue is full!! \n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % 5;
    items[rear] = element;
    printf("\n Inserted -> %d", element);
  }
}

// Removing an element
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\n Queue is empty !! \n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } 
    // Q has only one element, so we reset the 
    // queue after dequeing it. ?
    else {
      front = (front + 1) % 5;
    }
    printf("\n Deleted element -> %d \n", element);
    return (element);
  }
}

// Display the queue
void display() {
  int i;
  if (isEmpty())
    printf(" \n Empty Queue\n");
  else {
    printf("\n Front -> %d ", front);
    printf("\n Items -> ");
    for (i = front; i != rear; i = (i + 1) % 5) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("\n Rear -> %d \n", rear);
  }
}

int main() {
    //!showArray(items)

  deQueue();
  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);
  enQueue(6);
  display();
  deQueue();
  display();
  enQueue(7);
  display();
  enQueue(8);

  return 0;
}

#include <stdio.h>

int queue[4];
int front = -1;
int rear = -1;

void enqueue(int value) {
    if (rear == 4 - 1) {
        printf("Queue is full. Cannot enqueue.\n");
        return;
    }
    if (front == -1)
        front = 0;
    rear++;
    queue[rear] = value;
}

void dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is empty. Cannot dequeue.\n");
        return;
    }
    front++;
}

int getFront() {
    if (front == -1 || front > rear) {
        printf("Queue is empty. No front element.\n");
        return -1;
    }
    return queue[front];
}

int isEmpty() {
    if (front == -1 || front > rear)
        return 1;
    else
        return 0;
}

int getSize() {
    if (front == -1)
        return 0;
    else
        return rear - front + 1;
}

void display() {
    if (front == -1 || front > rear) {
        printf("Queue is empty. Nothing to display.\n");
        return;
    }
    printf("Queue elements: ");
    for (int i = front; i <= rear; i++)
        printf("%d ", queue[i]);
    printf("\n");
}

int main() {
    //!showArray(queue)
    enqueue(10);
    display();
    enqueue(20);
    display();
    enqueue(30);
    display();
    enqueue(40);
    display();
    enqueue(50);
    display(); 
    printf("Front element: %d\n", getFront()); 
    printf("Queue size: %d\n", getSize()); 
    printf("Is queue empty? %s\n", isEmpty() ? "Yes" : "No");
    dequeue();
    display(); 
    dequeue();
    display(); 
    dequeue();
    display();
    dequeue();
    display();
    dequeue();
    return 0;
} 

#include <stdio.h>

int stack[4];
int top = -1;

void push(int element) {
    if (top == 4 - 1) {
        printf("Stack Overflow\n");
    } else {
        stack[++top] = element;
        printf("Pushed is: %d \n", element);
    }
}

void pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
    } else {
        printf("Popped is: %d \n", stack[top--]);
    }
}

int peek() {
    if (top == -1) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return stack[top];
    }
}

int main() {
    //!showArray(stack)
    push(10);
    push(20);
    push(30);
    push(40);
    push(50);
    printf("Top Element is: %d\n", peek());
    pop();
    pop();
    pop();
    pop();
    pop();
    printf("Top Element is: %d\n", peek());
    return 0;
}

#include <stdio.h>

int ternarySearch(int l, int r, int key, int ar[])
{
	if (r >= l) {

		// Find the mid1 and mid2
		int mid1 = l + (r - l) / 3;
		int mid2 = r - (r - l) / 3;

		// Check if key is present at any mid
		if (ar[mid1] == key) {
			return mid1;
		}
		if (ar[mid2] == key) {
			return mid2;
		}

	

		if (key < ar[mid1]) {

			// The key lies in between l and mid1
			return ternarySearch(l, mid1 - 1, key, ar);
		}
		else if (key > ar[mid2]) { 

			// The key lies in between mid2 and r
			return ternarySearch(mid2 + 1, r, key, ar);
		}
		else {

			// The key lies in between mid1 and mid2
			return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
		}
	}

	// Key not found
	return -1;
}

// Driver code
int main()
{
    //!showArray(ar)
	int l, r, p, key;

	// Get the array
	// Sort the array if not sorted
	int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	// Starting index
	l = 0;

	// end element index
	r = 9;

	// Checking for 5

	// Key to be searched in the array
	key = 5;

	// Search the key using ternarySearch
	p = ternarySearch(l, r, key, ar);

	// Print the result
	printf("Index of %d is %d\n", key, p);

	// Checking for 50

	// Key to be searched in the array
	key = 50;

	// Search the key using ternarySearch
	p = ternarySearch(l, r, key, ar);

	// Print the result
	printf("Index of %d is %d", key, p);
}

#include <stdio.h>
int binarySearch(int [], int, int, int);

int main()
{
    //!showArray(array)
  int array[10], c, first, last, n, search,  index;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  printf("Enter value to find\n");
  scanf("%d", &search);

  first = 0;
  last = n - 1;

  index = binarySearch(array, first, last, search);
 
  if (index == -1)
    printf("Not found! %d isn't present in the list.\n", search);
  else
    printf("%d is present at location %d.\n", search, index + 1);
 
  return 0;
} 

int binarySearch(int a[], int s, int e, int f) {
  int m;
 
  if (s > e) // Not found
     return -1;

  m = (s + e)/2;

  if (a[m] == f)  // element found
    return m;
  else if (f > a[m])  
    return binarySearch(a, m+1, e, f);
  else
    return binarySearch(a, s, m-1, f);
}

#include <stdio.h>
 
int linear_search(int [], int, int);
 
int main()
{
    //!showArray(array)
int array[10], search, c, n, position;
 
   printf("Input number of elements in array\n");
   scanf("%d", &n);
 
   printf("Input %d numbers\n", n);
 
   for (c = 0; c < n; c++)
      scanf("%d", &array[c]);
 
   printf("Input a number to search\n");
   scanf("%d", &search);
 
   position = linear_search(array, n, search);
 
   if (position == -1)
      printf("%d isn't present in the array.\n", search);
   else
      printf("%d is present at location %d.\n", search, position+1);
 
   return 0;
}
 
int linear_search(int a[], int n, int find) {
int c;
 
   for (c = 0 ;c < n ; c++ ) {
      if (a[c] == find)
         return c;
   }
 
   return -1;
} 

#include <stdio.h>

void merge_sort(int i, int j, int a[], int aux[]) {
    if (j <= i) {
        return;
    }
    int mid = (i + j) / 2;

    merge_sort(i, mid, a, aux);
    merge_sort(mid + 1, j, a, aux);
    int pointer_left = i;
    int pointer_right = mid + 1;
    int k;

    for (k = i; k <= j; k++) {
        if (pointer_left == mid + 1) {
            aux[k] = a[pointer_right];
            pointer_right++;
        } else if (pointer_right == j + 1) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else if (a[pointer_left] < a[pointer_right]) {
            aux[k] = a[pointer_left];
            pointer_left++;
        } else {
            aux[k] = a[pointer_right];
            pointer_right++;
        }
    }

    for (k = i; k <= j; k++) {
        a[k] = aux[k];
    }
}

int main() {
    //!showSort(a)
    int a[5], aux[5], n, i;
    printf("Enter number of elements in the array:\n");
    scanf("%d", &n);
    printf("Enter %d integers\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    merge_sort(0, n - 1, a, aux);

    printf("Printing the sorted array:\n");
    for (i = 0; i < n; i++)
        printf("\t%d", a[i]);

    return 0;
}

#include <stdio.h>
 
void print_array(int size, int array[]) {
    for (int pos = 0; pos < size; pos += 1) {
        printf("%d%s", array[pos], pos + 1 == size ? "" : " ");
    }
    printf("\n");
}
 
void quick_sort (int size, int array[], int left, int right) {
    //! quicksort = showSort(array, cursors=[left, right, i, j], dim=size, thresholds=[pivot])
    if (right <= left)
        return;
    int pivot = array[right];
    int i = left;
    int j = right;
    while (1) {
        while (array[i] < pivot)
            i += 1;
        while (pivot < array[j])
            j -= 1;
        if (i >= j) {
            break;
        }
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i += 1;
        j -= 1;
    }
    quick_sort(size, array, left, i - 1);
    quick_sort(size, array, i, right);
}
 
int main() {
    //! quicksort = showSort(array, dim=n)
    int array[] = {4, 2, 1, 2, 3, 2, 1, 0, 1};
    int n = sizeof array / sizeof *array;
    quick_sort(n, array, 0, n - 1);
    print_array(n, array);
    return 0;
} 

#include <stdio.h>

int main()
{
//!showSort(array)
  int n, array[5], c, d, t, flag = 0;

  printf("Enter number of elements\n");
  scanf("%d", &n);

  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);

  for (c = 1 ; c <= n - 1; c++) {
    t = array[c];

    for (d = c - 1 ; d >= 0; d--) {
      if (array[d] > t) {
        array[d+1] = array[d];
        flag = 1;
      }
      else
        break;
    }
    if (flag)
      array[d+1] = t;
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
  }

  return 0;
}