• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Sortowanie zmiennych o przypisanych wartościach c++

VPS Starter Arubacloud
0 głosów
794 wizyt
pytanie zadane 22 września 2017 w SPOJ przez Józef Niecierski Początkujący (440 p.)
zmienione kategorie 22 września 2017 przez Józef Niecierski

(Dałem ten wątek do c++,a nie SPOJa, bo jest to problem ogólny, choć z zadania, ale nie tylko w tym konkretnym się pojawia). W zadaniu http://pl.spoj.com/problems/PP0506A/ mamy obliczyć odległość danych punktów w ukł. współ. od punktu (0,0). Program oblicza odległość danych punktów od tego początku układu poprawnie (w poniższym kodzie w liniach 16, 20, 22, 27, 28 są błędy, by nie podawać dobrego kodu).

Chodzi jednak o część zadania, gdzie na wyjściu mamy wypisać podane punkty z nazwą w kolejności od najbliższego do najdalszego. Czyli musimy posortować te punkty według zmiennych odl im przyporządkowanych. (Ten problem (jak posortować) nie dotyczy to tego jedynego zadania, bo często mamy ustawić liczby w kolejności np. rosnącej.) Jak tego dokonać? Jeśli użyć sortowania szybkiego, to jak to tu wprowadzić? Prosiłbym o pomoc. Jak zrobić, by te zmienne wypisać właśnie w kolejności rosnącej?? (Przepraszam za tablice wiem, że nie tak to się robi).

Jako odpowiedź możecie podać inny kod/wskazówkę co do sortowania ogólnie, niekoniecznie tego programu, chodzi mi o to, że np. dostajemy 10 liczb, po czym musimy ustawić je właśnie w kolejności rosnącej.

Nie wstawiam kodu, proszę o odpowiedź co do powyższego akapitu i ewentualnie jakąś wskazówkę co do wyjściowego zadania (ze SPOJa).

komentarz 22 września 2017 przez niezalogowany
Przywracam pytanie pod warunkiem poprawienia błędów. Dzięki ;)

1 odpowiedź

+1 głos
odpowiedź 22 września 2017 przez criss Mędrzec (172,590 p.)
edycja 23 września 2017 przez criss
 
Najlepsza

Po pierwsze:

string nazwa[n];
// ...
delete [] nazwa;

i tym podobne... Co to jest? Owszem, GCC oferuje takie rozszerzenie standardu (deklaracja lokalnej tablicy z rozmiarem będącym zmienną), ale to wciąż jest zmienna lokalna. Nie próbuj tej tablicy zwalniać.

Po drugie: popraw kod do takiego jaki napisałeś - tylko miesza, a wprowadzone przez ciebue błędy i tak nie stanowią żadnego wyzwania.
edit: autor usunął kod..

A już wracając bezpośrednio do twojego pytania:
Utwórz sobie jakąs prostą klase reprezentującą punkt, stwórz tablice takich obiektów i posortuj std::sort.

struct Point
{
   float x, y;
   std::string name;
};

std::vector<Point> points;
//na poczatku kodu znając już liczbe punktów n, możesz zawołać:
points.reserve(n); // ... żeby oszczędzić sobie czasu na niepotrzebne realokacje
// jeśli nie znasz std::vector, to doczytaj. Elementy dodajesz metodą push_back bądź emplace_back
// ...
std::sort(std::begin(points), std::end(points), /* lambda: */ [](const Point & a, const Point & b) { return (a.x*a.x + a.y*a.y) < (b.x*b.x + b.y*b.y); });

Edit: wyrzuciłem sqrt z kodu za podpowiedzią mokrowskiego.

komentarz 22 września 2017 przez mokrowski Mędrzec (155,460 p.)
sqrt jest tu niepotrzebny. Porównanie może być przecież wykonane tylko na odległościach podniesionych do kwadratu.

Następne łatwe usprawnienie to przetrzymywanie obliczonego 1 raz kwadratu odległości już w klasie punktu a nie robienie tego bezproduktywnie 2 razy.
komentarz 22 września 2017 przez criss Mędrzec (172,590 p.)
1. O, faktycznie, dzięki.
2. IMO przerost formy nad treścią ale jak kto woli
komentarz 23 września 2017 przez criss Mędrzec (172,590 p.)
edycja 23 września 2017 przez criss

Zrobiłem test odnośnie 2). Właściwie to wersja z zapisywaniem raz obliczonej odległości (a raczej jej kwadratu) okazuje się wolniejsza. Na najnowszym clangu różnice są dość duże (conajmniej 10-15%), a na gcc znacznie mniejsze (ale wciąż na niekorzyść 2) czy nawet niezauważalne. Co ciekawe - chociaż nie powiem żebym się nie spodziewał - jeśli z ExtPoint wyrzucimy słówko mutable i const z get() oraz zmuszeni zmienimy lambde żeby przyjmowała non-const referencje, to czas jeszcze się wydłuży. permalink

komentarz 23 września 2017 przez mokrowski Mędrzec (155,460 p.)
Po moich testach, jest szybsze. Ale stosuję dostęp indeksem od ostatniego elementu liczonego (cache), nie alokuję vector tylko tablicę z kontrolą indeksów... itp... ogólnie raport że Spoj 2.7 MB z czasem 0.00 dla gcc4.3*. Przy tej ilości danych trochę sport dla sportu... a... i tam są całkowite a nie float;)

Podobne pytania

0 głosów
1 odpowiedź 1,349 wizyt
pytanie zadane 23 września 2017 w C i C++ przez Józef Niecierski Początkujący (440 p.)
0 głosów
1 odpowiedź 355 wizyt
pytanie zadane 2 stycznia 2019 w JavaScript przez Q7V Gaduła (4,250 p.)
0 głosów
1 odpowiedź 139 wizyt
pytanie zadane 3 lipca 2015 w C i C++ przez Lopez Początkujący (460 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...