Data Structure: How to implement Straight Selection Sort in C++?

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)

دراسات تقنية

Data Structure: How to implement Straight Selection Sort in C++?

إرسال تعليق

Data Structure: How to implement Straight Selection Sort in C++?

آخر المشاركات

تعليقات: 0

إرسال تعليق