Unit-V Sorting, Searching and Hashing

Sorting

• Sorting is arranging array elements in ascending or descending order.

• For array A = {A1, A2, A3, A4, ?? An }, ascending order means A1 > A2 > A3 > A4 > A5 > ? > An.

Types of Sorting

• Internal Sorting

• External Sorting

Internal Sorting

• Occurs in the computer's main memory.

• Applied to small data collections.

• Takes smaller inputs for arranging data.

• Data collection must be small enough to fit in main memory.

External Sorting

• Done with additional external memory like magnetic tape or hard disk.

• Applied when the number of data elements to be sorted is very large.

• Can take larger inputs.

• Uses a hierarchical merging strategy and requires auxiliary storage.

Examples of Internal Sorting

• Bubble sort

• Selection sort

• Insertion sort

• Quick sort

• Bucket sort

• Heap sort

• Radix sort

Examples of External Sorting

• Merge sort

• Two-way merge sort

• External Radix Sort

Internal Sorting Details

• Takes place inside the main memory of the computer.

• Data to be sorted must be small enough to be managed by the main memory.

• Reading and writing data from slower media significantly slows down the sorting process.

• Many different sorting methods exist to avoid this condition.

Bubble Sort

• A simple, intuitive sorting algorithm.

• Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• Limited practical applications due to inefficiency on large datasets.

Working of Bubble Sort Algorithm

• The algorithm starts from the initial two elements.

• Elements are compared to check which is greater.

• Swapping is done if elements are in the wrong order.

• The process continues until the array is completely sorted.

Bubble Sort Example

• Given an array, the algorithm iterates through it, comparing adjacent elements.

• If elements are out of order, they are swapped.

• After each pass, the largest unsorted element bubbles up to its correct position.

• Multiple passes are required to sort the entire array.

Bubble Sort Code Snippet

#include<stdio.h>
void print(int a[], int n) {
    int i;
    for(i = 0; i < n; i++) {
        printf("%d ",a[i]);
    }
}

void bubble (int a[], int n) {
    int i, j, temp;
    for(i = 0; i < n; i++) {
        for(j = i+1; j < n; j++) {
            if(a[j] < a[i]) {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}

void main() {
    int i, j,temp;
    int a[5] = {10, 35, 32, 13, 26};
    int n = sizeof(a)/sizeof(a[0]);
    printf("Before sorting array elements are - \n");
    print(a, n);
    bubble(a, n);
    printf("\nAfter sorting array elements are - \n");
    print(a, n);
}

Insertion Sort

• Builds the final sorted array one item at a time.

• Less efficient on large lists compared to more advanced algorithms like quick sort and merge sort.

Working of Insertion Sort Algorithm

• Initially, the first two elements are compared.

• Each element is inserted into its correct position within the sorted portion of the array.

Insertion Sort Code Snippet

#include <stdio.h>
void insert(int a[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {
        temp = a[i];
        j = i - 1;
        while(j>=0 && temp <= a[j]) {
            a[j+1] = a[j];
            j = j-1;
        }
        a[j+1] = temp;
    }
}

void printArr(int a[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
}

int main() {
    int a[] = { 12, 31, 25, 8, 32, 17 };
    int n = sizeof(a) / sizeof(a[0]);
    printf("Before sorting array elements are: \n");
    printArr(a, n);
    insert(a, n);
    printf("\nAfter sorting array elements are: \n");
    printArr(a, n);
    return 0;
}

Quick Sort

• A commonly used sorting algorithm preferred for its efficiency and effectiveness.

• Splits an array into two parts: elements smaller than a pivot and elements bigger than the pivot.

• Applies this procedure recursively to each partition until the complete array is sorted.

Working of Quick Sort Algorithm

• Pivot Selection: Choose an element as the pivot.

• Partitioning: Rearrange the array so that all elements less than the pivot are before it, and all elements greater than the pivot are after it.

• Recursion: Recursively apply the above steps to the two sub-arrays.

Example Steps

1. Choose a pivot element.

2. Move elements smaller than the pivot to the left and elements larger than the pivot to the right.

3. Recursively apply the quick sort algorithm to the sub-arrays.

Quick Sort Code Snippet

#include <stdio.h>

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

void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = { 12, 17, 6, 25, 1, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

External Sorting Details

• A class of sorting algorithms that can handle massive amounts of data.

• Required when the data being sorted does not fit into the main memory (RAM).

• Data must reside in slower external memory (usually a hard drive).

Merge Sort

• Similar to the quick sort algorithm as it uses the divide and conquer approach.

• Divides the given list into two equal halves, calls itself for the two halves, and then merges the two sorted halves.

• The merge() function performs the merging.

Merge Sort Steps

1. Divide the list into two equal halves.

2. Recursively sort each half.

3. Merge the two sorted halves.

Merge Sort Code Snippet

#include <stdio.h>

void merge (int a[], int beg, int mid, int end) {
    int i, j, k;
    int n1 = mid - beg + 1;
    int n2 = end - mid;

    int LeftArray[n1], RightArray[n2];

    for (int i = 0; i < n1; i++)
        LeftArray[i] = a[beg + i];
    for (int j = 0; j < n2; j++)
        RightArray[j] = a[mid + 1+j];

    i = 0;  /* initial index of first sub-array */
    j = 0;  /* initial index of second sub-array */
    k = beg;  /* initial index of merged sub-array */

    while (i < n1 && j < n2) {
        if(LeftArray[i] <= RightArray[j]) {
            a[k] = LeftArray[i];
            i++;
        } else {
            a[k] = RightArray[j];
            j++;
        }
        k++;
    }

    while (i<n1) {
        a[k] = LeftArray[i];
        i++;
        k++;
    }

    while (j<n2) {
        a[k] = RightArray[j];
        j++;
        k++;
    }
}

void mergeSort(int a[], int beg, int end) {
    if (beg < end) {
        int mid = (beg + end) / 2;
        mergeSort(a, beg, mid);
        mergeSort(a, mid + 1, end);
        merge(a, beg, mid, end);
    }
}

void printArray(int a[], int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
}

int main() {
    int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
    int n = sizeof(a) / sizeof(a[0]);
    printf("Before sorting array elements are - \n");
    printArray(a, n);

    mergeSort(a, 0, n - 1);

    printf("After sorting array elements are - \n");
    printArray(a, n);
    return 0;
}

Searching

• Searching in data structure refers to finding the required information from a collection of items stored as elements in the computer memory.

• These sets of items are in different forms, such as an array, linked list, graph, or tree.

Types of Searching

• Linear Search

• Binary Search

Linear Search

• Also called the sequential search algorithm.

• The simplest searching algorithm.

• We simply traverse the list completely and match each element of the list with the item whose location is to be found.

• If the match is found, then the location of the item is returned; otherwise, the algorithm returns NULL.

Working of Linear Search

• The value of K is compared with each element of the array.

• If a match is found, the index of the element is returned.

• If no match is found, the algorithm returns NULL.

Linear Search Code Snippet

#include <stdio.h>

int linearSearch (int a[], int n, int val) {
    for (int i = 0; i < n; i++) {
        if (a[i] == val)
            return i+1;
    }
    return -1;
}

int main() {
    int a[] = {70, 40, 30, 11, 57, 41, 25, 14, 52};
    int val = 41;
    int n = sizeof(a) / sizeof(a[0]);

    int res = linearSearch (a, n, val);
    printf("The elements of the array are - ");
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\nElement to be searched is - %d", val);
    if (res == -1)
        printf("\nElement is not present in the array");
    else
        printf("\nElement is present at %d position of array", res);

    return 0;
}

Binary Search

• Follows the divide and conquer approach in which the list is divided into two halves.

• The item is compared with the middle element of the list.

• If the match is found then the location of the middle element is returned.

• Otherwise, we search into either of the halves depending upon the result produced through the match.

Note

• Binary search can be implemented on sorted array elements.

• If the list elements are not arranged in a sorted manner, we have first to sort them.

Working of Binary Search

• The mid of the array is calculated using the formula: $mid = (beg + end)/2$

• If A[mid] < K, then beg = mid + 1.

• If A[mid] = K, then the location = mid.

Binary Search Code Snippet

#include <stdio.h>

int binarySearch (int arr[], int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right -left) / 2;

        if (arr[mid] == key) {
            return mid;
        }

        if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int size = sizeof(arr) / sizeof(arr[0]);
    int key = 23;
    int result = binarySearch (arr, 0, size - 1, key);

    if (result == -1) {
        printf("Element is not present in array");
    } else {
        printf("Element is present at index %d", result);
    }
    return 0;
}

Hashing

• Hashing is a technique or process of mapping keys and values into the hash table by using a hash function.

• It is done for faster access to elements.

• The efficiency of mapping depends on the efficiency of the hash function used.

Examples of Hashing

• In universities, each student is assigned a unique roll number that can be used to retrieve information about them.

• Hash function $H(x)$ maps the value $x$ at the index $x \% 10$ in an Array.

• For example if the list of values is [11,12,13,14,15] it will be stored at positions {1,2,3,4,5} in the array or Hash table respectively.

Terminology

• Hash table: A data structure where the data is stored based upon its hashed key which is obtained using a hashing function.

• Hash function: A function outputs a value mapped to a fixed range for a given data.

• Perfect Hash function: A hash function that maps each item into a unique slot (no collisions).

Collision Resolution Techniques

• In Hashing, hash functions were used to generate hash values.

• The hash value is used to create an index for the keys in the hash table.

• The hash function may return the same hash value for two or more keys.

• When two or more keys have the same hash value, a collision happens.

Types of Collision Resolution Techniques

• Open Hashing (Separate chaining)

• Open Addressing (Closed Hashing)

  • Linear Probing

  • Quadratic Probing

  • Double Hashing

1. Open Hashing (Separate chaining)

• Collisions are resolved using a list of elements to store objects with the same key together.

• If we were to map the given data with the given hash function we'll get the corresponding values

2. Closed Hashing (Open Addressing)

• This collision resolution technique requires a hash table with fixed and known size.

• During insertion, if a collision is encountered, alternative cells are tried until an empty bucket is found.

• These techniques require the size of the hash table to be supposedly larger than the number of objects to be stored (something with a load factor < 1 is ideal).

a. Linear Probing

• In linear probing, the hash table is searched sequentially, starting from the original location of the hash.

• If in case the location that we get is already occupied, then we check for the next location.

Example

• Consider a simple hash function as “key mod 5” and a sequence of keys that are to be inserted are 50, 70, 76, 85, 93.

2.b) Quadratic Probing

• Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in hash tables.

• Quadratic probing operates by taking the original hash index and adding successive values of an arbitrary quadratic polynomial until an open slot is found.

• $H + 1^2, H + 2^2, H + 3^2, H + 4^2, …, H + k^2$

Example

• Let us consider table Size = 7, hash function as $Hash(x) = x \% 7$ and collision resolution strategy to be $f(i) = i^2$.

• Insert = 22, 30, and 50

2.c) Double Hashing

• Double hashing is a collision resolving technique in Open Addressed Hash tables.

• Double hashing makes use of two hash functions.

• The first hash function is h1(k) which takes the key and gives out a location on the hash table.

• If the new location is not occupied or empty then we can easily place our key.

• In case the location is occupied (collision) we will use secondary hash- function h2(k) in combination with the first hash-function h1(k) to find the new location on the hash table.

• This combination of hash functions is of the form:

• $h(k, i) = (h1(k) + i * h2(k)) \% n$

  • Where:

    • $i$ is a non-negative integer that indicates a collision number,

    • $k = element/key$ which is being hashed

    • $n = hash table size$

Example

• Insert the keys 27, 43, 692, 72 into the Hash Table of size 7.

• where first hash function is $h1(k) = k mod 7$ and second hash-function is $h2(k) = 1 + (k mod 5)$

Hashing Code Snippet

#include<stdio.h>
#define size 7
int arr[size];

void initialize() {
    int i;
    for(i = 0; i < size; i++) {
        arr[i] = -1;
    }
}

void print() {
    int i;
    for(i = 0; i < size; i++) {
        printf("arr[%d] = %d\n", i, arr[i]);
    }
}

void insert(int value) {
    int key = value % size;
    if(arr[key] == -1) {
        arr[key] = value;
        printf("%d inserted at arr[%d]\n", value, key);
    } else {
        printf("Collision: arr[%d] has element %d already!\n", key, arr[key]);
        printf("Unable to insert %d\n", value);
    }
}

void del(int value) {
    int key = value % size;
    if(arr[key] == value) {
        arr[key] = -1;
    } else {
        printf("%d not present in the hash table\n", value);
    }
}

void search(int value) {
    int key = value % size;
   if(arr[key] == value) {
    printf("%d is present in the Hash table");
   }
   else{
    printf("%d is not present in the Hash table\n",value);
   }

}

void main() {
    initialize();
    insert(10); //key = 10 % 7 ==> 3
    insert(4); //key = 4 % 7 ==> 4
    insert(3); //key = 3 % 7 ==> 3 (collision)
    printf("Hash table\n");
    print();
    printf("\n");
    printf("Deleting value 10..\n");
    del(10);

    printf("After the deletion hash table\n");
    print();
    printf("\n");
    printf("Deleting value 5..\n");
    del(5);

    printf("After the deletion hash table\n");
    print();
    printf("\n");
    printf("Searching value 4..\n");
    search(4);
    printf("Searching value 10..\n");
    search(10);
}

Sorting

• Sorting arranges array elements in order.

• Ascending order example: A = {A1, A2, A3, … An }, where A1 > A2 > A3 > … > An.

Types of Sorting

• Internal Sorting: Occurs in main memory, for small data.

• External Sorting: Uses external memory, for large data.

Internal Sorting

• In main memory.

• Small data collections.

• Data fits in main memory.

External Sorting

• Uses external memory.

• Large data elements.

• Hierarchical merging strategy.

Internal Sorting Examples

• Bubble, Selection, Insertion, Quick, Bucket, Heap, Radix sorts.

External Sorting Examples

• Merge, Two-way merge, External Radix Sort.

Internal Sorting Details

• Inside main memory.

• Data must be small.

• Avoids slower media.

• Various methods exist.

Bubble Sort

• Simple algorithm, compares and swaps adjacent elements.

• Inefficient on large datasets.

Working of Bubble Sort Algorithm

• Compares initial elements.

• Swaps if needed.

• Repeats until sorted.

Bubble Sort Example

• Iterates, compares, and swaps.

• Largest element bubbles up.

• Requires multiple passes.

Insertion Sort

• Builds sorted array one item at a time.

• Less efficient on large lists.

Working of Insertion Sort Algorithm

• Compares first two elements.

• Inserts each element in sorted position.

Quick Sort

• Efficient sorting algorithm which utilizes the principal of partioning

• Splits array around a pivot.

• Recursively sorts sub-arrays.

Working of Quick Sort Algorithm

• Pivot Selection, Partitioning and Recursion