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].

advertisement
advertisement

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].
8. Return to main and display the result.
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.

advertisement
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)

advertisement
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++”.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.