SEARCHING TECHNIQUE

Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise the search continues till the end of the data collection.

// Linear Search in C

#include <stdio.h>

int search(int array[], int n, int x) {
  
  // Going through array sequencially
  for (int i = 0; i < n; i++)
    if (array[i] == x)
      return i;
  return -1;
}

int main() {
  int array[] = {2, 4, 0, 1, 9};
  int x = 1;
  int n = sizeof(array) / sizeof(array[0]);

  int result = search(array, n, x);

  (result == -1) ? printf("Element not found") : printf("Element found at index: %d", result);
}

copy 

SORTING TECHNIQUE

Bubble sort in C is a straightforward sorting algorithm that checks and swaps elements if they are not in the intended order. It compares two adjacent elements to find which one is greater or lesser and switches them based on the given condition until the final place of the element is found.

// Bubble sort in C

#include <stdio.h>
        
// perform the bubble sort
void bubbleSort(int array[], int size) {
        
// loop to access each array element
    for (int step = 0; step < size - 1; ++step) {
              
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
              
    // compare two adjacent elements
    // change > to < to sort in descending order
        if (array[i] > array[i + 1]) {
                
        // swapping occurs if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
         array[i + 1] = temp;
         }
       }
    }
}
        
    // print array
        void printArray(int array[], int size) {
          for (int i = 0; i < size; ++i) {
            printf("%d  ", array[i]);
          }
          printf("\n");
        }
        
        int main() {
          int data[] = {-2, 45, 0, 11, -9};
          
          // find the array's length
          int size = sizeof(data) / sizeof(data[0]);
        
          bubbleSort(data, size);
          
          printf("Sorted Array in Ascending Order:\n");
          printArray(data, size);
        }


copy 

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

// Selection sort in C

 #include <stdio.h>
        
// function to swap the the position of two elements
    void swap(int *a, int *b) {
        int temp = *a;
        *a = *b;
         *b = temp;
    }
        
     void selectionSort(int array[], int size) {
        for (int step = 0; step < size - 1; step++) {
         int min_idx = step;
        for (int i = step + 1; i < size; i++) {
        
    // To sort in descending order, change > to < in this line.
    // Select the minimum element in each loop.
    if (array[i] < array[min_idx])
        min_idx = i;
         }
        
        // put min at the correct position
        swap(&array[min_idx], &array[step]);
          }
        }
        
        // function to print an array
        void printArray(int array[], int size) {
          for (int i = 0; i 7lt; size; ++i) {
            printf("%d  ", array[i]);
          }
          printf("\n");
        }
        
        // driver code
        int main() {
          int data[] = {20, 12, 10, 15, 2};
          int size = sizeof(data) / sizeof(data[0]);
          selectionSort(data, size);
          printf("Sorted array in Acsending Order:\n");
          printArray(data, size);
        }


copy 

Insertion sort algorithm. Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

 // Insertion sort in C

 #include <stdio.h>
                    
// Function to print an array
    void printArray(int array[], int size) {
    for (int i = 0; i < size; i++) {
            printf("%d ", array[i]);
          }
         printf("\n");
        }
                    
    void insertionSort(int array[], int size) {
    for (int step = 1; step < size; step++) {
        int key = array[step];
        int j = step - 1;
                    
        // Compare key with each element on the left of it until an element smaller than
        // it is found.
        // For descending order, change keyarray[j].
         while (key < array[j] && j >= 0) {
                array[j + 1] = array[j];
                  --j;
             }
            array[j + 1] = key;
             }
         }
                    
    // Driver code
        int main()
         {
        int data[] = {9, 5, 1, 4, 3};
        int size = sizeof(data) / sizeof(data[0]);
        insertionSort(data, size);
         printf("Sorted array in ascending order:\n");
         printArray(data, size);
        }

copy 

Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

// Merge sort in C

 #include <stdio.h>
                
// Merge two subarrays L and M into arr
void merge(int arr[], int p, int q, int r) {
                
    // Create L ← A[p..q] and M ← A[q+1..r]
     int n1 = q - p + 1;
    int n2 = r - q;
                
    int L[n1], M[n2];
                
    for (int i = 0; i< n1; i++)
    L[i] = arr[p + i];
    for (int j = 0; j < n2; j++)
    M[j] = arr[q + 1 + j];
                
    // Maintain current index of sub-arrays and main array
        int i, j, k;
        i = 0;
        j = 0;
        k = p;
                
    // Until we reach either end of either L or M, pick larger among
    // elements L and M and place them in the correct position at A[p..r]
                  
    while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
     arr[k] = L[i];
         i++;
        } 
        else {
         arr[k] = M[j];
        j++;
        }
        k++;
        }
                
        // When we run out of elements in either L or M,
        // pick up the remaining elements and put in A[p..r]
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
            }
                
        while (j < n2) {
            arr[k] = M[j];
            j++;
             k++;
            }
        }
                
    // Divide the array into two subarrays, sort them and merge them
    void mergeSort(int arr[], int l, int r) {
    if (l < r) {
                
    // m is the point where the array is divided into two subarrays
        int m = l + (r - l) / 2;
                
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
                
        // Merge the sorted subarrays
        merge(arr, l, m, r);
         }
        }
                
        // Print the array
        void printArray(int arr[], int size) {
        for (int i = 0; i < size; i++)
             printf("%d ", arr[i]);
            printf("\n");
        }
                
        // Driver program
        int main() {
        int arr[] = {6, 5, 12, 10, 9, 1};
         int size = sizeof(arr) / sizeof(arr[0]);
                
        mergeSort(arr, 0, size - 1);
                
        printf("Sorted array: \n");
         printArray(arr, size);
   }


