How do you write a program to arrange the elements in ascending order by using selection sort technique?

Answer 1

#include<iostream>

#include<vector>

template<class T>

void insertion_sort (std::vector<T>& v)

{

if (v.size()<2U)

return;

for (size_t index=1; index<v.size(); ++index)

{

T value = v[index];

size_t gap = index;

size_t prev = index-1;

while (gap && value<v[left] )

v[gap--]=v[left--];

v[gap] = value;

}

}

int main()

{

std::vector<int> vect {42, 1, 27, 8, 15, 4};

for (auto v : vect) std::cout << v << '\t';

std::cout << std::endl;

insertion_sort (vect);

for (auto v : vect) std::cout << v << '\t';

std::cout << std::endl;

}

Answer 2

#include<iostream>

#include<vector>

#include<functional> // for std::greater<T>

template<typename T, typename Compare=std::less<T::value_type>>

T partition (T begin, T end) {

using std::swap;

auto size {std::distance (begin, end)};

if (size<2) return begin;

auto mid {begin + size / 2};

auto last {begin + size - 1};

Compare cmp;

if (!cmp (*begin, *mid)) swap (*begin, *mid);

if (!cmp (*begin, *last)) swap (*begin, *last);

if (!cmp (*last, *mid)) swap (*last, *mid);

mid = last;

while (std::distance (begin, last)>0) {

while (std::distance (begin, last)>0 && cmp (*begin, *mid)) ++begin;

while (std::distance (begin, last)>0 && cmp (*mid, *last)) --last;

std::swap (*begin, *last);

}

std::swap (*last, *mid);

return begin;

}

template<typename T, typename Compare=std::less<T::value_type>>

void quicksort (T begin, T end) {

if (std::distance(begin, end)>1) {

T pivot = partition<T, Compare> (begin, end);

quicksort<T, Compare> (begin, pivot);

quicksort<T, Compare> (pivot+1, end);

}

}

template<typename T, typename Compare=std::less<T::value_type>>

void quicksort (T& v) {

quicksort<T::iterator, Compare> (v.begin(), v.end());

}

template<typename T>

std::ostream& operator<< (std::ostream& os, const std::vector<T>& vct){

os << "{";

for (auto val : vct) os << val << ", ";

os << "\b\b}"; // backspace over trailing comma

return os;

}

int main () {

using data_type = std::vector<int>;

data_type data {5, 6, 4, 7, 3, 8, 2, 9, 1};

std::cout << "Unsorted: " << data << std::endl;

quicksort<data_type> (data); // default sort uses std::less<int>

std::cout << " Ascend: " << data << std::endl;

quicksort<data_type, std::greater<data_type::value_type>> (data);

std::cout << " Descend: " << data << std::endl;

}

Answer 3

Selection sort works by locating the smallest value in an unsorted array and swapping it with the first value in the array. This then splits the array in two, with sorted items to the left and unsorted to the right. The process repeats for the unsorted portion of the array until there is only one element in the unsorted portion of the array, at which point the entire array is sorted.

The following code demonstrates an implementation of the selection sort algorithm in C/C++ using an array of integers.

#include <iostream>

#include <time.h>

using namespace std;

void SelectionSort(int a[], const int Elements )

{

int i, j, m, t;

// Minimum set is 2 elements.

if(Elements<2)

return;

// Loop through all array indices except the last.

for(i=0; i<Elements-1; ++i)

{

// Assume the current index holds the smallest value.

m=i;

// Search the remainder of the array for a smaller value (store the index).

for(j=i+1; j<Elements; ++j)

if( a[j]<a[m] )

m=j;

// No need to swap values at the same index.

if(m!=i)

{

// Swap values at index i and m.

t=a[i];

a[i]=a[m];

a[m]=t;

}

}

}

int main( void )

{

const int Elements = 20;

int A[Elements];

int i;

// Seed random numbers.

srand(( unsigned int ) time( NULL ));

// Create an array with 20 two-digit numbers (range: 10-99)

for(i=0; i<Elements; ++i )

A[i]=rand()%90+10;

// Print the unsorted array.

cout << "Unsorted:\t";

for(i=0; i<Elements; ++i )

cout << A[i] << " ";

cout << endl;

// Perform a selection sort.

SelectionSort( A, Elements );

// Print the sorted array.

cout << "Sorted:\t\t";

for(i=0; i<Elements; ++i )

cout << A[i] << " ";

cout << endl;

return(0);

}