Selection Sort Program in c and c plus plus?

Answer 1

The following code demonstrates the implementations for bubble sort, insertion sort and selection sort, in C++.

#include<iostream>

#include<time.h>

#include<iomanip>

#include<string>

void swap(int& x, int& y)

{

x^=y^=x^=y;

}

void bubble_sort(int* A, int size)

{

while(size)

{

int n=0;

for(int i=1; i<size; ++i)

{

if(A[i-1]>A[i])

{

swap(A[i-1], A[i]);

n=i;

}

}

size=n;

}

}

void insertion_sort(int* A, int size)

{

for(int i=1; i<size; ++i)

{

int value=A[i];

int hole=i;

while( hole && value<A[hole-1] )

{

A[hole]=A[hole-1];

--hole;

}

A[hole]=value;

}

}

void selection_sort(int* A, int size)

{

for(int i=0; i<size-1; ++i)

{

int j=i;

for(int k=i+1; k<size; ++k)

if(A[k]<A[j])

j=k;

if( i!=j )

swap(A[i],A[j]);

}

}

void sort(int* A, int size, int sort_type)

{

switch(sort_type)

{

case(0): bubble_sort( A, size );

case(1): insertion_sort( A, size );

case(2): selection_sort( A, size );

}

}

int* copy_array(int* A, int size)

{

int* copy=new int[size];

memcpy(copy, A, size*sizeof(int));

return(copy);

}

void print_array(int* A, int size, char* prompt)

{

std::cout<<prompt<<"\t";

for(int i=0; i<size; ++i)

std::cout<<std::setw(2)<<A[i]<<" ";

std::cout<<std::endl;

}

int get_rand(int range_min=0, int range_max=RAND_MAX)

{

return((int) ((double)rand() / (RAND_MAX + 1) * ((range_max + 1) - range_min) + range_min));

}

int input_char(std::string prompt, std::string input)

{

char ch;

do

{

std::cout<<prompt<<": ";

std::cin>>ch;

}

while(input.find(ch)==std::string::npos);

return(input.find(ch)%(input.size()/2));

}

int main()

{

srand((unsigned) time(NULL));

int size = get_rand( 10, 80);

if( int* A = new int[size] )

{

for( int i=0; i<size; ++i )

A[i]=get_rand( 1, size );

int choice=input_char("Please select a sorting method:\n[B]ubble, [I]nsert, [S]election", "bisBIS");

std::cout<<"You chose ";

switch(choice)

{

case(0): std::cout<<"bubble"; break;

case(1): std::cout<<"insertion"; break;

case(2): std::cout<<"selection"; break;

}

std::cout<<" sort...\n"<<std::endl;

print_array( A, size, "Before sorting" );

sort(A, size, choice);

print_array( A, size, "After sorting" );

delete [] A;

}

return(0);

}

Answer 2

Place the numbers in a linear sequence container such as a std::tr1::array or a std::vector. Use an array if the element count is a fixed size (static array) or a vector if the element count is variable (dynamic array). Then use std::sort to sort the sequence. The following program demonstrates both methods.

#include<iostream>

#include<array>

#include<vector>

#include<algorithm> // for std::sort()

template<typename T, const unsigned S>

void print (std::tr1::array<T, S>& arr)

{

for (std::tr1::array<T, S>::iterator it=arr.begin(); it!=arr.end(); ++it)

std::cout << *it << '\t';

std::cout << std::endl;

}

template<typename T>

void print (std::vector<T>& arr)

{

for (std::vector<T>::iterator it=arr.begin(); it!=arr.end(); ++it)

std::cout << *it << '\t';

std::cout << std::endl;

}

template<typename T, const unsigned S>

void sort (std::tr1::array<T, S>& a)

{

std::sort (a.begin(), a.end());

}

template<typename T>

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

{

std::sort (v.begin(), v.end());

}

int main()