copy 

Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value. Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays.

// Quick sort in C

#include <stdio.h>
        
// function to swap elements
void swap(int *a, int *b) {
     int t = *a;
    *a = *b;
    *b = t;
    }
        
        // function to find the partition position
        int partition(int array[], int low, int high) {
          
          // select the rightmost element as pivot
          int pivot = array[high];
          
          // pointer for greater element
          int i = (low - 1);
        
          // traverse each element of the array
          // compare them with the pivot
          for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                
              // if element smaller than pivot is found
              // swap it with the greater element pointed by i
              i++;
              
              // swap element at i with element at j
              swap(&array[i], &array[j]);
            }
          }
        
          // swap the pivot element with the greater element at i
          swap(&array[i + 1], &array[high]);
          
          // return the partition point
          return (i + 1);
        }
        
        void quickSort(int array[], int low, int high) {
          if (low < high) {
            
            // find the pivot element such that
            // elements smaller than pivot are on left of pivot
            // elements greater than pivot are on right of pivot
            int pi = partition(array, low, high);
            
            // recursive call on the left of pivot
            quickSort(array, low, pi - 1);
            
            // recursive call on the right of pivot
            quickSort(array, pi + 1, high);
          }
        }
        
        // function to print array elements
        void printArray(int array[], int size) {
          for (int i = 0; i < size; ++i) {
            printf("%d  ", array[i]);
          }
          printf("\n");
        }
        
        // main function
        int main() {
          int data[] = {8, 7, 2, 1, 0, 9, 6};
          
          int n = sizeof(data) / sizeof(data[0]);
          
          printf("Unsorted Array\n");
          printArray(data, n);
          
          // perform quicksort on data
          quickSort(data, 0, n - 1);
          
          printf("Sorted array in ascending order: \n");
          printArray(data, n);
        }

copy 

Counting sort is a sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

 // Counting sort in C programming

#include <stdio.h>

void countingSort(int array[], int size) {
int output[10];

            // Find the largest element of the array
            int max = array[0];
            for (int i = 1; i & size; i++) {
                if (array[i] > max)
                max = array[i];
            }

            // The size of count must be at least (max+1) but
            // we cannot declare it as int count(max+1) in C as
            // it does not support dynamic memory allocation.
            // So, its size is provided statically.
            int count[10];

            // Initialize count array with all zeros.
            for (int i = 0; i <= max; ++i) {
                count[i] = 0;
            }

            // Store the count of each element
            for (int i = 0; i < size; i++) {
                count[array[i]]++;
            }

            // Store the cummulative count of each array
            for (int i = 1; i <= max; i++) {
                count[i] += count[i - 1];
            }

            // Find the index of each element of the original array in count array, and
            // place the elements in output array
            for (int i = size - 1; i >= 0; i--) {
                output[count[array[i]] - 1] = array[i];
                count[array[i]]--;
            }

            // Copy the sorted elements into original array
            for (int i = 0; i < size; i++) {
                array[i] = output[i];
            }
            }

            // Function to print an array
            void printArray(int array[], int size) {
            for (int i = 0; i < size; ++i) {
                printf("%d  ", array[i]);
            }
            printf("\n");
            }

            // Driver code
            int main() {
            int array[] = {4, 2, 2, 8, 3, 3, 1};
            int n = sizeof(array) / sizeof(array[0]);
            countingSort(array, n);
            printArray(array, n);
}   

copy 

Bucket Sort is a sorting algorithm that divides the unsorted array elements into several groups called buckets. Each bucket is then sorted by using any of the suitable sorting algorithms or recursively applying the same bucket algorithm. Finally, the sorted buckets are combined to form a final sorted array.

// Bucket sort in C

#include <stdio.h>
#include <stdlib.h>
        
