Slection Sort

Selection sort theory  :

Steps involved in Selection Sort:

1. Find the smallest element in the array and swap it with the first element of the array i.e. a[0].
2. The elements left for sorting are n-1 so far. Find the smallest element in the array from index 1 to n-1 i.e. a[1] to a[n-1] and swap it with a[1].
3. Continue this process for all the elements in the array until we get a sorted list.

Program : 

/******************************************************************************

Online C++ Compiler.

Code, Compile, Run and Debug C++ program online.

SELECTION SORT

*******************************************************************************/

#include <iostream>

using namespace std;

// C++ program for implementation of selection sort

#include <bits/stdc++.h>

using namespace std;

//swap function 

void swap(int *xp, int *yp)

{

int temp = *xp;

*xp = *yp;

*yp = temp;

}

// SELECTION SORT FUNCTION

void selectionSort(int arr[], int n)

{

int i, j, min_idx;

// One by one move boundary of unsorted subarray

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

{

// Find the minimum element in unsorted array

min_idx = i;

for (j = i+1; j < n; j++)

if (arr[j] < arr[min_idx])

min_idx = j;

// Swap the found minimum element with the first element

swap(&arr[min_idx], &arr[i]);

}

}

/* Function to print an array */

void printArray(int arr[], int size)

{

int i;

for (i=0; i < size; i++)

cout << arr[i] << " ";

cout << endl;

}

// Main Function

int main()

{

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr)/sizeof(arr[0]);

selectionSort(arr, n);

cout << "Sorted array: \n";

printArray(arr, n);

return 0;

}

// Time Complexity: O(n^2) n Squire 

Program Link: https://onlinegdb.com/9pM7uP0lL