EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 600+ Courses All in One Bundle
  • Login

Selection Sort in C++

Home » Software Development » Software Development Tutorials » C ++ Programming Tutorial » Selection Sort in C++

Selection Sort in C++

Introduction to Selection Sort in C++

Selection sort is a sort algorithm which uses to sort the array of n elements. In Selection sort, every pass finds the smallest element and inserts it to the correct position in an array. An algorithm works on two sub array. First subarray which store sorted elements and second subarray which store unsorted elements. In every pass of selection, sort finds the smallest element from the unsorted array and placed to the sorted array. In simple the first pass finds the smallest element and places it in the first position. And in the second pass it finds the second smallest element and places it on the second position and so on. The process is repeated till all the elements of an array is sorted.

Selection Sort Logic

Let’s take an array L which is having n number of elements and which are to be sort by using selection sort. So the selection sort algorithm processes in the following pass.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

  • I Pass: Find the smallest element in an array with its index. And then swap L[0] with L[index]. The result of this pass is, we have L[0] sorted subarray and n-1 elements are to be sort unsorted subarray.
  • II Pass: Find the smallest element in unsorted subarray with its index. And then swap L[1] with L[index].  The result of this pass is, we have L[0] and L[1] sorted subarray and n-1 elements are to be sort unsorted subarray, and so on.
  • Similarly, it performs n-1 passes and in n-1 pass, finds the smallest element in unsorted subarray with its index. And then swap L[n-1] with L[index]. The result of this pass is, we have L[0] to L[n-1] are sorted as sorted subarray and no more elements are to be sort.

Let’s see how above passes works with an example, so let’s take an array of 5 elements an example L = [ 6, 2, 5, 3, 9 ], which are to be sort using selection sort as:

  • I Pass: [ 6, 2, 5, 3, 9 ] –> [ 2, 6, 5, 3, 9 ], Algorithm start by finding the first smallest number in L[0] to L[4] and place it at L[0].
  • II Pass: [ 2, 6, 5, 3, 9 ] –> [ 2, 3, 5, 6, 9 ], find the smallest number in range L[1] to L[4] and place it at L[1].
  • III Pass: [ 2, 3, 5, 6, 9 ] –> [ 2, 3, 5, 6, 9 ], find the smallest number in range L[2] to L[4] and place it at L[2].
  • IV Pass: [ 2, 3, 5, 6, 9 ] –> [ 2, 3, 5, 6, 9 ], find smallest number in range L[3] to L[4] and place it at L[3].

Now, an array is sorted after all n-1 pass.

Selection Sort Algorithm

Consider L is an array which is having n number of elements. So selection sort algorithm to sort the given L array algorithm is:

Algorithm:

begin Selection_Sort (L, N)
for i = 1 to N-1
call small (L, i, N, index)
swap L[i] with L[index] end for
return L
end Selection_Sort
begin small (L, i, N, index)
initialize small = L[i] initialize index = i
for J = i+1 to N -1
if small > L[j] small = L[j] index = j
end if
end for
return index
end small

The Complexity of Selection Sort Technique:

  • Best Case Running Time: Ω( n )
  • Average Case Running time Complexity: θ( n2 )
  • Worst Case Running time Complexity: o( n2 )
  • Space Complexity: o( 1 )

Examples to Implement Selection Sort in C++

Next, we write the c++ code to understand the selection sort technique more clearly with the following example where we use the selection sort technique inside for loop to apply on array elements.

Popular Course in this category
C++ Training (4 Courses, 5 Projects, 4 Quizzes)4 Online Courses | 5 Hands-on Projects | 37+ Hours | Verifiable Certificate of Completion | Lifetime Access | 4 Quizzes with Solutions
4.5 (4,837 ratings)
Course Price

View Course

Related Courses
Java Training (40 Courses, 29 Projects, 4 Quizzes)C Programming Training (3 Courses, 5 Project)

Example #1

Code:

