0
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);
}
Wiki User
∙ 10y ago
Wiki User
∙ 9y agoPlace 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);
}
Wiki User
∙ 10y ago#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;
}
Wiki User
∙ 10y agoPass 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;
}
}
Wiki User
∙ 11y ago#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 );
}
Wiki User
∙ 10y agoThe 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 );
}
}
Wiki User
∙ 9y agostd::array<int> A {5, 3, 2, 1, 4};
std::sort (arr.begin(), arr.end());
// arr = 1, 2, 3, 4, 5
Add your answer:
Earn +20 pts
How do you write a c plus plus program to sort a vector of strings using MSD radix sort?
The standard library sort algorithm automatically uses MSD radix to sort strings: std::vector<std::string> vs = {"a", "b", "c" "d", "ab"}; std::sort(vs.begin(), vs.end()); After sorting, the order will be: {"a", "ab", "b", "c", "d"}
Enumerate the types of selection constructs in c plus plus?
Selection constructs in C++if...elseswitch/caseconditional ternary operator (?:)
Lint is a compiler b a interactive debugger c a cinterpreter d a tool for analysing c plus plus program?
d a tool for analysing c plus plus program
Different types of sorting techniques in c language?
types of sorting in c language are: insertion sort selection sort bubble sort merge sort two way merge sort heap sort quick sort
Types of sort in c plus plus?
There's only one type of sort in C++; std::sort. If you want other types you'll need to write your own.
How do you write a c plus plus program to sort a vector of strings using MSD radix sort?
The standard library sort algorithm automatically uses MSD radix to sort strings: std::vector<std::string> vs = {"a", "b", "c" "d", "ab"}; std::sort(vs.begin(), vs.end()); After sorting, the order will be: {"a", "ab", "b", "c", "d"}
Can you program games with c plus plus?
Yes, you can program games with C++.
Enumerate the types of selection constructs in c plus plus?
Selection constructs in C++if...elseswitch/caseconditional ternary operator (?:)
What is the sort cut for running c plus plus program?
It depends on the particular IDE. Visual Studio uses <Ctrl>F5 to start a program in non-debug mode, and F5 to start a program in debug mode.
How to restart c plus plus program?
Exit the program and relaunch it.
Lint is a compiler b a interactive debugger c a cinterpreter d a tool for analysing c plus plus program?
d a tool for analysing c plus plus program
Different types of sorting techniques in c language?
types of sorting in c language are: insertion sort selection sort bubble sort merge sort two way merge sort heap sort quick sort
What are the three selection structures available in C plus plus?
if while switch
Types of sort in c plus plus?
There's only one type of sort in C++; std::sort. If you want other types you'll need to write your own.
How do you write a C plus plus program that will display the first 10 positive prime numbers?
By learning how to program on C+.
Where did C plus plus program come from?
C++ is an extension of C, and was invented by Bjarne Stroustrup.
Simple c program for selection sort?
The Selection Sort definition is rather simple : find the largest number (element) in a list and move it to it's position in sorted form.You can perform selection sort like, smallest elements are in the beginning and largest element at the end.Now how this element arrange to it's exact position,We can do this by swapping elements at highest index and the process is continue till all the elements are sorted.
