C++ Tutorial/Development/Sort
Версия от 14:21, 25 мая 2010; (обсуждение)
Содержание
A Bubble sort
#include <iostream>
#include <cstdlib>
using namespace std;
int main()
{
int nums[10];
int a, b, t;
int size;
size = 10; // number of elements to sort
for(t=0; t<size; t++)
nums[t] = rand();
cout << "Original array is:\n ";
for(t=0; t<size; t++)
cout << nums[t] << " ";
cout << "\n";
// This is the bubble sort.
for(a=1; a<size; a++)
for(b=size-1; b>=a; b--) {
if(nums[b-1] > nums[b]) { // if out of order
// exchange elements
t = nums[b-1];
nums[b-1] = nums[b];
nums[b] = t;
}
}
cout << "\nSorted array is:\n ";
for(t=0; t<size; t++)
cout << nums[t] << " ";
return 0;
}Original array is: 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 Sorted array is: 41 6334 11478 15724 18467 19169 24464 26500 26962 29358
A recursive version of Quicksort for sorting characters
#include <iostream>
#include <cstring>
using namespace std;
void quicksort(char *items, int len);
void qs(char *items, int left, int right);
int main() {
char str[] = "fdsawertgsvbnhgfdertygfd";
cout << "Original order: " << str << "\n";
quicksort(str, strlen(str));
cout << "Sorted order: " << str << "\n";
return 0;
}
void quicksort(char *items, int len)
{
qs(items, 0, len-1);
}
void qs(char *items, int left, int right)
{
int i, j;
char x, y;
i = left; j = right;
x = items[( left+right) / 2 ];
do {
while((items[i] < x) && (i < right))
i++;
while((x < items[j]) && (j > left))
j--;
if(i <= j) {
y = items[i];
items[i] = items[j];
items[j] = y;
i++; j--;
}
} while(i <= j);
if(left < j)
qs(items, left, j);
if(i < right)
qs(items, i, right);
}Original order: fdsawertgsvbnhgfdertygfd Sorted order: abdddeefffggghnrrssttvwy
how to declare your own function and function pointer to be used with qsort( )
#include <iostream>
#include <stdlib.h>
using namespace std;
#define IMAXVALUES 10
int icompare_funct(const void *iresult_a, const void *iresult_b);
int (*ifunct_ptr)(const void *,const void *);
int main( )
{
int i;
int iarray[IMAXVALUES]={0,5,3,2,8,7,9,1,4,6};
ifunct_ptr=icompare_funct;
qsort(iarray,IMAXVALUES,sizeof(int),ifunct_ptr);
for(i = 0; i < IMAXVALUES; i++)
cout <<"[{||}]" << iarray[i];
}
int icompare_funct(const void *iresult_a, const void *iresult_b)
{
return((*(int *)iresult_a) - (*(int *)iresult_b));
}Quick Sort
#include <iostream>
using namespace std;
int *swapnumbers(int rawdata[], int lower, int upper);
int *quicksort(int rawdata[], int first, int last);
int main()
{
int unsorted[10],i;
int *sorted;
unsorted[0] = 9;
unsorted[1] = 8;
unsorted[2] = 7;
unsorted[3] = 7;
unsorted[4] = 6;
unsorted[5] = 5;
unsorted[6] = 5;
unsorted[7] = 4;
unsorted[8] = 4;
unsorted[9] = 2;
sorted = quicksort(unsorted, 0, 10);
cout << "This is your array sorted:"<< endl;
for(i = 0; i < 10; i++)
{
cout << sorted[i] << endl;
}
return 0;
}
int *quicksort(int rawdata[], int first, int last)
{
int lower = first+1, upper = last;
int bound;
rawdata = swapnumbers(rawdata, first, (first+last)/2);
bound = rawdata[first];
while(lower <= upper)
{
while(rawdata[lower] < bound)
lower++;
while(bound < rawdata[upper])
upper--;
if(lower < upper)
{
rawdata = swapnumbers(rawdata, lower++, upper--);
}
else
{
lower++;
}
}
rawdata = swapnumbers(rawdata, upper, first);
if(first < upper-1)
{
rawdata = quicksort(rawdata, first, upper-1);
}
if(upper+1 < last)
{
rawdata = quicksort(rawdata, upper+1, last);
}
return(rawdata);
}
int *swapnumbers(int rawdata[], int lower, int upper)
{
int temp;
temp = rawdata[lower];
rawdata[lower] = rawdata[upper];
rawdata[upper] = temp;
return(rawdata);
}This is your array sorted: 0 2 4 4 5 5 6 7 7 8
Selection Sort
#include <iostream>
using std::cout;
using std::endl;
#include <iomanip>
using std::setw;
void selectionSort( int * const, const int );
void swap( int * const, int * const );
int main()
{
const int arraySize = 10;
int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 9, 1, 5, 7 };
selectionSort( a, arraySize );
for ( int j = 0; j < arraySize; j++ )
cout << a[ j ];
return 0;
}
void selectionSort( int * const array, const int size )
{
int smallest;
for ( int i = 0; i < size - 1; i++ )
{
smallest = i;
for ( int index = i + 1; index < size; index++ )
if ( array[ index ] < array[ smallest ] )
smallest = index;
swap( &array[ i ], &array[ smallest ] );
}
}
void swap( int * const element1Ptr, int * const element2Ptr )
{
int hold = *element1Ptr;
*element1Ptr = *element2Ptr;
*element2Ptr = hold;
}124567891012
Sort Tracer
/* The following code example is taken from the book
* "C++ Templates - The Complete Guide"
* by David Vandevoorde and Nicolai M. Josuttis, Addison-Wesley, 2002
*
* (C) Copyright David Vandevoorde and Nicolai M. Josuttis 2002.
* Permission to copy, use, modify, sell and distribute this software
* is granted provided this copyright notice appears in all copies.
* This software is provided "as is" without express or implied
* warranty, and with no claim as to its suitability for any purpose.
*/
#include <iostream>
#include <algorithm>
#include <iostream>
class SortTracer {
private:
int value; // integer value to be sorted
int generation; // generation of this tracer
static long n_created; // number of constructor calls
static long n_destroyed; // number of destructor calls
static long n_assigned; // number of assignments
static long n_compared; // number of comparisons
static long n_max_live; // maximum of existing objects
// recompute maximum of existing objects
static void update_max_live() {
if (n_created-n_destroyed > n_max_live) {
n_max_live = n_created-n_destroyed;
}
}
public:
static long creations() {
return n_created;
}
static long destructions() {
return n_destroyed;
}
static long assignments() {
return n_assigned;
}
static long comparisons() {
return n_compared;
}
static long max_live() {
return n_max_live;
}
public:
// constructor
SortTracer (int v = 0) : value(v), generation(1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", created generation " << generation
<< " (total: " << n_created - n_destroyed
<< ")\n";
}
// copy constructor
SortTracer (SortTracer const& b)
: value(b.value), generation(b.generation+1) {
++n_created;
update_max_live();
std::cerr << "SortTracer #" << n_created
<< ", copied as generation " << generation
<< " (total: " << n_created - n_destroyed
<< ")\n";
}
// destructor
~SortTracer() {
++n_destroyed;
update_max_live();
std::cerr << "SortTracer generation " << generation
<< " destroyed (total: "
<< n_created - n_destroyed << ")\n";
}
// assignment
SortTracer& operator= (SortTracer const& b) {
++n_assigned;
std::cerr << "SortTracer assignment #" << n_assigned
<< " (generation " << generation
<< " = " << b.generation
<< ")\n";
value = b.value;
return *this;
}
// comparison
friend bool operator < (SortTracer const& a,
SortTracer const& b) {
++n_compared;
std::cerr << "SortTracer comparison #" << n_compared
<< " (generation " << a.generation
<< " < " << b.generation
<< ")\n";
return a.value < b.value;
}
int val() const {
return value;
}
};
long SortTracer::n_created = 0;
long SortTracer::n_destroyed = 0;
long SortTracer::n_max_live = 0;
long SortTracer::n_assigned = 0;
long SortTracer::n_compared = 0;
int main()
{
// prepare sample input:
SortTracer input[] = { 7, 3, 5, 6, 4, 2, 0, 1, 9, 8 };
// print initial values:
for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << " ";
}
std::cerr << std::endl;
// remember initial conditions:
long created_at_start = SortTracer::creations();
long max_live_at_start = SortTracer::max_live();
long assigned_at_start = SortTracer::assignments();
long compared_at_start = SortTracer::comparisons();
// execute algorithm:
std::cerr << "---[ Start std::sort() ]--------------------\n";
std::sort<>(&input[0], &input[9]+1);
std::cerr << "---[ End std::sort() ]----------------------\n";
// verify result:
for (int i=0; i<10; ++i) {
std::cerr << input[i].val() << " ";
}
std::cerr << "\n\n";
// final report:
std::cerr << "std::sort() of 10 SortTracer"s"
<< " was performed by:\n "
<< SortTracer::creations() - created_at_start
<< " temporary tracers\n "
<< "up to "
<< SortTracer::max_live()
<< " tracers at the same time ("
<< max_live_at_start << " before)\n "
<< SortTracer::assignments() - assigned_at_start
<< " assignments\n "
<< SortTracer::comparisons() - compared_at_start
<< " comparisons\n\n";
}SortTracer #1, created generation 1 (total: 1) SortTracer #2, created generation 1 (total: 2) SortTracer #3, created generation 1 (total: 3) SortTracer #4, created generation 1 (total: 4) SortTracer #5, created generation 1 (total: 5) SortTracer #6, created generation 1 (total: 6) SortTracer #7, created generation 1 (total: 7) SortTracer #8, created generation 1 (total: 8) SortTracer #9, created generation 1 (total: 9) SortTracer #10, created generation 1 (total: 10) 7 3 5 6 4 2 0 1 9 8 ---[ Start std::sort() ]-------------------- SortTracer #11, copied as generation 2 (total: 11) SortTracer comparison #1 (generation 2 < 1) SortTracer assignment #1 (generation 1 = 1) SortTracer assignment #2 (generation 1 = 2) SortTracer generation 2 destroyed (total: 10) SortTracer #12, copied as generation 2 (total: 11) SortTracer comparison #2 (generation 2 < 1) SortTracer #13, copied as generation 3 (total: 12) SortTracer comparison #3 (generation 3 < 1) SortTracer assignment #3 (generation 1 = 1) SortTracer comparison #4 (generation 3 < 1) SortTracer assignment #4 (generation 1 = 3) SortTracer generation 3 destroyed (total: 11) SortTracer generation 2 destroyed (total: 10) SortTracer #14, copied as generation 2 (total: 11) SortTracer comparison #5 (generation 2 < 1) SortTracer #15, copied as generation 3 (total: 12) SortTracer comparison #6 (generation 3 < 1) SortTracer assignment #5 (generation 1 = 1) SortTracer comparison #7 (generation 3 < 1) SortTracer assignment #6 (generation 1 = 3) SortTracer generation 3 destroyed (total: 11) SortTracer generation 2 destroyed (total: 10) SortTracer #16, copied as generation 2 (total: 11) SortTracer comparison #8 (generation 2 < 1) SortTracer #17, copied as generation 3 (total: 12) SortTracer comparison #9 (generation 3 < 1) SortTracer assignment #7 (generation 1 = 1) SortTracer comparison #10 (generation 3 < 1) SortTracer assignment #8 (generation 1 = 1) SortTracer comparison #11 (generation 3 < 1) SortTracer assignment #9 (generation 1 = 1) SortTracer comparison #12 (generation 3 < 1) SortTracer assignment #10 (generation 1 = 3) SortTracer generation 3 destroyed (total: 11) SortTracer generation 2 destroyed (total: 10) SortTracer #18, copied as generation 2 (total: 11) SortTracer comparison #13 (generation 2 < 1) SortTracer assignment #11 (generation 1 = 1) SortTracer assignment #12 (generation 1 = 1) SortTracer assignment #13 (generation 1 = 1) SortTracer assignment #14 (generation 1 = 1) SortTracer assignment #15 (generation 1 = 1) SortTracer assignment #16 (generation 1 = 2) SortTracer generation 2 destroyed (total: 10) SortTracer #19, copied as generation 2 (total: 11) SortTracer comparison #14 (generation 2 < 1) SortTracer assignment #17 (generation 1 = 1) SortTracer assignment #18 (generation 1 = 1) SortTracer assignment #19 (generation 1 = 1) SortTracer assignment #20 (generation 1 = 1) SortTracer assignment #21 (generation 1 = 1) SortTracer assignment #22 (generation 1 = 1) SortTracer assignment #23 (generation 1 = 2) SortTracer generation 2 destroyed (total: 10) SortTracer #20, copied as generation 2 (total: 11) SortTracer comparison #15 (generation 2 < 1) SortTracer #21, copied as generation 3 (total: 12) SortTracer comparison #16 (generation 3 < 1) SortTracer assignment #24 (generation 1 = 1) SortTracer comparison #17 (generation 3 < 1) SortTracer assignment #25 (generation 1 = 1) SortTracer comparison #18 (generation 3 < 1) SortTracer assignment #26 (generation 1 = 1) SortTracer comparison #19 (generation 3 < 1) SortTracer assignment #27 (generation 1 = 1) SortTracer comparison #20 (generation 3 < 1) SortTracer assignment #28 (generation 1 = 1) SortTracer comparison #21 (generation 3 < 1) SortTracer assignment #29 (generation 1 = 1) SortTracer comparison #22 (generation 3 < 1) SortTracer assignment #30 (generation 1 = 3) SortTracer generation 3 destroyed (total: 11) SortTracer generation 2 destroyed (total: 10) SortTracer #22, copied as generation 2 (total: 11) SortTracer comparison #23 (generation 2 < 1) SortTracer #23, copied as generation 3 (total: 12) SortTracer comparison #24 (generation 3 < 1) SortTracer assignment #31 (generation 1 = 3) SortTracer generation 3 destroyed (total: 11) SortTracer generation 2 destroyed (total: 10) SortTracer #24, copied as generation 2 (total: 11) SortTracer comparison #25 (generation 2 < 1) SortTracer #25, copied as generation 3 (total: 12) SortTracer comparison #26 (generation 3 < 1) SortTracer assignment #32 (generation 1 = 1) SortTracer comparison #27 (generation 3 < 1) SortTracer assignment #33 (generation 1 = 3) SortTracer generation 3 destroyed (total: 11) SortTracer generation 2 destroyed (total: 10) ---[ End std::sort() ]---------------------- 0 1 2 3 4 5 6 7 8 9 std::sort() of 10 SortTracer"s was performed by: 15 temporary tracers up to 12 tracers at the same time (10 before) 33 assignments 27 comparisons SortTracer generation 1 destroyed (total: 9) SortTracer generation 1 destroyed (total: 8) SortTracer generation 1 destroyed (total: 7) SortTracer generation 1 destroyed (total: 6) SortTracer generation 1 destroyed (total: 5) SortTracer generation 1 destroyed (total: 4) SortTracer generation 1 destroyed (total: 3) SortTracer generation 1 destroyed (total: 2) SortTracer generation 1 destroyed (total: 1) SortTracer generation 1 destroyed (total: 0)
