To develop templates of standard sorting algorithms, namely Bubble Sort, Insertion Sort and Quick Sort.

 

Experiment 8

Aim

To develop templates of standard sorting algorithms, namely Bubble Sort, Insertion Sort and Quick Sort.

Objectives

• To understand function templates.
• To implement generic sorting algorithms.
• To compare different sorting approaches.
• To apply templates to array-based data.

Program

#include <iostream>

using namespace std;

 

template <class T>

void bubbleSort(T a[], int n) {

    for (int i = 0; i < n - 1; i++)

        for (int j = 0; j < n - i - 1; j++)

            if (a[j] > a[j + 1])

                swap(a[j], a[j + 1]);

}

 

template <class T>

void insertionSort(T a[], int n) {

    for (int i = 1; i < n; i++) {

        T key = a[i];

        int j = i - 1;

 

        while (j >= 0 && a[j] > key) {

            a[j + 1] = a[j];

            j--;

        }

 

        a[j + 1] = key;

    }

}

 

template <class T>

void quickSort(T a[], int low, int high) {

    if (low >= high)

        return;

 

    T pivot = a[high];

    int i = low - 1;

 

    for (int j = low; j < high; j++) {

        if (a[j] < pivot)

            swap(a[++i], a[j]);

    }

 

    swap(a[i + 1], a[high]);

 

    int p = i + 1;

 

    quickSort(a, low, p - 1);

    quickSort(a, p + 1, high);

}

 

template <class T>

void display(T a[], int n) {

    for (int i = 0; i < n; i++)

        cout << a[i] << " ";

 

    cout << endl;

}

 

int main() {

    int a[] = {5, 2, 8, 1, 3};

    int n = 5;

 

    cout << "Original: ";

    display(a, n);

 

    bubbleSort(a, n);

    cout << "Bubble Sort: ";

    display(a, n);

 

    int b[] = {5, 2, 8, 1, 3};

    insertionSort(b, n);

    cout << "Insertion Sort: ";

    display(b, n);

 

    int c[] = {5, 2, 8, 1, 3};

    quickSort(c, 0, n - 1);

    cout << "Quick Sort: ";

    display(c, n);

 

    return 0;

}

Result

Thus, Bubble Sort, Insertion Sort and Quick Sort were successfully implemented using function templates.