{

// fixed size array

std::tr1::array<unsigned, 9> arr = { 9, 6, 4, 2, 7, 1, 3, 5, 8 };

// variable-length array (copy arr)

std::vector<unsigned> vect (arr.begin(), arr.end());

vect.push_back (0); // add another value

std::cout << "Unsorted array:\t\t"; print (arr);

sort (arr);

std::cout << "Sorted array:\t\t"; print (arr);

std::cout << "Unsorted vector:\t"; print (vect);

sort (vect);

std::cout << "Sorted vector:\t\t"; print (vect);

}

Answer 3

#include<iostream>

#include<time.h>

template<class T>

void exch( T& x, T& y )

{

T tmp=x;

x=y;

y=tmp;

}

// Generates a pseudo-random number in the range min to max (inclusive).

int get_rand( const int range_min=0, const int range_max=RAND_MAX )

{

static bool seeded = true; // set to false to ensure randomness.

if( !seeded )

{

seeded = !seeded;

std::srand((unsigned) time(NULL));

while( get_rand() );

}

return((int)((double)std::rand() / (RAND_MAX+1) * ((range_max+1) - range_min) + range_min));

}

template<class T>

void quicksort( T a[], int l, int r )

{

int i;

static int j;

tail_call:

if(r<=l)

return;

// Select random pivot and move it to end of array.

exch( a[get_rand(l,r)], a[r] );

i = l-1;

j = r;

while(1)

{

// Locate the 1st value from left that is not less than the pivot.

while(a[++i]<a[r]);

// Locate the 1st value from right

while(a[r]<a[--j])

if(j==l)

break;

if(i>=j)

break;

exch(a[i], a[j]);

}

exch( a[i], a[r] );

// Determine the smaller subset

static int l1, l2;

l1=l, l2=i-1;

int r1=i+1, r2=r;

if(r2-r1<l2-l1)

{

l1=r1, l2=r2;

r1=l, r2=i-1;

}

// Recurse over smaller subset

quicksort( a, l1, l2);

// Tail-call over largest subset

l=r1, r=r2;

goto tail_call;

}

template<class T>

void quicksort( T a[], const size_t size )

{

if( size < 2 )

return;

quicksort( a, 0, size-1 );

}

int main()

{

int a[9]={9,7,8,5,6,3,4,1,2};

std::cout<<"Before sorting:"<<std::endl;

for(size_t i=0; i<9; ++i)

std::cout<<a[i]<<std::endl;

quicksort(a, 9);

std::cout<<"After sorting:"<<std::endl;

for(size_t i=0; i<9; ++i)

std::cout<<a[i]<<std::endl;

}

Answer 4

Pass your array to the following function:

template<class T>

void bubble_sort( T A[], size_t size )

{

size_t last_exch, left, right;

while( size )

{

for( left=0, right=1, last_exch=left; right<size; ++left, ++right)

if( A[right]<A[left] )

{

T tmp = A[left];

A[left]=A[right];

A[right]=tmp;

last_exch=right;

}

size = last_exch;

}

}

Answer 5

#include <iostream>

#include <time.h>

void quicksort( int * subarray, int size)

