Przykład - sortowanie

Porządek Szarkowskiego


Oleksandr Mikołajewicz Szarkowski

Twierdzenie Szarkowskiego. (1964) Jeśli odwzorowanie ciągłe odcinka w siebie ma punkt okresowy o okresie k, a k poprzedza l w porządku Szarkowskiego, to odwzorowanie to ma też punkt okresowy o okresie l.

Rozwiązanie I : wskaźniki do funkcji

typedef bool (*LessThan)(int a1,int a2);
void bubbleSort(std::vector<int>& sequence,LessThan lt,int n){
  bool done=false;
  while(!done){
    done = true;
    for(int j=0;j<n-1;++j){
      if(lt(sequence[j+1],sequence[j])){
        swap(sequence[j],sequence[j+1]);
        done=false;
}}}}

Przykład: abstrakcyjne sortowanie poprzez wskaźniki do funkcji w C++

Wady rozwiązania stosującego wskaźniki do funkcji

Spirala Ulama

Stanisław Marcin Ulam (ur. 13 kwietnia 1909 we Lwowie, zm. 13 maja 1984 w Santa Fe)

Rozwiązanie II : polimorfizm dynamiczny

Przykład: abstrakcyjne sortowanie poprzez polimorfizm dynamiczny w C++

Wady rozwiązania stosującego polimorfizm dynamiczny

Rozwiązanie III : polimorfizm statyczny

Przykład: abstrakcyjne sortowanie poprzez polimorfizm statyczny w C++

Przykład: abstrakcyjne sortowanie poprzez polimorfizm statyczny w ConceptC++

Porównanie efektywności dla C++

Ilość Porządek Algorytm Func Dyn Stat
10 000 naturalny bubbleSort 1.34 1.02 0.40
10 000 Sharkovski bubbleSort 0.97 1.08 0.67
10 000 Ulam bubbleSort - 1.02 0.69

Przykład: abstrakcyjne sortowanie poprzez delegaty w C#

Przykład: abstrakcyjne sortowanie poprzez polimorfizm dynamiczny w C#

Brak możliwości wywoływania niedomyślnych konstruktorów dla typów parametrycznych zmusza nas do zastosowania obejścia poprzez wprowadzenie interfejsu IResetable, implementowania go w klasach definiujących porządek oraz wywoływania funkcji resetAs po każdym wywołaniu konstruktora domyślnego w implementacji generatora ciągów.

Przykład: abstrakcyjne sortowanie poprzez polimorfizm statyczny w C#

Przykład: abstrakcyjne sortowanie poprzez polimorfizm dynamiczny w Javie

Brak możliwości wywoływania konstruktorów dla typów parametrycznych w Javie uniemożliwia generyczne zrealizowanie generatorów ciągów dla różnych typów sortowanych.

Przykład: abstrakcyjne sortowanie poprzez polimorfizm statyczny w Javie

Porównanie efektywności dla C++, C# i Javy

Ilość Porządek Algorytm Język Func Dyn Stat
10 000 naturalny bubbleSort
C++ 1.34 1.02 0.41
C# 1.64 4.05 2.95
Java - 6.81 6.75
10 000 Sharkovski bubbleSort
C++ 0.97 1.08 0.67
C# 2.17 3.48 3.30
Java - 5.66 5.66
10 000 Ulam bubbleSort
C++ - 1.02 0.69
C# - 2.14 2.67
Java - 3.31 3.22