#include<iostream>
using namespace std;
int small(int L[], int n, int i);
int main ()
{
int i, j, k, index, t;
int L[10] = { 10, 12, 7, 9, 5 };
cout << "The list of element before sorting:" <<endl;
for(i = 0; i < 5; i++)
{
cout<<L[i]<<endl;
}
for( i = 0;i < 5; i++)
{
index = small(L, 5, i);
t = L[i];
L[i] = L[index];
L[index] = t;
}
cout << "The list of element after sorting:" <<endl;
for(i = 0; i < 5; i++)
{
cout<<L[i]<<endl;
}
return 0;
}
int small(int L[], int n, int i)
{
int s, index, j;
s = L[i];
index = i;
for( j = i+1; j < 5; j++)
{
if(L[j] < s )
{
s = L[j];
index = j;
}
}
return index;
}

Output:

Selection Sort in C++

Next, we write the c++ code and we write the bubble sort technique inside a function, which we will be call and pass an array.

Example #2

Code:

#include<iostream>
using namespace std;
void disp( int *L )
{
int i;
for(i = 0; i < 5; i++)
{
cout<<L[i]<<endl;
}
}
int small(int L[], int n, int i);
void Selection_Sort(int *L, int N )
{
int t, i, index;
for( i = 0;i < N; i++)
{
index = small(L, N, i);
t = L[i];
L[i] = L[index];
L[index] = t;
}
}
int main ()
{
int i, j, N=5;
int L[10] = { 10, 12, 7, 9, 5 };
cout << "The list of element before sorting:" <<endl;
disp(L);
Selection_Sort( L, N );
cout << "The list of element after sorting:" <<endl;
disp(L);
return 0;
}
int small(int L[], int n, int i)
{
int s, index, j;
s = L[i];
index = i;
for( j = i+1; j < 5; j++)
{
if(L[j] < s )
{
s = L[j];
index = j;
}
}
return index;
}

Output:

For Loop Example 2

Conclusion

In Selection sort algorithm every pass finds the smallest element and insert it to the correct position in an array. An array with n elements need (n-1) passes to sort them. The complexity of selection sort algorithm is O( n2 ).

Recommended Article

This is a guide to Selection Sort in C++. Here we discuss the Introduction to Selection Sort in C++ and its Examples along with Code Implementation and Output. you can also go through our suggested articles to learn more –

  1. Python Sort List
  2. Python Sort Array
  3. Bubble Sort in C#
  4.  Insertion Sort in C++

All in One Software Development Bundle (600+ Courses, 50+ projects)

600+ Online Courses

50+ projects

3000+ Hours