{

int pivot=0, lower=0, upper=0, temp=0;

tail_call: // Used to minimise recursive calls.

if( size > 1 )

{

// Select a pivot value at random.

pivot = subarray[rand()%size];

lower=0;

upper=size-1;

while( lower<upper )

{

while( lower<size && subarray[lower]<pivot )

++lower;

while( upper && subarray[upper]>pivot)

--upper;

if( lower<upper )

{

// Bug-fix to cater for duplicate values:

if( subarray[lower]==subarray[upper] )

if( upper )

--upper;

else

++lower;

else

{

// Swap values:

temp=subarray[lower];

subarray[lower]=subarray[upper];

subarray[upper]=temp;

}

}

}

// Tail call optimiser begins here:

// Determine the size of the upper partition.

upper=size-lower-1;

// Is the lower partion smaller than upper partition?

if( lower<upper )

{

// Quicksort the lower partition with recursion if 2 or more elements.

if( lower > 1 )

quicksort(subarray, lower );

// Update both parameters for the tail call.

subarray = &(subarray[lower+1]);

size = upper;

}

else // The upper partition is smaller than lower partition.

{

// Quicksort the upper partition with recursion if 2 or more elements.

if( upper > 1)

quicksort(&(subarray[lower+1]), upper );

// Update the size parameter for the tail call.

size = lower;

}

// Sort the larger partition with a tail call rather than recursion.

goto tail_call;

// Without tail call optimisation, you would need to make the following

// recursive calls instead, which isn't as efficient:

//quicksort(subarray, lower );

//quicksort(&(subarray[lower+1]),size-lower-1);

}

}

int main()

{

// Seed random number generator.

srand(( unsigned ) time( NULL ));

// Create up to 1000 elements (minimum of 10).

int i = 0, elements = rand()%991+10;

int * Array = new int[ elements ];

// Generate random values for each element and print.

printf( "%d randomly generated elements:\n", elements );

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

{

Array[i] = rand()%elements+1;

printf( "%.3d%s", Array[i], i<elements-1 ? ", " : "." );

}

printf( "\n\n" );

quicksort( Array, elements );

// Print the sorted elements.

printf( "Sorted:\n" );

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

printf( "%.3d%s", Array[i], i<elements-1 ? ", " : "." );

printf( "\n\n" );

// Debug: check for errors...

for( i=1; i<elements; ++i )

if( Array[i-1] > Array[i] )

printf( "Error in element [%d] (%d > %d)\n", i, Array[i-1], Array[i] );

// Tidy up.

delete [] Array;

return( 0 );

}

Answer 6

The following demonstrates the functions required by the Williams heap algorithm. Although Floyd's heap algorithm is faster in theory, in practice that is not the case at all. This is largely due to modern CPU optimisations which work much better with Williams' algorithm. In my tests, Floyd's algorithm is only marginally quicker than the generic heap sort, while Williams is around 33% quicker.

Together, these template functions will sort an array of any type and size. Simply call the primary function, void williams_heap_sort(T a[], size_t size ), passing the array name and its size.

template<typename T>

void williams_bubbleup(T a[], size_t child)

{

// Bubble up the given child's value to its correct position

// in the heap, demoting its parent as we go.

T value=a[child];

size_t parent=child-1;

parent>>=1;

while( child )

{

if( a[parent]<value )

{

a[child]=a[parent];

child=parent;

--parent;

parent>>=1;

}

else

break;

}

a[child]=value;

}

template<typename T>

void williams_siftdown(T a[], const size_t size, const T value)

{

// Starting from the root parent, sift down the parent value

// to its correct position in the heap, promoting children

// to p[arents as we go. Note: size is n-1 upon entry.

size_t parent=0;

size_t child=2;

while( child<size )

{

if( a[child]<a[child-1] )

--child;

if( value<a[child] )

{

a[parent]=a[child];

parent=child;

++child;

child<<=1;

}

else

break;

}

size_t prev=size-1;

if( child==size && value<a[prev] )

{

a[parent]=a[prev];

parent=prev;

}

a[parent]=value;

}

template<typename T>

void williams_make_heap(T a[], const size_t size)

{

for( size_t vacant=1; vacant<size; ++vacant )

williams_bubbleup( a, vacant );

}

template<typename T>

void williams_heap_sort(T a[], size_t size )

{

if( size < 2 )

return;

williams_make_heap( a, size );

while( --size )

{

T missing=a[size];

a[size]=a[0];

williams_siftdown( a, size, missing );

}

}

Answer 7

std::array<int> A {5, 3, 2, 1, 4};

std::sort (arr.begin(), arr.end());

// arr = 1, 2, 3, 4, 5