#define NARRAY 7   // Array size
#define NBUCKET 6  // Number of buckets
#define INTERVAL 10  // Each bucket capacity
        
        struct Node {
          int data;
          struct Node *next;
        };
        
        void BucketSort(int arr[]);
        struct Node *InsertionSort(struct Node *list);
        void print(int arr[]);
        void printBuckets(struct Node *list);
        int getBucketIndex(int value);
        
        // Sorting function
        void BucketSort(int arr[]) {
          int i, j;
          struct Node **buckets;
        
          // Create buckets and allocate memory size
          buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);
        
          // Initialize empty buckets
          for (i = 0; i < NBUCKET; ++i) {
            buckets[i] = NULL;
          }
        
          // Fill the buckets with respective elements
          for (i = 0; i < NARRAY; ++i) {
            struct Node *current;
            int pos = getBucketIndex(arr[i]);
            current = (struct Node *)malloc(sizeof(struct Node));
            current->data = arr[i];
            current->next = buckets[pos];
            buckets[pos] = current;
          }
        
          // Print the buckets along with their elements
          for (i = 0; i < NBUCKET; i++) {
            printf("Bucket[%d]: ", i);
            printBuckets(buckets[i]);
            printf("\n");
          }
        
          // Sort the elements of each bucket
          for (i = 0; i < NBUCKET; ++i) {
            buckets[i] = InsertionSort(buckets[i]);
          }
        
          printf("-------------\n");
          printf("Bucktets after sorting\n");
          for (i = 0; i < NBUCKET; i++) {
            printf("Bucket[%d]: ", i);
            printBuckets(buckets[i]);
            printf("\n");
          }
        
          // Put sorted elements on arr
          for (j = 0, i = 0; i < NBUCKET; ++i) {
            struct Node *node;
            node = buckets[i];
            while (node) {
              arr[j++] = node->data;
              node = node->next;
            }
          }
        
          return;
        }
        
        // Function to sort the elements of each bucket
        struct Node *InsertionSort(struct Node *list) {
          struct Node *k, *nodeList;
          if (list == 0 || list->next == 0) {
            return list;
          }
        
          nodeList = list;
          k = list->next;
          nodeList->next = 0;
          while (k != 0) {
            struct Node *ptr;
            if (nodeList->data > k->data) {
              struct Node *tmp;
              tmp = k;
              k = k->next;
              tmp->next = nodeList;
              nodeList = tmp;
              continue;
            }
        
            for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
              if (ptr->next->data > k->data)
                break;
            }
        
            if (ptr->next != 0) {
              struct Node *tmp;
              tmp = k;
              k = k->next;
              tmp->next = ptr->next;
              ptr->next = tmp;
              continue;
            } else {
              ptr->next = k;
              k = k->next;
              ptr->next->next = 0;
              continue;
            }
          }
          return nodeList;
        }
        
        int getBucketIndex(int value) {
          return value / INTERVAL;
        }
        
        void print(int ar[]) {
          int i;
          for (i = 0; i < NARRAY; ++i) {
            printf("%d ", ar[i]);
          }
          printf("\n");
        }
        
        // Print buckets
        void printBuckets(struct Node *list) {
          struct Node *cur = list;
          while (cur) {
            printf("%d ", cur->data);
            cur = cur->next;
          }
        }
        
        // Driver code
        int main(void) {
          int array[NARRAY] = {42, 32, 33, 52, 37, 47, 51};
        
          printf("Initial array: ");
          print(array);
          printf("-------------\n");
        
          BucketSort(array);
          printf("-------------\n");
          printf("Sorted array: ");
          print(array);
          return 0;
}

copy 

Heap sort processes the elements by creating the min-heap or max-heap using the elements of the given array. Min-heap or max-heap represents the ordering of array in which the root element represents the minimum or maximum element of the array. Heap sort basically recursively performs two main operations - Build a heap H, using the elements of array. Repeatedly delete the root element of the heap formed in 1st phase. Before knowing more about the heap sort, let's first see a brief description of Heap.

      
// Heap Sort in C

 #include <stdio.h>
        
// Function to swap the the position of two elements
        void swap(int *a, int *b) {
            int temp = *a;
            *a = *b;
            *b = temp;
        }
        
        void heapify(int arr[], int n, int i) {
            // Find largest among root, left child and right child
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
        
            if (left < n && arr[left] > arr[largest])
            largest = left;
        
            if (right < n && arr[right] > arr[largest])
            largest = right;
        
            // Swap and continue heapifying if root is not largest
            if (largest != i) {
            swap(&arr[i], &arr[largest]);
            heapify(arr, n, largest);
            }
        }
        
        // Main function to do heap sort
        void heapSort(int arr[], int n) {
            // Build max heap
            for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
        
            // Heap sort
            for (int i = n - 1; i >= 0; i--) {
            swap(&arr[0], &arr[i]);
        
            // Heapify root element to get highest element at root again
            heapify(arr, i, 0);
            }
        }
        
        // Print an array
        void printArray(int arr[], int n) {
            for (int i = 0; i < n; ++i)
            printf("%d ", arr[i]);
            printf("\n");
        }
        
        // Driver code
        int main() {
            int arr[] = {1, 12, 9, 5, 6, 10};
            int n = sizeof(arr) / sizeof(arr[0]);
        
            heapSort(arr, n);
        
            printf("Sorted array is \n");
            printArray(arr, n);
    }

