Selection Sort

Selection sort finds minimum element of the unsorted elements and swaps it with the first element of unsorted part. It continues with the rest of the unsorted elements with this manner. Below is the implementation of selection sort. Note its worst case is O(n^2).

#include <iostream>

using namespace std;

int find_min(int* arr, size_t size, int start)
{
    int min = arr[start];
    int minIndex = start;

    for (int i = start+1; i < size; ++i) {
        if (min > arr[i]) {
            min = arr[i];
            minIndex = i;
        }
    }

    return minIndex;
}

void selection_sort(int* arr, size_t size)
{
    for (int i = 0; i < size; ++i) {
        int minIndex = find_min(arr, size, i);

        // current index is not the minimum so swap it
        if (minIndex != i) {
            swap(arr[i], arr[minIndex]);
        }
    }
}

void display(int* arr, size_t size)
{
    for (int i = 0; i < size; ++i) {
        cout << arr[i] << endl;
    }
}


int main() {
    int a[] = {20,30,10,60,40,50,80,70,90};

    display(a, 9);

    selection_sort(a, 9);

    display(a, 9);

    return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *