Print Friendly and PDF
In selection sort

In each pass smallest/largest element is selected and placed in a sorted list.

Th entire array is divided into two parts: sorted and unsorted

In each pass, in the unsorted subarray, the smallest element is selected and exchanged with the first element.

Algorithm

1. Declare and initialize necessary variables such as array[], i, j, large, n etc.

2. for ( i = n - 1; i > 0; i--), repeat following steps

large = x[0];

index = 0;

2.1 for(j = i ; j <= i; j++)

if x[j] > large

large = x[i]

index = j

2.2 x[index] =x[i]

x[i] = large

3. Display the sorted array

Source Code:

#include<iostream>
using namespace std;
class SelectionSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit(int [], int);
void display();
};
void SelectionSort::getarray(){
cout<<"How many elements? ";
cin>>no_of_elements;
cout<<"Insert array of element to sort: ";
for(int i=0;i<no_of_elements;i++){
cin>>elements[i];
}

}

void SelectionSort::sortit(int x[], int n){
int i, indx, j, large;
for(i = n - 1; i > 0; i--){
large = x[0];
indx = 0;
for(j = 1; j <= i; j++){
if(x[j] > large){
large = x[j];
indx = j;

}

}
x[indx] = x[i];
x[i] = large;
}

}

void SelectionSort::display()
{
cout<<"The sorted array is :\n";
for(int i = 0 ; i < no_of_elements; i++)
{
cout<<elements[i]<<" ";
}
cout<<endl;
}
int main()
{
SelectionSort SS;
SS.getarray();
SS.sortit(SS.elements,SS.no_of_elements);
SS.display();
return 0;
}

Output:

How many elements? 6
Insert array of element to sort: 78 56 110 12 56 26
The sorted list is 12 26 56 56 78 110

Efficiency of Straight selection sort

In this first pass, it makes (n – 1) comparisons, in second pass it makes (n – 2) comparisons and so on, So total number of comparisons is n(n-1)/2 which is O(n^2)
zubairsaif

Zubair saif

A passionate writer who loves to write on new technology and programming

Post A Comment:

0 comments: