Przeczytaj

Implementacja algorytmu sortowania pozycyjnego słów w języku C++

Jak już wiesz, sortowanie pozycyjne służy do sortowania zbiorów danych według porządku leksykograficznegoporządek leksykograficznyporządku leksykograficznego. Algorytm ten wewnętrznie używa pomocniczego - innego niż sortowanie pozycyjne - algorytmu sortowania, który jest odpowiedzialny za sortowanie według poszczególnych elementów w ciągach.

Pamiętajmy, że zastosowany algorytm musi być stabilnystabilny algorytm sortowaniastabilny – możemy użyć dowolnego algorytmu, jeśli tylko spełnia on ten warunek. Sortowanie pozycyjne jest często łączone np. z sortowaniem przez zliczaniePNx8quWZlsortowaniem przez zliczanie, ponieważ oba algorytmy są relatywnie szybkie dla rozważanego typu danych (ciągów znaków).

Na podstawie zdobytej wiedzy przygotujmy program sortujący zbiór słów w porządku leksykograficznym. Poniżej została przedstawiona jego specyfikacja.

Specyfikacja problemu:

Dane:

dane[] – tablica ciągów znaków zawierająca teksty do posortowania, składające się wyłacznie z małych liter alfabetu łacińskiego
liczbaElementow – liczba naturalna; liczba elementów w tablicy dane
dlugoscNajdluzszegoSlowa – liczba naturalna; długość najdłuższego słowa w tablicy dane

Wynik:

dane[] – posortowana leksykograficznie tablica ciągów znaków; jej elementy wypisane są w kolejnych liniach

Poniżej przedstawimy implementację algorytmu sortowania pozycyjnego w języku C++ i przetestujemy jego działanie dla następujących danych:

tablicy dane zawierającej ciągi znaków: „igor”, „ala”, „adam”
liczby elementów w tablicy dane wynoszącej 3
najdłuższego słowa o długości 4

Kod zawiera trzy funkcje realizujące algorytm. Zadaniem funkcji przygotujNapisy() jest przygotowanie ciągów w tablicy dane tak, aby wszystkie miały taką samą długość równą wartości zmiennej dlugoscNajdluzszegoSlowa. Jeżeli któryś z ciągów jest krótszy, zostaje na końcu (po ostatnim znaku) uzupełniony znakami grawisu – ` (jest to ostatni – przed małymi literami – znak w tablicy ASCII). Funkcja wyczyscNapisy() ma zadanie odwrotne – po wykonaniu sortowania musi usunąć nadmiarowe znaki grawisów, zastępując je spacjami. Funkcja sortowaniePrzezZliczanie() realizuje algorytm sortowania przez zliczanie.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. string dane otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy cudzysłów igor cudzysłów przecinek cudzysłów ala cudzysłów przecinek cudzysłów adam cudzysłów zamknij nawias klamrowy średnik. Linia 6. const int liczbaElementow znak równości 3 średnik. Linia 7. int dlugoscNajdluzszegoSlowa znak równości 4 średnik. Linia 9. void przygotujNapisy otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. while otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny dlugoscNajdluzszegoSlowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów ` cudzysłów średnik. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 15. zamknij nawias klamrowy. Linia 17. void wyczyscNapisy otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny dlugoscNajdluzszegoSlowa średnik plus plus j zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. if otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości apostrof ` apostrof zamknij nawias okrągły. Linia 21. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości apostrof apostrof średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 24. zamknij nawias klamrowy. Linia 27. void sortowaniePrzezZliczanie otwórz nawias okrągły int indeksZnaku zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. string temp otwórz nawias kwadratowy liczbaElementow zamknij nawias kwadratowy znak równości otwórz nawias klamrowy zamknij nawias klamrowy średnik. Linia 29. int tablicaZliczenLiter otwórz nawias kwadratowy 27 zamknij nawias kwadratowy znak równości otwórz nawias klamrowy zamknij nawias klamrowy średnik. Linia 31. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. int odczytanyKodZnaku znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy indeksZnaku zamknij nawias kwadratowy minus 96 średnik. Linia 33. tablicaZliczenLiter otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy plus plus średnik. Linia 34. zamknij nawias klamrowy. Linia 36. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny 27 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. tablicaZliczenLiter otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości tablicaZliczenLiter otwórz nawias kwadratowy i zamknij nawias kwadratowy plus tablicaZliczenLiter otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 38. zamknij nawias klamrowy. Linia 40. for otwórz nawias okrągły int i znak równości liczbaElementow minus 1 średnik i zamknij nawias ostrokątny znak równości 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. int odczytanyKodZnaku znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy indeksZnaku zamknij nawias kwadratowy minus 96 średnik. Linia 42. int indeksWTablicyWynikowej znak równości tablicaZliczenLiter otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy minus 1 średnik. Linia 43. temp otwórz nawias kwadratowy indeksWTablicyWynikowej zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 44. tablicaZliczenLiter otwórz nawias kwadratowy odczytanyKodZnaku zamknij nawias kwadratowy minus minus średnik. Linia 45. zamknij nawias klamrowy. Linia 47. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 48. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 52. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 53. otwórz nawias klamrowy. Linia 54. przygotujNapisy otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 56. for otwórz nawias okrągły int i znak równości dlugoscNajdluzszegoSlowa minus 1 średnik i zamknij nawias ostrokątny znak równości 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. sortowaniePrzezZliczanie otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 58. zamknij nawias klamrowy. Linia 60. wyczyscNapisy otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 62. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 63. cout otwórz nawias ostrokątny otwórz nawias ostrokątny dane otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 64. zamknij nawias klamrowy. Linia 66. return 0 średnik. Linia 67. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

string dane[] = { "igor", "ala", "adam" };
const int liczbaElementow = 3;
int dlugoscNajdluzszegoSlowa = 4;

void przygotujNapisy() {
	for (int i = 0; i < liczbaElementow; i++) {        
		while (dane[i].length() < dlugoscNajdluzszegoSlowa) {       
			dane[i] = dane[i] + "`";                                
		}
	}
}

void wyczyscNapisy() {
	for (int i = 0; i < liczbaElementow; i++) {                        
		for (int j = 0; j < dlugoscNajdluzszegoSlowa; ++j) {                
			if (dane[i][j] == '`')                              
				dane[i][j] = ' ';                              
		}
	}
}


void sortowaniePrzezZliczanie(int indeksZnaku) {    
	string temp[liczbaElementow] = {};              
	int tablicaZliczenLiter[27] = {};               

	for (int i = 0; i < liczbaElementow; i++) {                 
		int odczytanyKodZnaku = dane[i][indeksZnaku] - 96;      
		tablicaZliczenLiter[odczytanyKodZnaku]++;
	}

	for (int i = 1; i < 27; i++) {
		tablicaZliczenLiter[i] = tablicaZliczenLiter[i] + tablicaZliczenLiter[i - 1];  
	}

	for (int i = liczbaElementow - 1; i >= 0; i--) {        
		int odczytanyKodZnaku = dane[i][indeksZnaku] - 96;  
		int indeksWTablicyWynikowej = tablicaZliczenLiter[odczytanyKodZnaku] - 1;      
		temp[indeksWTablicyWynikowej] = dane[i];                
		tablicaZliczenLiter[odczytanyKodZnaku]--;               
	}

	for (int i = 0; i < liczbaElementow; i++) {             
		dane[i] = temp[i];
	}
}

int main()
{
	przygotujNapisy();                 

	for (int i = dlugoscNajdluzszegoSlowa - 1; i >= 0; i--) {    
		sortowaniePrzezZliczanie(i);                            
	}

	wyczyscNapisy();                                            

	for (int i = 0; i < liczbaElementow; i++) {                     
		cout << dane[i] << endl;
	}
    
   return 0; 
}

Efektem działania programu jest wyświetlenie danych ciągów znaków już po posortowaniu. Ciągi wyświetlane są w kolejnych wierszach:

adam
ala 
igor

Słownik

porządek leksykograficzny

sposób porządkowania ciągów w sposób analogiczny do porządku alfabetycznego

stabilny algorytm sortowania

algorytm sortowania, który dla dwóch równych elementów w zbiorze danych wejściowych zachowuje ich kolejność

Wprowadzenie

Symulacja interaktywna

Implementacja algorytmu sortowania pozycyjnego słów w języku C++

Słownik