NOVINKA: Kurz kybernetické bezpečnosti s akreditací MŠMT, nyní již od 0 Kč. Staň se žádaným profesionálem. Zjisti více:
Avatar
Vakos
Tvůrce
Avatar
Vakos:7.7.2019 0:00

Ahoj, chtěl bych udělat program, kde z porovnaných dat by vytvořil seřazený seznam.

Dejme tomu, že mám seznam předmětů, kde chci porovnat jejich velikost a udělat index od největšího po nejmenší.

Problém je, že nechci nikde zapisovat jejich velikost v číselné podobě, ale chci je první všechny manuálně porovnat a na základě mého porovnání udělat index. (Důvod toho způsobu je ten, že toto je jen příklad a v konkrétním případě, který nechci zmiňovat, se jedná o abstraktní data a lze je porovnat pouze takto, subjektivně)

Jak by se tohoto dalo dosáhnout? Nějaké tipy na články které by mi mohly pomoct?

Díky

Editováno
Odpovědět
7.7.2019 0:00
"Jediný způsob, jak dělat skvělou práci, je milovat to, co děláte. Pokud jste to ještě nenašli, hledejte dál. Ne...
Avatar
Neaktivní uživatel
Tvůrce
Avatar
Odpovídá na Vakos
Neaktivní uživatel:7.7.2019 1:19

Při použití standardních řadících algoritmů není potřeba nikam zapisovat jednotlivé "velikosti" - prostě porovnáváš jeden prvek s jiným.

[Termín k vyhledání Total Order]

Předpokládám teď, že to tvoje porovnávání je tranzitivní, antisymetrické a reflexivní. To jsou totiž přesně 3 požadavky na komparátor použitý v řadícím algoritmu, pokud chci docílit totálního seřazení.

O co teda jde lidsky řečeno:

Tranzitivita: Pokud platí, že A ® B a také B ® C => A ® C.
Pokud je Adam menší než Bob a Cyril je větší než Bob, pak je Cyril větší než Adam.

Antisymetrie: A ® B a B ® A pak určitě A = B nebo jinak řečeno A ® B => NOT B ® A pro všechna A různá od B.
Pokud je Adam alespoň tak vysoký jako Bob a Bob je alespoň tak vysoký jako Adam, pak jsou stejně velcí. Jinak řečeno, pokud nejsou stejně velcí, pak nemůžou být oba alespoň stejně velcí jako ten druhý.

Reflexivity: A ® A pro všechna A.
Adam je alespoň tak velký jako Adam.

Všimni si, že na relační symbol ® dobře sedí neostrá nerovnost. Menší rovno nebo věští rovno.

Pokud tohle platí ve tvém systému, tak bys to měl normálně seřadit quicksortem nebo mergesortem správně.

Zdroje:
https://en.m.wikipedia.org/…/Total_order
https://en.m.wikipedia.org/…ng_algorithm

Nahoru Odpovědět
7.7.2019 1:19
Neaktivní uživatelský účet
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:7.7.2019 22:13

https://www.itnetwork.cz/…itmy-razeni/

Pokud mas male pole, tak je vyhodny insert sort, ale misto od zacatku porovnavas vzdy stred pole, stred zbyle casti, atd.
Pokud mas delsi, tak je lepsi quick sort.

A co ti brani pouzit nativni algoritmus tveho programovaciho jazyka? Ze potrebujes vytvaret vlastni reseni?
https://www.geeksforgeeks.org/…n-list-sort/

Editováno
 
Nahoru Odpovědět
7.7.2019 22:13
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:8.7.2019 8:52

https://mlich.zam.slu.cz/…sorting3.htm
Jeste muzes zkusit takovy muj pokus. Ale neni to moc dodelane a prehledne :)
2. Vyberes Efectivity test, kliknes Start efectivity.

  • Test postupne zvysuje velikost pole a zkousi algoritmus, meri cas. Pokud soucet presahne nejakou hodnotu, dalsi pokusy zastavi. Cili, cim vic cisel, tim rychlejsi algoritmus.

1. U Algorirmus kliknes (fast), to by melo zaskrtnout 15 algoritmu. Pocet prvku je vybrany 1000. Kliknes Start.

  • Tento test vytvori statistiky algoritmu, cas, pocet nutnych porovnavani a tak.
  • Pak si tam dej treba all (37 algoritmu)

Nevyhoda je, ze tam muzou byt chyby a neco je nedodelane a je tam chaos v kodu, obcas.

Nej algoritmy jsou zname:

  • cas: tim sort (insert kombinovany s list-merge), quick sort, list merge (upraveny merge sort)
  • cas pro specialni pripad: counting, radix sort
  • pocet porovnani: tim sort, insert to middle, list merge
  • male naroky na pamet: tim sort, quick sort

Pro 10.000 prvku:

  • sortTimsort - 120432
  • XsortInsertMid­dle_1a - 123217 cmp operaci porovnani 2 cisel a<=b (tam mam asi chybku, obvykle byva lepsi nez tim)
  • sortListMerge_2a - 123653 (presunuje z pole a do b a zpet, takze potrebuje extra pamet)
  • sortQuick2_2a - 165071 (v nejhorsi variante je ale pocet operaci stejny jako bubble sort)

A zajimave mozna bude pro tebe porovnani 4 cisel, pokud chces stahnout pocet cmp a budes si pamatovat vysledky prechozich operaci. Viz Taskkill, ti to krasne vedecky rozepsal :)
https://mlich.zam.slu.cz/…-sort-x2.htm
Pokud bys mel moznost multi-threading, tak lze udelat algoritmus, ktery otevre 3 vlakna. A jedno z nich po 3 krocich serazeni ukonci. Cili, idealni algoritmus. cmp = n - 1, pocet porovnani je roven (poctu prvku - 1). U 10.000 by to bylo 9.999 a ne 120.000 :) Ale mel bys rozjetych 10.000 vlaken, nebo, tak nejak (mozna 10.000x10.1000). V podstate neco jako bubble sort.

Editováno
 
Nahoru Odpovědět
8.7.2019 8:52
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 4 zpráv z 4.