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()
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<<"The sorted array is :\n";
for(int i = 0 ; i < no_of_elements; i++)
{
cout<<elements[i]<<" ";
}
cout<<endl;
}
int main()
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)
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)
Post A Comment:
0 comments: