OBOWIĄZKOWE DO PRZESŁANIA: Implementacja dwóch algorytmów sortowania w C++, w tym co najmniej jednego zaawansowanego. Funkcje sortujące muszą być szablonami, muszą mieć podany interfejs tablicowy lub z iteratorami, wystarczy użyć standardowego porównywania (operator<). W programie należy sprawdzić, czy sortowanie się udało, najlepiej wykorzystać funkcję std::is_sorted().
Ogólne zalecenia do przesyłanych programów.
(1) Katalog z programem powinien zawierać Makefile i pliki źródłowe.
(2) Program powinien kompilować się poleceniem make.
(3) Nie używać deklaracji using namespace std;.
(4) Zalecane są testy automatyczne z assert().
Sortowaniem nazywamy proces ustawiania zbioru obiektów w określonym porządku [Wirth]. Sortowanie stosuje się w celu ułatwienia późniejszego wyszukiwania elementów sortowanego zbioru.
SPECYFIKACJA Problem sortowania [Cormen]. DANE WEJŚCIOWE Ciąg n liczb (a_1, a_2, ..., a_n). DANE WYJŚCIOWE Permutacja (zmiana kolejności) (a_1', a_2', ..., a_n') ciągu wejściowego taka, że a_1' ≤ a_2' ≤ ... ≤ a_n'.
Sortowanie wewnętrzne (tablice) i zewnętrzne (pliki).
Sortowanie adaptacyjne i nieadaptacyjne.
Sortowanie stabilne i niestabilne.
Przykład sortowania par liczb całkowitych względem pierwszej wartości. (4, 1) (3, 7) (3, 1) (5, 6) - oryginalna kolejność (3, 7) (3, 1) (4, 1) (5, 6) - kolejność zachowana (stabilność) (3, 1) (3, 7) (4, 1) (5, 6) - kolejność zmieniona (brak stabilności)
Sortowanie bazujące na porównaniach kluczy.
Algorytmy proste z czasem O(n^2).
Sortowanie przez wybór (selectsort).
Sortowanie przez wstawianie (insertsort), pamięć O(1).
Sortowanie przez zamianę (bubblesort), stabilne.
Sortowanie przez wstrząsanie (shakersort).
Algorytmy zaawansowane z czasem O(n*log(n)).
Sortowanie Shella (shellsort), niestabilne.
Sortowanie szybkie (quicksort), pesymistycznie O(n^2), niestabilne.
Sortowanie przez scalanie (mergesort), stabilne.
Sortowanie przez kopcowanie, sortowanie stogowe (heapsort), niestabilne.
Sortowanie bez porównywania kluczy.
Sortowanie przez zliczanie (countsort), czas O(n+k).
Sortowanie bukietowe (bucketsort), czas O(n), pamięć O(k).
Sortowanie pozycyjne (radixsort) - czas O(d*(n+k)), pamięć O(n+k),
k liczba różnych cyfr, d liczba cyfr w kluczach.
# L to lista elementów, które można porównywać. # Liczby są sortowane normalnie. # Napisy są sortowane leksykograficznie. L.sort() # sortowanie stabilne algorytmem timsort (Py2.3-Py3.10) lub powersort (Py3.11+) L.sort(key=len) # sortowanie napisów pod względem długości L.sort(cmp=cmpfunc) # Python 2, przekazanie funkcji porównującej
https://en.wikipedia.org/wiki/Introsort
Introsort or introspective sort
is a hybrid sorting algorithm that provides both fast average performance
and (asymptotically) optimal worst-case performance.
Introsort was invented by David Musser in 1997.
#include <cstdlib> // qsort()
void qsort( void *ptr, size_t count, size_t size,
int (*comp)(const void *, const void *) );
// Sortowanie tablicy ptr w porządku niemalejącym.
// Funkcja porównująca zwraca -1/0/+1.
// Funkcja porównująca nie może modyfikować porównywanych elementów.
// count - liczba elementów tablicy
// size - rozmiar jednego elementu w bajtach
int cmp_int(const void *a, const void *b) {
int arg1 = *(const int *)a;
int arg2 = *(const int *)b;
if (arg1 < arg2) return -1;
else if (arg1 > arg2) return 1;
else return 0;
}
int v[] = { 9,4,7,3,6,8,2,1,5,0 };
qsort(v, sizeof(v) / sizeof(*v), sizeof(*v), cmp_int);
// https://en.cppreference.com/w/cpp/algorithm/sort
#include <algorithm> // std::sort(), std::stable_sort()
#include <vector>
#include <array>
template< class RandomIt >
void sort( RandomIt first, RandomIt last );
// Sorts the elements in the range [first, last) in non-descending order.
// The order of equal elements is not guaranteed to be preserved.
// Elements are compared using operator< (until C++20) or std::less{} (since C++20).
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );
// Elements are sorted with respect to comp.
// bool cmp(const Type1 & a, const Type2 & b);
// Funkcja zwraca true jeżeli a jest mniejsze od b.
// Complexity
// O(N*log(N)), where N = std::distance(first, last) comparisons on average. (until C++11)
// O(N*log(N)), where N = std::distance(first, last) comparisons. (since C++11)
// Dla std::stable_sort() analogicznie.
// The order of equivalent elements is guaranteed to be preserved.
// Complexity
// O(N*log(N)^2), where N = std::distance(first, last) applications of cmp.
// If additional memory is available, then the complexity is O(N*log(N)).
// Notes
// This function attempts to allocate a temporary buffer equal in size
// to the sequence to be sorted.
// If the allocation fails, the less efficient algorithm is chosen.
std::vector<int> v = { 9,4,7,3,6,8,2,1,5,0 };
//std::array<int, 10> v{ { 9,4,7,3,6,8,2,1,5,0 } }; // bez znaku '=' mamy {{}}
std::array<int, 10> v = { 9,4,7,3,6,8,2,1,5,0 };
int v[] = { 9,4,7,3,6,8,2,1,5,0 }; // zwykła tablica
std::sort(v.begin(), v.end()); // vector, array
std::sort(std::begin(v), std::end(v)); // zwykła tablica, vector, array
std::sort(v.data(), v.data() + v.size()); // array
std::sort(v, v + (sizeof(v) / sizeof(*v))); // zwykła tablica
// Szablon przykładowej funkcji sortującej. // Funkcja sortuje elementy w zakresie od ptr[left] do ptr[right] włącznie. template<typename T> void anysort(T *ptr, int left, int right); // Elements are compared using bool operator<(const T & lhs, const T & rhs);
// Szablon przykładowej funkcji sortującej. template<typename Iterator> void anysort(Iterator first, Iterator last); template<typename Iterator, typename Compare> void anysort(Iterator first, Iterator last, Compare comp);
// https://en.cppreference.com/w/cpp/algorithm/is_sorted // Sprawdzenie poprawności sortowania liczb całkowitych. #include <cassert> // Wykorzystanie funkcji z STL. assert( std::is_sorted(v.begin(), v.end()) ); // vector, array assert( std::is_sorted(std::begin(v), std::end(v)) ); // zwykła tablica assert( std::is_sorted(v, v + (sizeof(v) / sizeof(*v))) ); // zwykła tablica assert( std::is_sorted(v.data(), v.data() + v.size()) ); // array
Przykładowy plik Makefile wspomagający kompilację
i sposób korzystania z narzędzia make.
UWAGA Wcięcia w pliku Makefile robimy klawiszem tabulacji,
to nie jest ciąg spacji!
$ ls # zawartość katalogu z projektem atrapa.cpp atrapa.h main.cpp Makefile # Zależności między plikami: # atrapa.cpp zawiera #include "atrapa.h" # main.cpp zawiera #include "atrapa.h" $ make # kompilacja g++ -Wall -std=c++11 -c main.cpp -o main.o g++ -Wall -std=c++11 -c atrapa.cpp -o atrapa.o g++ -Wall -std=c++11 main.o atrapa.o -o main.out $ make clean # czyszczenie po kompilacji rm -f main.out *.o core
# Makefile # Kompilator g++. CXX = g++ # Możliwe dodatkowe zmienne. # LIBS = -ll -lm LIBS = # Flagi dla kompilatora C++. # Standardy: -std=c++11 -std=c++14 -std=c++17 -std=c++20 -std=c++23 -std=c++26 CXXFLAGS = -Wall -std=c++11 # Pliki obiektowe - powstają z plików *.cpp. OBJECTS = main.o atrapa.o # Pliki nagłówkowe - są włączane do plików *.cpp. HFILES = atrapa.h # Końcowy plik wykonywalny. TARGET = main.out # Definicja domyślnej reguły wzorcowej. # $< oznacza nazwę pliku pierwszej zależności reguły. # $@ oznacza nazwę pliku celu w regule. # Wszystkie pliki obiektowe zależą od wszystkich plików nagłówkowych. # Wcięcia robimy przez TAB. %.o : %.cpp $(HFILES) Makefile $(CXX) $(CXXFLAGS) -c $< -o $@ # Na końcu wstawiamy $(LIBS), aby nie było problemów z linkowaniem. $(TARGET) : $(OBJECTS) $(CXX) $(CXXFLAGS) $(OBJECTS) -o $(TARGET) $(LIBS) # Określenie celów sztucznych. .PHONY : clean clean : $(RM) $(TARGET) *.o core
Zaimplementować algorytm sortowania przez wybór.
Zaimplementować algorytm sortowania przez wstawianie.
Zaimplementować algorytm sortowania bąbelkowego.
Zaimplementować algorytm sortowania szybkiego.
Zaimplementować algorytm sortowania przez scalanie. Można wykorzystać funkcję std::inplace_merge().
https://en.cppreference.com/w/cpp/algorithm/inplace_merge
Zaimplementować algorytm sortowania przez kopcowanie.