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<). Proszę przesłać archiwum ZIP katalogu z programem, który zawiera Makefile i pliki źródłowe. Program powinien kompilować się poleceniem 'make'.
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 L.sort(key=len) # sortowanie napisów pod względem długości L.sort(cmp=cmpfunc) # Python 2, przekazanie funkcji porównującej
#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++ # Mozliwe 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 - powstaja z plikow *.cpp. OBJECTS = main.o atrapa.o # Pliki naglowkowe - sa wlaczane do plikow *.cpp. HFILES = atrapa.h # Koncowy plik wykonywalny. TARGET = main.out # Definicja domyslnej reguly wzorcowej. # $< oznacza nazwe pliku pierwszej zaleznosci reguly. # $@ oznacza nazwe pliku celu w regule. # Wszystkie pliki obiektowe zaleza od wszystkich plikow naglowkowych. # Wciecia robimy przez TAB. %.o : %.cpp $(HFILES) Makefile $(CXX) $(CXXFLAGS) -c $< -o $@ $(TARGET) : $(OBJECTS) $(CXX) $(CXXFLAGS) $(LIBS) $(OBJECTS) -o $(TARGET) # Okreslenie celow 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.