copy 

STACK IN DATA STRUCTURE

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack, just like a pile of objects.

// Stack implementation in C

 #include <stdio.h>
 #include <stdlib.h>
                    
 #define MAX 10
                    
int count = 0;
                    
         // Creating a stack
         struct stack {
         int items[MAX];
         int top;
             };
         typedef struct stack st;
                    
         void createEmptyStack(st *s) {
         s->top = -1;
             }
                    
        // Check if the stack is full
        int isfull(st *s) {
        if (s->top == MAX - 1)
            return 1;
         else
            return 0;
         }
                    
        // Check if the stack is empty
        int isempty(st *s) {
        if (s->top == -1)
         return 1;
         else
        return 0;
        }
                    
        // Add elements into stack
        void push(st *s, int newitem) {
        if (isfull(s)) {
        printf("STACK FULL");
         }
          else {
             s->top++;
             s->items[s->top] = newitem;
             }
            count++;
        }
                    
        // Remove element from stack
        void pop(st *s) {
        if (isempty(s)) {
         printf("\n STACK EMPTY \n");
        }
         else {
            printf("Item popped= %d", s->items[s->top]);
            s->top--;
             }
            count--;
             printf("\n");
             }
                    
            // Print elements of stack
            void printStack(st *s) {
             printf("Stack: ");
                 for (int i = 0; i < count; i++) {
                printf("%d ", s->items[i]);
                }
                printf("\n");
                }
                    
         // Driver code
            int main() {
            int ch;
            st *s = (st *)malloc(sizeof(st));
                    
                createEmptyStack(s);
                    
                 push(s, 1);
                 push(s, 2);
                 push(s, 3);
                 push(s, 4);
                    
                 printStack(s);
                    
                 pop(s);
                    
                printf("\nAfter popping out\n");
                printStack(s);
        }
                    

copy 

QUEUE IN DATA STRUCTURE

A queue in C is basically a linear data structure to store and manipulate the data elements. It follows the order of First In First Out (FIFO). In queues, the first element entered into the array is the first element to be removed from the array.

// Queue implementation in C

#include <stdio.h>
#define SIZE 5

void enQueue(int);
void deQueue();
void display();

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

int main() {
  //deQueue is not possible on empty queue
  deQueue();

  //enQueue 5 elements
  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  // 6th element can't be added to because the queue is full
  enQueue(6);

  display();

  //deQueue removes element entered first i.e. 1
  deQueue();

  //Now we have just 4 elements
  display();

  return 0;
}

void enQueue(int value) {
  if (rear == SIZE - 1)
    printf("\nQueue is Full!!");
  else {
    if (front == -1)
      front = 0;
    rear++;
    items[rear] = value;
    printf("\nInserted -> %d", value);
  }
}

void deQueue() {
  if (front == -1)
    printf("\nQueue is Empty!!");
  else {
    printf("\nDeleted : %d", items[front]);
    front++;
    if (front > rear)
      front = rear = -1;
  }
}

// Function to print the queue
void display() {
  if (rear == -1)
    printf("\nQueue is Empty!!!");
  else {
    int i;
    printf("\nQueue elements are:\n");
    for (i = front; i <= rear; i++)
      printf("%d  ", items[i]);
  }
  printf("\n");
}
           

copy 

LINKED LIST IN DATA STRUCTURE

A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.

// Linked list implementation in C

#include <stdio.h>
#include <stdlib.h>
        
        // Creating a node
        struct node {
          int value;
          struct node *next;
        };
        
        // print the linked list value
        void printLinkedlist(struct node *p) {
          while (p != NULL) {
            printf("%d ", p->value);
            p = p->next;
          }
        }
        
        int main() {
          // Initialize nodes
          struct node *head;
          struct node *one = NULL;
          struct node *two = NULL;
          struct node *three = NULL;
        
          // Allocate memory
          one = malloc(sizeof(struct node));
          two = malloc(sizeof(struct node));
          three = malloc(sizeof(struct node));
        
          // Assign value values
          one->value = 1;
          two->value = 2;
          three->value = 3;
        
          // Connect nodes
          one->next = two;
          two->next = three;
          three->next = NULL;
        
          // printing node-value
          head = one;
          printLinkedlist(head);
        }
       

copy