C++ Tutorial/Development/Sort — различия между версиями

Текущая версия на 10:29, 25 мая 2010

Содержание

1 A Bubble sort
2 A recursive version of Quicksort for sorting characters
3 how to declare your own function and function pointer to be used with qsort( )
4 Quick Sort
5 Selection Sort
6 Sort Tracer

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)

C++ Tutorial/Development/Sort — различия между версиями

Текущая версия на 10:29, 25 мая 2010

Содержание

A Bubble sort

A recursive version of Quicksort for sorting characters

how to declare your own function and function pointer to be used with qsort( )

Quick Sort

Selection Sort

Sort Tracer

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

С

С++

Навигация

Инструменты

Версия 14:21, 25 мая 2010 (просмотреть исходный код) (обсуждение) ← Предыдущая правка	Текущая версия на 10:29, 25 мая 2010 (просмотреть исходный код) Admin (обсуждение \| вклад) м (1 версия: Импорт контента...)
(нет различий)