Obiecałam pomóc siostrze w rozwiązywaniu zadań z olimpiady dla gimnazjum, więc przy okazji wkleję kod tutaj.
(Psyyttt ten post powstał w 2012, więc udostępniam, ale lepiej wziąć to pod uwagę, że nie piszę w C++, a kod nadziergałam, gdy uczyłam się tego języka na studiach).
Ciężko mi to czymkolwiek uzasadnić… na upartego przypomina jedno z pierwszych zadań w języku C, które napisałam – książkę telefoniczną. Z tym, że tu obsługujemy tylko jedno nazwisko, a nie strukturę z imieniem, nazwiskiem, nr tel – dobra nieważne.
Zadanie: Dysponując listą nazwisk uczestników uporządkuj ją leksykograficznie (alfabetycznie).
Wejście: W pierwszym wierszu standardowego wejścia zapisano liczbę nazwisk N(1<= N <= 200). W następnych N wierszach zapisano po jednym nazwisku. Nazwisko rozpoczyna wielką litera, jego długość nie przekracza 50 znaków, i składa się tylko z liter alfabetu angielskiego.
Wyjście : W kolejnych wierszach wypisz nazwiska uczestników uporządkowane alfabetycznie.
Zwrócie uwagę na sposób przekazywania nazwisk – w przykładach najpierw podajemy liczbę: ile będzie dodanych osób, a dopiero później wprowadzamy kolejne nazwiska.
#include <string>
#include <stdlib.h>
using namespace std;
int number = 0;
void Sorting(string names[], int number);
int main() {
cout << "Podaj liczbe nazwisk" << endl;
cin >> number;
string *names = new string[number];
for (int i = 0; i < number; i++) {
cout << "podaj lastname:" << endl;
cin >> names[i];
}
Sorting(names, number);
for (int i = 0; i < number; i++) {
cout << names[i] << endl;
}
system("pause");
return 0;
}
void Sorting(string names[], int number) {
string lastname;
int i;
int j;
for (i = 1; i < number; ++i) {
lastname = names[i];
for (j = i – 1; j >= 0 && names[j] > lastname; –j) {
names[j + 1] = names[j];
}
names[j + 1] = lastname;
}
}
Logika działania jest dosyć prosta, mam nadzieję, że jak działa sortowanie alfabetyczne w C++ będzie zrozumiałe przez nazewnictwo.
Do sortowania nazwisk użyłam zwykłego sortowania insert sort. Można wybrać lepiej, a wręcz jestem pewna, że można napisać to lepiej. Wrzucam jako ciekawostkę – kod, który napisałam wieki temu.
W przypadku sortowania ciągów znaków, które mogą się różnić nieznacznie (jak np. nazwiska właśnie) znacznie lepiej sprawdzi się radix sort (http://pl.wikipedia.org/wiki/Sortowanie_pozycyjne), który używałby in-place merge sort lub library sort, w zależności czy będziemy potem dodawć sporo nowych elementów.
Zadanie można sobie rozbudować – listę nazwisk pobrać z pliku txt lub csv, dodać więcej danych o użytkownikach (adres, numer telefonu, datę urodzenia, liczbę rodzeństwa), dodać opcje sortowania po nowododanych kolumnach typu wyszukiwanie najstarszej osoby na liście, albo osoby o konkretnej liczbie rodzeństwa.
o dzięki, tego szukałam