This article demonstrates how to implement common sorting algorithms using C++ class templates with dynamic array storage. The implementation includes ranking sort, selection sort with early termination, bubble sort with early termination, and insertion sort.

Requirements

No STL containers (arrrays, vectors, etc.) Must use class templates (template) Define a dedicated sort class to encapsulate sorting methods Store data using dynamically allocated arrays Implement four sorting operations: renking sort, early-terminating selection sort, early-terminating bubble sort, and insertion sort

Input/Output Specification

Input: First line contains integer n (1≤n≤1000) representing the number of integers to sort. The second line contains n integers in the range [0, 1000], separated by spaces.

Output: A single line containing the sorted sequence.

Class Design

The class constructor handles input directly to avoid additional loops in the main function. A seperate output method displays the results.

template <typename E>
class Sorter {
public:
    Sorter(int size) {
        length = size;
        data = new E[size];
        for (int i = 0; i < size; i++) {
            cin >> data[i];
        }
    }
    
    void rankSort();
    void selectSort();
    void bubbleSort();
    void insertSort();
    
    void print() {
        for (int i = 0; i < length; i++) {
            cout << data[i] << " ";
        }
    }
    
private:
    E* data;
    int length;
};

Ranking Sort Implementation

Ranking sort works by computing the rank (position) of each element through pairwise comparisons, then placing elements into their corresponding positions using an auxiliary array.

template <typename E>
void Sorter<E>::rankSort() {
    int* rank = new int[length];
    for (int i = 0; i < length; i++) {
        rank[i] = 0;
    }
    
    for (int i = 1; i < length; i++) {
        for (int j = 0; j < i; j++) {
            if (data[j] <= data[i]) {
                rank[i]++;
            } else {
                rank[j]++;
            }
        }
    }
    
    E* temp = new E[length];
    for (int i = 0; i < length; i++) {
        temp[rank[i]] = data[i];
    }
    
    delete[] rank;
    for (int i = 0; i < length; i++) {
        data[i] = temp[i];
    }
    delete[] temp;
}

Selection Sort with Early Termination

This variant uses a boolean flag to detect when the array becomes sorted, allowing the algorithm to terminate early when no swaps are needed.

template <typename E>
void Sorter<E>::selectSort() {
    bool ordered = false;
    for (int limit = length; !ordered && limit > 1; limit--) {
        int pos = 0;
        ordered = true;
        
        for (int i = 1; i < limit; i++) {
            if (data[pos] <= data[i]) {
                pos = i;
            } else {
                ordered = false;
            }
        }
        
        E swap = data[pos];
        data[pos] = data[limit - 1];
        data[limit - 1] = swap;
    }
}

Bubble Sort with Early Termination

Similarly, this bubble sort implementation uses a flag to stop when no swaps occur during a complete pass.

template <typename E>
void Sorter<E>::bubbleSort() {
    bool ordered = false;
    for (int limit = length; limit > 1 && !ordered; limit--) {
        ordered = true;
        for (int i = 0; i < limit - 1; i++) {
            if (data[i] > data[i + 1]) {
                E swap = data[i];
                data[i] = data[i + 1];
                data[i + 1] = swap;
                ordered = false;
            }
        }
    }
}

Insertion Sort Implementation

Insertion sort builds the final sorted array one element at a time by inserting each element into its correct position among the previously sorted elements.

template <typename E>
void Sorter<E>::insertSort() {
    for (int i = 1; i < length; i++) {
        E key = data[i];
        int j;
        for (j = i - 1; j >= 0 && key < data[j]; j--) {
            data[j + 1] = data[j];
        }
        data[j + 1] = key;
    }
}

Complete Program

#include <iostream>
using namespace std;

template <typename E>
class Sorter {
public:
    Sorter(int size) {
        length = size;
        data = new E[size];
        for (int i = 0; i < size; i++) {
            cin >> data[i];
        }
    }
    
    void rankSort() {
        int* rank = new int[length];
        for (int i = 0; i < length; i++) {
            rank[i] = 0;
        }
        
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (data[j] <= data[i]) {
                    rank[i]++;
                } else {
                    rank[j]++;
                }
            }
        }
        
        E* temp = new E[length];
        for (int i = 0; i < length; i++) {
            temp[rank[i]] = data[i];
        }
        
        delete[] rank;
        for (int i = 0; i < length; i++) {
            data[i] = temp[i];
        }
        delete[] temp;
    }
    
    void selectSort() {
        bool ordered = false;
        for (int limit = length; !ordered && limit > 1; limit--) {
            int pos = 0;
            ordered = true;
            
            for (int i = 1; i < limit; i++) {
                if (data[pos] <= data[i]) {
                    pos = i;
                } else {
                    ordered = false;
                }
            }
            
            E swap = data[pos];
            data[pos] = data[limit - 1];
            data[limit - 1] = swap;
        }
    }
    
    void bubbleSort() {
        bool ordered = false;
        for (int limit = length; limit > 1 && !ordered; limit--) {
            ordered = true;
            for (int i = 0; i < limit - 1; i++) {
                if (data[i] > data[i + 1]) {
                    E swap = data[i];
                    data[i] = data[i + 1];
                    data[i + 1] = swap;
                    ordered = false;
                }
            }
        }
    }
    
    void insertSort() {
        for (int i = 1; i < length; i++) {
            E key = data[i];
            int j;
            for (j = i - 1; j >= 0 && key < data[j]; j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = key;
        }
    }
    
    void print() {
        for (int i = 0; i < length; i++) {
            cout << data[i] << " ";
        }
    }
    
private:
    E* data;
    int length;
};

int main() {
    int n;
    cin >> n;
    Sorter<int> sorter(n);
    sorter.insertSort();
    sorter.print();
    return 0;
}

The template parameter E allows the sorter class to handle various data types while the early-termination variants efficiently handle already-sorted or nearly-sorted inputs.