Sorting Techniques

Sorting Techinques
3A. Write a program to implement bubble sort.
Sort the following array using bubble sort technique
8,7,5,11,15,2.

#include <stdio.h>
#include <conio.h> // Required for clrscr() and getch()

int main() {
    int a[6] = {8, 7, 5, 11, 15, 2}; // Array initialization
    int p, n, j, i, temp;

    clrscr(); // Clears the screen

    n = 6; // Length of the array

    // Display the original array
    printf("\n A : \t");
    for (i = 0; i < n; i++) {
        printf("%d\t", a[i]);
    }

    // Bubble Sort algorithm
    for (p = 1; p <= n - 1; p++) {
        printf("\n Pass : %d", p);
        for (i = 0; i < n - p; i++) {
            if (a[i] > a[i + 1]) {
                // Swap elements
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }

        // Display the array after each pass
        printf("\n A : \t");
        for (j = 0; j < n; j++) {
            printf("%d\t", a[j]);
        }
    }

    getch(); // Wait for a key press
    return 0;
}


3B. Write a program to implement selection sort
Sort the following array using selection sort technique
73,18,10,5,21,32,74.

#include <stdio.h>
#include <conio.h> // Required for clrscr() and getch()

int a[30], n;

// Function declaration
void selection_sort();

int main() {
    int i;

    clrscr(); // Clear screen for Turbo C

    printf("Enter the Size of Array! : ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        printf("Enter the elements of the array: ");
        scanf("%d", &a[i]);
    }

    // Call the selection sort function
    selection_sort();

    printf("\n\nElements after Sorting: ");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    getch(); // Wait for a key press
    return 0;
}

// Function definition
void selection_sort() {
    int i, j, min, temp;

    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[min]) {
                min = j;
            }
        }
        // Swap elements
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
}

3C. Write a program to implement insertion sortWrite a program to implement insertion sort
Sort the following array using insertion sort technique
15,11,18,5,3,7,21

#include <stdio.h>
#include <conio.h> // Required for Turbo C functions

int main() {
    int a[7] = {15, 11, 18, 5, 3, 7, 21}, i, n, temp, k, j;
    n = 7;

    clrscr(); // Clear screen for Turbo C

    // Display the original array
    printf("\n A : \t");
    for (i = 0; i < n; i++) {
        printf("%d \t", a[i]);
    }

    // Insertion sort algorithm
    for (i = 1; i < n; i++) {
        printf("\n Pass! %d", i);
        temp = a[i];
        k = i - 1;

        while (k >= 0 && temp < a[k]) {
            a[k + 1] = a[k];
            k = k - 1;
        }
        a[k + 1] = temp;

        // Display the array after each pass
        printf("\n A : \t");
        for (j = 0; j < n; j++) {
            printf("%d \t", a[j]);
        }
    }

    getch(); // Wait for a key press
    return 0;
}

4A. : Write a program to implement Merge Sort

#include <stdio.h>
#include <conio.h> // Required for Turbo C functions

#define MAX 10 // Maximum size of the array

// Merge function
void merge(int a[], int temp[], int l_pos, int r_pos, int r_end) {
    int i, l_end, n, tmp_pos;
    l_end = r_pos - 1;
    tmp_pos = l_pos;
    n = r_end - l_pos + 1;

    while (l_pos <= l_end && r_pos <= r_end) {
        if (a[l_pos] <= a[r_pos]) {
            temp[tmp_pos++] = a[l_pos++];
        } else {
            temp[tmp_pos++] = a[r_pos++];
        }
    }

    while (l_pos <= l_end) {
        temp[tmp_pos++] = a[l_pos++];
    }

    while (r_pos <= r_end) {
        temp[tmp_pos++] = a[r_pos++];
    }

    // Copy the sorted temp array back to the original array
    for (i = 0; i < n; i++, r_end--) {
        a[r_end] = temp[r_end];
    }
}

// Recursive function to divide the array
void Msort(int a[], int temp[], int left, int right) {
    int center;
    if (left < right) {
        center = (left + right) / 2;
        Msort(a, temp, left, center);
        Msort(a, temp, center + 1, right);
        merge(a, temp, left, center + 1, right);
    }
}

// Merge sort function
void mergeSort(int a[], int n) {
    int temp[MAX]; // Statically allocate the temporary array
    Msort(a, temp, 0, n - 1);
}

// Main function
int main() {
    int i, n, a[MAX];

    clrscr(); // Clear screen for Turbo C

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

    if (n > MAX) {
        printf("Error: Maximum array size exceeded!\n");
        return 1;
    }

    for (i = 0; i < n; i++) {
        printf("Enter the elements: ");
        scanf("%d", &a[i]);
    }

    mergeSort(a, n);

    printf("\nThe Sorted Elements Are: ");
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    getch(); // Wait for a key press
    return 0;
}