Radix Sort

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void printArr ( int arr[], int arrSize )
{
    for ( int i = 0; i < arrSize; i++ ) {
        cout << arr[i] << "   ";
    }
    cout << endl;
}

void radixSort ( int arr[], int arrSize )
{
    const int MaxBuckets = 10;
    //const int MaxBucketSize = 100;
    vector < vector<int> > buckets(MaxBuckets);
    
    //find max value for termination condition
    int maxValue = arr[0];
    for ( int i = 1; i < arrSize; i++ ) {
        if ( arr[i] > maxValue ) {
            maxValue = arr[i];
        }
    }
    
    int radixPos = 0;
    int extractor = pow(10, radixPos);
    while (maxValue / extractor > 0) {
    
        //push the elements to the respective buckets for the radix position
        for ( int i = 0; i < arrSize; i++ ) {
            int bucketIdx = (arr[i] / extractor) % 10;
            buckets[bucketIdx].push_back(arr[i]); 
        }
        
        //put the elements back from the bucket to the array
        int arrIdx = 0;
        for ( int i = 0; i < MaxBuckets; i++ ) {
            for ( int j = 0; j < buckets[i].size(); j++ ) {
                arr[arrIdx++] = buckets[i][j];
            }
        }
        buckets.clear();
        buckets.resize(10);
        cout << "iter "<< radixPos << ": ";
        printArr(arr, arrSize);
        
        radixPos++;
        extractor = pow(10, radixPos);
    }
    
}

int main ( )
{
    cout << "Enter the size: ";
    int arrSize;
    cin >> arrSize;
    
    cout << "Enter the numbers\n";
    int arr[arrSize];
    for ( int i = 0; i < arrSize; i++ ) {
        cin >> arr[i];
    }
    
    radixSort(arr, arrSize);
    
    cout << "--------Array sorted------\n";
    printArr(arr, arrSize);
    
    return 0;
}

Selection Sort

#include <iostream>

using namespace std;

void swap ( int &a, int &b )
{
    int temp = a;
    a = b;
    b = temp;
    return;
}

void printArr ( int arr[], int arrSize )
{
    for ( int i = 0; i < arrSize; i++ ) {
        cout << arr[i] << "   ";
    }
    cout << endl;
}

void selectionSort ( int arr[], int arrSize )
{
    int sortedIndex = 0;
    
    while ( sortedIndex < arrSize ) {
        int min = arr[sortedIndex];
        int minIndex = sortedIndex;
        for ( int i = sortedIndex + 1; i < arrSize; i++ ) {
            if ( arr[i] < min ) {
                min = arr[i];
                minIndex = i;
            }
        }
        swap(arr[minIndex], arr[sortedIndex]);
        cout << "iter " << sortedIndex << ": ";
        printArr(arr, arrSize);
        sortedIndex++;
    }
}

int main ( )
{
    cout << "Enter the size: ";
    int arrSize;
    cin >> arrSize;
    
    cout << "Enter the numbers\n";
    int arr[arrSize];
    for ( int i = 0; i < arrSize; i++ ) {
        cin >> arr[i];
    }
    
    selectionSort(arr, arrSize);
    
    cout << "--------Array sorted------\n";
    printArr(arr, arrSize);
    
    return 0;
}

selection sort image

Insertion Sort

#include <iostream>

using namespace std;

void swap ( int &a, int &b )
{
    int temp = a;
    a = b;
    b = temp;
    return;
}

void printArr ( int arr[], int arrSize )
{
    for ( int i = 0; i < arrSize; i++ ) {
        cout << arr[i] << "   ";
    }
    cout << endl;
}

void insertionSort ( int arr[], int arrSize )
{
    int sortedIndex = 0;
    
    while ( sortedIndex < arrSize ) {
        for ( int i = sortedIndex; i > 0; i-- ) {
            if ( arr[i] < arr[i-1] ) {
                swap(arr[i], arr[i-1]);
            } else {
                break;
            }
        }
        cout << "iter " << sortedIndex << ": ";
        printArr(arr, arrSize);
        sortedIndex++;
    }
}

int main ( )
{
    cout << "Enter the size: ";
    int arrSize;
    cin >> arrSize;
    
    cout << "Enter the numbers\n";
    int arr[arrSize];
    for ( int i = 0; i < arrSize; i++ ) {
        cin >> arr[i];
    }
    
    insertionSort(arr, arrSize);
    
    cout << "--------Array sorted------\n";
    printArr(arr, arrSize);
    
    return 0;
}

Insertion Sort gif

Bubble Sort


#include &lt;iostream&gt;

using namespace std;

void swap ( int &amp;a, int &amp;b )
{
    int temp = a;
    a = b;
    b = temp;
    return;
}

void printArr ( int arr[], int arrSize )
{
    for ( int i = 0; i &lt; arrSize; i++ ) {
        cout &lt;&lt; arr[i] &lt;&lt; &quot;   &quot;;
    }
    cout &lt;&lt; endl;
}

void bubbleSort ( int arr[], int arrSize )
{
//last element would already be in place hence n-1 iteration at max
    for ( int k = 0; k &lt; arrSize-1; k++ ) {
        //in each iteration the last k+1 elements would have been already sorted.
        //Hence comparing only n-(k+1) elements.
        for ( int i = 0; i &lt; arrSize-k-1 ; i++ ) {
            if ( arr[i] &gt; arr[i+1] ) {
                swap ( arr[i], arr[i+1] );
            }
        }
        cout &lt;&lt; &quot;iteration &quot; &lt;&lt; k+1 &lt;&lt; &quot;: &quot;;
        printArr(arr, arrSize);
    }
}

int main ( )
{
    cout &lt;&lt; &quot;Enter the size: &quot;;
    int arrSize;
    cin &gt;&gt; arrSize;

    cout &lt;&lt; &quot;Enter the numbers\n&quot;;
    int arr[arrSize];
    for ( int i = 0; i &lt; arrSize; i++ ) {
        cin &gt;&gt; arr[i];
    }

    bubbleSort(arr, arrSize);

    cout &lt;&lt; &quot;--------Array sorted------\n&quot;;
    printArr(arr, arrSize);

    return 0;
}

 

Bubble sort gif