====================================================================================================
2(ii) Binary Search
====================================================================================================

AIM: To implement Binary Search algorithm to find a key element in a sorted array.

DESCRIPTION: Binary search is an efficient algorithm that works only on sorted arrays. It repeatedly divides the search interval in half by comparing the middle element with the target key. If the middle element equals the key, the search succeeds. If the key is smaller, the search continues on the left half; if larger, on the right half. This divide-and-conquer approach achieves O(log n) time complexity, making it significantly faster than linear search for large datasets. The algorithm requires the array to be sorted beforehand. The implementation uses two pointers (low and high) and calculates mid iteratively. Binary search is widely used in database indexing, dictionary lookups, and whenever fast searching on sorted data is needed.

PROGRAM:
#include<stdio.h>

int main(){
    int a[100], n, key, l=0, r, mid;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);

    scanf("%d",&key);
    r=n-1;

    while(l<=r){
        mid=(l+r)/2;
        if(a[mid]==key){
            printf("Found");
            return 0;
        }
        else if(a[mid]<key)
            l=mid+1;
        else
            r=mid-1;
    }
    printf("Not found");
}

OUTPUT:
Input:
5
10 20 30 40 50
30
Output: Found


====================================================================================================
3(ii) Insertion Sort
====================================================================================================

AIM: To implement Insertion Sort algorithm to sort an array in ascending order.

DESCRIPTION: Insertion sort builds the final sorted array one element at a time. It works similarly to sorting playing cards in hand: take each element and insert it into its correct position among previously sorted elements. The algorithm divides the array into sorted (left) and unsorted (right) regions. For each unsorted element, it moves leftwards, shifting larger elements right until finding the correct insertion point. Time complexity is O(n²) in worst and average cases, but O(n) in best case (already sorted). Insertion sort is efficient for small datasets or nearly sorted data, is stable, and sorts in-place. It's often used as the base case in advanced sorts like QuickSort and MergeSort for small subarrays due to low overhead.

PROGRAM:
#include<stdio.h>

