# C++ Program to Implement Selection Sort

Problem Description

Write a C++ program to sort the given data using Selection Sort.

What is Selection Sort?

Selection sort in C++ is a simple sorting algorithm that repeatedly finds the minimum element from the unsorted portion of an array and places it at the beginning, resulting in a sorted array.

Selection Sort Algorithm

Here’s the pseudo code for the selection sort algorithm:

```procedure selectionSort(arr: array of elements)
n = length(arr)
for i = 0 to n-2
minIndex = i
for j = i+1 to n-1
if arr[j] < arr[minIndex]
minIndex = j
swap arr[i] and arr[minIndex]
end for
end procedure```

In the above pseudo code, arr represents the array to be sorted. The selectionSort procedure iterates through the array, finding the index of the minimum element in the unsorted portion (minIndex). It then swaps the current element with the minimum element. This process is repeated until the entire array is sorted.

Problem Solution

1. Starting from the beginning pick one number.
2. Compare it with others one by one.
3. replace if the other number is lesser than this one.
4. Display the result.
5. Exit.

Selection Sort Working Procedure:

Initially, the array is [998, 451, 2, 35, 1206].

In each iteration:
Find the minimum element in the unsorted portion and swap it with the first unsorted element.
Repeat until the entire array is sorted.

After the iterations:

• First: [2, 451, 998, 35, 1206]
• Second: [2, 35, 998, 451, 1206]
• Third: [2, 35, 998, 451, 1206]
• Fourth: [2, 35, 998, 1206, 451]
• Fifth: [2, 35, 451, 998, 1206]

The array is now sorted in ascending order: [2, 35, 451, 998, 1206].

Implementation of Selection Sort in C++.

This program is successfully run on Dev-C++ using TDM-GCC 4.9.2 MinGW compiler on a Windows system.

Note: Join free Sanfoundry classes at Telegram or Youtube
```/*
* Implementation of Selection Sort
*/

#include <iostream>

using namespace std;

// Sort arr[] of size n using Selection Sort.
void SelectionSort (int arr[], int n)
{
int i, j;
for (i = 0; i < n; ++i)
{
for (j = i+1; j < n; ++j)
{
// Comparing consecutive data and switching values if value at i > j.
if (arr[i] > arr[j])
{
arr[i] = arr[i]+arr[j];
arr[j] = arr[i]-arr[j];
arr[i] = arr[i]-arr[j];
}
}
// Value at i will be minimum of all the values above this index.
}
}

int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}

SelectionSort(arr, n);

// Display the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];

return 0;
}```
Program Explanation

1. Take input of data.
2. Call SelectionSort() function with ‘arr’ the array of data and ‘n’ the number of values, in the argument list.
3. Implement Sorting algorithm using nested for loop.
4. The first loop will run on ‘i’ from 0 to n-1.
5. The second loop will run on ‘j’ from i+1 to n-1.
6. Compare value at i with value at j.
7. Switch the values if arr[j+1] < arr[j].
9. Exit.

Time Complexity: O(n2)
The time complexity of the Selection Sort algorithm is O(n2) in the worst and average case.

Space Complexity: O(1)
The space complexity is O(1) since it sorts the array in-place without requiring additional memory allocation.

Runtime Test Cases

Testcase 1: (Average Case)

```Enter the number of data element to be sorted: 5
Enter element 1: 998
Enter element 2: 451
Enter element 3: 2
Enter element 4: 35
Enter element 5: 1206

Sorted Data ->2->35->451->998->1206```

Testcase 2: (Best Case)

```Enter the number of data element to be sorted: 5
Enter element 1: 2
Enter element 2: 332
Enter element 3: 456
Enter element 4: 1024
Enter element 5: 16565

Sorted Data ->2->332->456->1024->16565```

Testcase 3: (Worst Case)

```Enter the number of data element to be sorted: 5
Enter element 1: 99845
Enter element 2: 564
Enter element 3: 332
Enter element 4: 86
Enter element 5: 1

Sorted Data ->1->86->332->564->99845```

To practice programs on every topic in C++, please visit “Programming Examples in C++”, “Data Structures in C++” and “Algorithms in C++”.