Verifiable Certificates

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
C plus plus Programming Tutorial
  • Sorting
    • Sorting in C++ 
    • Heap Sort in C++
    • C++ Vector Sort
    • Insertion Sort in C++
    • Selection Sort in C++
  • Basic
    • Introduction To C++
    • What is C++
    • Features of C++
    • Applications of C++
    • Best C++ Compiler
    • C++ Data Types
    • C++ Double
    • C++ unsigned int
    • User Defined Data Types in C++
    • Variables in C++
    • C++ Keywords
    • Pointers in C++
    • C++ Void Pointer
    • Function Pointer in C++
    • Iterator in C++
    • C++ Commands
    • Object in C++
    • C++ Literals
    • C++ Reference
    • C++ Undefined Reference
    • String in C++
    • C++ Programming Language (Basics)
    • C++ Identifiers
    • C++ Header Files
    • Type Casting in C++
    • C++ Formatter
  • Operators
    • C++ Operators
    • Arithmetic Operators in C++
    • Assignment Operators in C++
    • Bitwise Operators in C++
    • Relational Operators in C++
    • Boolean Operators in C++
    • Unary Operators in C++
    • C++ Operator[]
    • Operator Precedence in C++
    • C++ operator=()
  • Control Statements
    • Control Statement in C++
    • if else Statement in C++
    • Else If in C++
    • Nested if in C++
    • Continue Statement in C++
    • Break Statement in C++
    • Switch Statement in C++
    • goto Statement in C++
    • C++ Struct
    • Loops in C++
    • Do While Loop in C++
    • Nested Loop in C++
  • Functions
    • C++ String Functions
    • Math Functions in C++
    • Friend Function in C++
    • Recursive Function in C++
    • Virtual Functions in C++
    • strcat() in C++
    • swap() in C++
    • strcmp() in C++
    • ceil function in C++
    • C++ begin()
    • size() in C++
    • C++ test()
    • C++ any()
    • C++ Bitset
    • C++ find()
    • C++?Aggregation
    • C++?String append
    • C++ String Copy
    • C++ end()
    • C++ endl
    • C++ push_back
    • C++ shuffle()
    • malloc() in C++
    • C++ reserve()
    • C++ unique()
    • C++ sort()
    • C++ find_if()
    • Reflection in C++
    • C++ replace()
    • C++ search()
    • C++ Memset
    • C++ size_t
    • C++ Substring
    • C++ Max
    • C++ absolute value
    • C++ memcpy
    • C++ wchar_t
    • C++ free()
    • C++ sizeof()
    • C++ Move Semantics
  • Array
    • Arrays in C++
    • 2D Arrays in C++
    • 3D Arrays in C++
    • Multi-Dimensional Arrays in C++
    • C++ Array Functions
    • String Array in C++
    • C++ Length of Array
    • C++ arraylist
  • Constuctor and Destructor
    • Constructor and Destructor in C++
    • Constructor in C++
    • Destructor in C++
    • Copy Constructor in C++
    • Parameterized Constructor in C++
  • Overloading and overriding
    • Overloading and Overriding in C++
    • Overloading in C++
    • Overriding in C++
    • Function Overloading in C++
    • Function Overriding in C++
    • Method Overloading in C++
  • Inhertiance
    • Types of Inheritance in C++
    • Single Inheritance in C++
    • Multiple Inheritance in C++
    • Hierarchical Inheritance in C++
    • Multilevel Inheritance in C++
    • Hybrid Inheritance in C++
  • Advanced
    • C++ namespace
    • Encapsulation in C++
    • Access Modifiers in C++
    • Abstract Class in C++
    • C++ Class and Object
    • What is Template Class in C++?
    • C++ Algorithm
    • Data Structures and Algorithms C++
    • C++ Garbage Collection
    • Virtual Keyword in C++
    • Access Specifiers in C++
    • Storage Class in C++
    • Call by Value in C++
    • Multimap in C++
    • C++ Multiset
    • C++ Lambda Expressions
    • Stack in C++
    • C++ Static
    • C++ static_cast
    • Deque in C++
    • C++ Vector Functions
    • C++ 2D Vector
    • C++ List
    • C++ Mutable
    • Enum in C++
    • Abstraction in C++
    • Signal in C++
    • C++ Queue
    • Priority Queue in C++
    • Regular Expressions in C++
    • C++ Hash Table
    • File Handling in C++
    • C++ Stream
    • ifstream in C++
    • C++ ofstream
    • C++ fstream
    • C++ Read File
    • C++ iomanip
    • Macros in C++
    • Templates in C++
    • C++ setprecision
    • C++ Int to String
    • C++ thread( )
    • C++ Thread Pool
    • C++ thread_local
  • Programs
    • Patterns in C++
    • Star Patterns In c++
    • Swapping in C++
    • Reverse Number in C++
    • Palindrome Program in C++
    • Palindrome in C++
    • Factorial Program in C++
    • Fibonacci Series in C++
    • Square Root in C++
    • Random Number Generator in C++
    • Prime Number in C++
    • Leap Year Program in C++
    • Anagram in C++
    • Armstrong Number in C++
    • Reverse String in C++
    • Socket Programming in C++
    • Matrix Multiplication in C++
    • C++ using vs typedef
    • C++ vector vs list
    • C++ vector vs array
  • Interview question
    • C++ Interview Questions
    • Multithreading Interview Questions C++

Related Courses

C++ Training Course

Java Training Course

C Programming Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Java Tutorials
  • Python Tutorials
  • All Tutorials
Certification Courses
  • All Courses
  • Software Development Course - All in One Bundle
  • Become a Python Developer
  • Java Course
  • Become a Selenium Automation Tester
  • Become an IoT Developer
  • ASP.NET Course
  • VB.NET Course
  • PHP Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Software Development Course

Web development, programming languages, Software testing & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

Special Offer - C++ Training Course Learn More