int main(){
    int a[100],n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);

    for(int i=1;i<n;i++){
        int key=a[i],j=i-1;
        while(j>=0 && a[j]>key){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=key;
    }

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

OUTPUT:
Input:
5
64 34 25 12 22
Output: 12 22 25 34 64

====================================================================================================
3(iii) Selection Sort
====================================================================================================

AIM: To implement Selection Sort algorithm to sort an array in ascending order.

DESCRIPTION: Selection sort divides the array into sorted and unsorted regions. In each pass, it finds the minimum element from the unsorted region and swaps it with the first unsorted element, expanding the sorted region. This process continues until the entire array is sorted. After i passes, the first i elements are in their final positions. Time complexity is O(n²) in all cases, as each pass scans the entire remaining unsorted portion regardless of input order. Selection sort performs fewer swaps than bubble sort (only n-1 swaps total) but makes the same number of comparisons. It is an in-place, unstable sorting algorithm (the relative order of equal elements may change). It is simple but inefficient for large datasets.

PROGRAM:
#include<stdio.h>

int main(){
    int a[100],n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);

    for(int i=0;i<n;i++){
        int min=i;
        for(int j=i+1;j<n;j++)
            if(a[j]<a[min])
                min=j;

        int t=a[i];
        a[i]=a[min];
        a[min]=t;
    }

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

OUTPUT:
Input:
5
64 34 25 12 22
Output: 12 22 25 34 64

====================================================================================================
4(i) Quick Sort
====================================================================================================

AIM: To implement Quick Sort algorithm to sort an array in ascending order.

DESCRIPTION: Quick sort is a divide-and-conquer algorithm that selects a pivot element and partitions the array such that elements less than pivot go left and greater go right. It then recursively sorts the subarrays. The given implementation uses the first element as pivot (though more efficient pivots exist like median-of-three). The partition step scans from both ends, swapping elements to maintain the invariant. After partitioning, the pivot is placed in its correct sorted position. Average and best-case time complexity is O(n log n), worst-case O(n²) (when pivot is always smallest or largest). Quick sort sorts in-place and is generally faster in practice than other O(n log n) algorithms due to good cache performance and low overhead.

PROGRAM:
#include<stdio.h>

void quick(int a[], int l, int r){
    if(l>=r) return;

    int i=l,j=r,p=a[l];

    while(i<j){
        while(a[i]<=p) i++;
        while(a[j]>p) j--;

        if(i<j){
            int t=a[i]; a[i]=a[j]; a[j]=t;
        }
    }
    a[l]=a[j]; a[j]=p;

    quick(a,l,j-1);
    quick(a,j+1,r);
}

int main(){
    int a[100],n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);

    quick(a,0,n-1);

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

OUTPUT:
Input:
6
10 7 8 9 1 5
Output: 1 5 7 8 9 10

====================================================================================================
4(ii) Merge Sort
====================================================================================================

AIM: To implement Merge Sort algorithm to sort an array in ascending order.

DESCRIPTION: Merge sort is a divide-and-conquer algorithm that recursively divides the array into halves until single elements remain, then merges the sorted halves back together. The merge operation combines two sorted subarrays into one sorted array using a temporary buffer. The algorithm guarantees O(n log n) time complexity in all cases (worst, average, best), making it highly predictable. However, it requires O(n) additional space for the temporary array during merging (not in-place). Merge sort is stable (preserves relative order of equal elements) and is well-suited for sorting linked lists and large datasets where predictable performance is required. It is the standard sorting method when stable sorting is needed and memory overhead is acceptable.

PROGRAM:
#include<stdio.h>

void merge(int a[], int l, int m, int r){
    int i=l,j=m+1,k=0,temp[100];

    while(i<=m && j<=r){
        if(a[i]<a[j]) temp[k++]=a[i++];
        else temp[k++]=a[j++];
    }

    while(i<=m) temp[k++]=a[i++];
    while(j<=r) temp[k++]=a[j++];

    for(i=l,k=0;i<=r;i++,k++)
        a[i]=temp[k];
}

void ms(int a[], int l, int r){
    if(l<r){
        int m=(l+r)/2;
        ms(a,l,m);
        ms(a,m+1,r);
        merge(a,l,m,r);
    }
}

int main(){
    int a[100],n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);

    ms(a,0,n-1);

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

OUTPUT:
Input:
6
38 27 43 3 9 82
Output: 3 9 27 38 43 82



====================================================================================================
7(ii) Priority Queue (Simple)
====================================================================================================

AIM: To implement a simple Priority Queue where elements are processed based on priority rather than FIFO.

DESCRIPTION: A priority queue is an abstract data type where each element has an associated priority. Elements with higher priority are served before those with lower priority. If two elements have equal priority, they are served according to FIFO order. The given simple implementation stores priorities in an array and sorts them in ascending order (assuming smaller number = higher priority). A full priority queue would typically be implemented using a heap data structure (binary heap) for O(log n) insertion and deletion. Priority queues are used in operating systems (process scheduling), Dijkstra's shortest path algorithm, Huffman coding, event-driven simulation, and bandwidth management. This simplified version demonstrates the priority concept but is inefficient for large datasets.

PROGRAM:
#include<stdio.h>

int main(){
    int a[100], n;
    scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);

    // smaller number = higher priority
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            if(a[i]>a[j]){
                int t=a[i]; a[i]=a[j]; a[j]=t;
            }

    printf("Priority order:\n");
    for(int i=0;i<n;i++)
        printf("%d ",a[i]);
}

OUTPUT:
Input:
5
5 2 9 1 7
Output:
Priority order:
1 2 5 7 9


====================================================================================================
8(ii) Doubly Linked List
====================================================================================================

AIM: To implement a Doubly Linked List with basic insertion operation.

DESCRIPTION: A doubly linked list extends the singly linked list by adding a previous pointer (prev) in each node, allowing bidirectional traversal. Each node contains data, a pointer to the next node, and a pointer to the previous node. The given program creates a list by inserting nodes at the beginning: for each new node, it sets next to current head, prev to NULL, and if head exists, sets head->prev to new node, then updates head to new node. Doubly linked lists support O(1) insertion/deletion at both ends and easier deletion of a given node (without traversing to find predecessor). However, they require extra memory for the prev pointer. They are used in browser history, undo/redo operations, cache implementations (LRU), and where backward traversal is needed.

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

struct node{
    int data;
    struct node *prev,*next;
};

int main(){
    struct node *head=NULL,*temp;

    for(int i=1;i<=3;i++){
        temp=(struct node*)malloc(sizeof(struct node));
        temp->data=i;
        temp->prev=NULL;
        temp->next=head;
        if(head) head->prev=temp;
        head=temp;
    }

    while(head){
        printf("%d ",head->data);
        head=head->next;
    }
}

OUTPUT:
3 2 1
