Który algorytm sortowania wielu kryteriów ma być używany?

Powiedzmy, że mamy listę przedmiotów, każda pozycja ma (nieznaną) liczbę atrybutów. Sortowanie według pojedynczego atrybutu jest prostym algorytmem sortowania. Pytanie brzmi: jak posortować listę według wszystkich atrybutów? Każdy atrybut ma wagę, więc możemy najpierw sortować według najmniej ważnych atrybutów, a następnie według ważniejszego atrybutu za pomocą algorytmu stabilnego sortowania itd., Ale to oczywiście nie jest wydajne.Który algorytm sortowania wielu kryteriów ma być używany?

Dzięki.

Źródło

2011-09-15 Dima

utworzyć funkcję f: A1xA2x ..-> R [tj. podać wartość dla każdego elementu na podstawie priorytetów i atrybutów]. funkcja jest bardzo zależna od atrybutów [na przykład, jeśli wartości atrybutów mieszczą się w zakresie (0,9), podając wartość jest prosta: Sigma[val(i)*10^prio(i)] for each attribute i.

Powtórz listę, obliczyć wartość funkcji i zapisać wynik tej funkcji w pamięci podręcznej i sortować według niej. złożoność będzie O (nk + nlogn), gdzie k jest liczbą atrybutów, n jest liczbą elementów.

Źródło

2011-09-15 13:34:44 amit

Co to jest "prio (i)"? – Dima

'prio (i)' jest priorytetem i'tego atrybutu, gdzie i = 0 jest najmniej ważne w tym przykładzie. – amit

hej! Właśnie widziałem twoją odpowiedź (w 2 lata późno ..) .. i próbuję zrozumieć to przez prawie dwa dni .. Czy możesz spróbować wyjaśnić algorytm lub połączyć mnie z jakimś odniesieniem? –

Większość algorytmów sortowania może przyjmować jako dane wejściowe jedną funkcję porównania, która może łączyć kilka kryteriów sortowania.

Ostatecznie, aby móc w ogóle sortować, musi istnieć jedna relacja porządkowa między wszystkimi elementami (np. A jest zdecydowanie przed elementem B lub na odwrót, lub oba są równoważne; musi spełniać właściwości przechodnie/symetryczne/refleksyjne), co oznacza, że musi być możliwe sortowanie za pomocą jednego przebiegu algorytmu sortowania, z uwzględnieniem ważnej funkcji porównawczej.

Źródło

2011-09-15 13:34:47

Jest to również najgorszy przypadek O (k * n * logn), [k to liczba atrybutów, a n to liczba elementów], ponieważ trzeba sprawdzić k elementów w każdym porównaniu. taka sama granica jak sortowanie k razy ze stabilnym algorytmem. – amit

tak, ale nie musisz używać sortowania stabilnego. –

prawda, a wydajność będzie prawdopodobnie lepsza niż sortowanie k razy, ponieważ nie będziesz potrzebował wszystkich porównań k dla wszystkich elementów, wystarczy wskazać, że będzie on asymptotycznie taki sam [przynajmniej dla najgorszego przypadku analizy] – amit

SORT BY A,B,C

Twoje porównanie wewnątrz rodzaju będzie: A, B, C są w najwyższej do najniższej prioerity

Porównaj elementu 1 jest z elementu 2 jest
- Jeśli większa lub mniejsza Wynik zwrotu:
- reszta porównania B
- - Jeśli wynikiem większej lub mniejszej powrotu
- - reszta wynik porównania C powrotu

Można to ekstrapolować na kryteria A..n za pomocą prostej pętli.

Dla każdego kryterium w wykazie kryteriów
- Porównaj kryteria elementu 1 jest z elementem 2 na
- - Jeśli wynik większy lub mniejszy zwrot
- - Else kontynuować // dla jasności
Powrót równego

Powyższy zarówno zakładamy, że funkcja Porównanie jest Porównaj (element1, Element2)

Źródło

2011-09-15 13:42:02

to także jest O (k * n * logn), gdzie k jest liczbą atrybutów, a n jest liczbą elementów, taką samą linią, jak proste sortowanie k razy. – amit

Problem polega na tym, że jedno kryterium, A, ma nieskończenie większą wagę niż wszystko inne. Powiedzmy, że uczeń jest dobry w matematyce i czekam na kogoś, kto dołącza do mojego zespołu robotyki. Ale ci studenci ssiecie w etyce, profesjonalnym, kodowaniu, mają problemy z narkotykami i więcej, ale ponieważ matematyka zaczyna się, ważny czynnik algo zasugeruje, że najlepszym uczniem jest to, że przynajmniej będzie w najlepszych uczniach –

@MuhammadUmer - chcesz uzyskać * punktację * algorytm nie jest algorytmem * sortowania *. Więc chcesz wygenerować wynik dla każdego ucznia w oparciu o to, co uznasz za godne podziwu, a następnie posortujesz według tego wyniku. –

Który algorytm sortowania wielu kryteriów ma być używany?

Odpowiedz

Powiązane problemy