Pytania otagowane jako sorting

algorytmiczny problem porządkowania zbioru elementów w odniesieniu do jakiejś relacji porządkowania.

3
W najgorszym przypadku w miejscu stabilny rodzaj?
Mam problem ze znalezieniem dobrych zasobów, które dają najgorszy przypadek w miejscu stabilnego algorytmu sortowania. Czy ktoś wie o dobrych zasobach?O ( n lnn )O(nln⁡n)O(n \ln n) Tylko przypomnienie, w miejscu oznacza, że ​​wykorzystuje przekazaną tablicę, a algorytm sortujący może używać tylko stałej dodatkowej przestrzeni. Stabilny oznacza, że ​​elementy z …
4
Jak zmierzyć „sortowanie”
Zastanawiam się, czy istnieje standardowy sposób pomiaru „sortowania” tablicy? Czy tablicę z medianą liczby możliwych inwersji można uznać za maksymalnie nieposortowaną? Rozumiem przez to, że jest to w zasadzie tak daleko, jak to możliwe, od sortowania lub odwrotnego sortowania.
5
Dodawanie elementów do posortowanej tablicy
Jaki byłby najszybszy sposób na zrobienie tego (z punktu widzenia algorytmu, a także ze względów praktycznych)? Myślałem o czymś następującym. Mógłbym dodać na końcu tablicy, a następnie użyć bąbelkowego sortowania, ponieważ ma najlepszy przypadek (tablica całkowicie posortowana na początku), który jest zbliżony do tego i ma liniowy czas działania (w …
3
Dlaczego wybór sortuje się szybciej niż sortowanie bąbelkowe?
Na Wikipedii napisano, że „... sortowanie selekcji prawie zawsze przewyższa sortowanie bąbelkowe i sortowanie gnomów”. Czy ktoś może mi wyjaśnić, dlaczego sortowanie jest uważane za szybsze niż sortowanie bąbelkowe, mimo że oba mają: Złożoność najgorszego przypadku :O(n2)\mathcal O(n^2) Liczba porównań : O(n2)\mathcal O(n^2) Najlepsza złożoność czasu sprawy : Sortowanie bąbelkowe:O(n)\mathcal …
6
Generowanie kombinacji z zestawu par bez powtarzania elementów
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …
1
Sortowanie jako program liniowy
Zaskakująca liczba problemów ma dość naturalne ograniczenia w programowaniu liniowym (LP). Przykłady, takie jak przepływy sieciowe, dopasowanie dwustronne, gry o sumie zerowej, najkrótsze ścieżki, forma regresji liniowej, a nawet ocena obwodu, patrz rozdział 7 w [1]! Ponieważ ocena obwodu ogranicza się do programowania liniowego, każdy problem w musi mieć sformułowanie …
3
Dlaczego Radix Sort ?
W sortowaniu radix najpierw sortujemy według najmniej znaczącej cyfry, a następnie sortujemy według drugiej najmniej znaczącej cyfry itd. I kończymy na posortowanej liście. Teraz, jeśli mamy listę liczb, potrzebujemy bitów, aby odróżnić te liczby. Tak więc liczba wykonanych przez nas przejść sortowania będzie wynosić . Każde przejście zajmuje czas O …
4
Minimalna liczba porównań potrzebnych do posortowania (uporządkowania) 5 elementów
Znajdź najmniejszą liczbę porównań potrzebną do posortowania (uporządkowania) pięciu elementów i opracuj algorytm, który sortuje te elementy przy użyciu tej liczby porównań. Rozwiązanie : Jest ich 5! = 120 możliwych wyników. Dlatego drzewo binarne do procedury sortowania będzie miało co najmniej 7 poziomów. Rzeczywiście, ≥ 120 oznacza≥ 7. Ale 7 …
4
Czy nie ma algorytmu sortowania ze wszystkimi konkretnymi pożądanymi właściwościami?
Na stronie internetowej Sorting Algorytmy wysunięto następujące oświadczenie: Idealny algorytm sortowania miałby następujące właściwości: Stabilny: nie zmienia się kolejności klawiszy równych. Działa w miejscu, wymagając dodatkowej przestrzeni.O ( 1 )O(1)O(1) Porównania klawiszy w najgorszym przypadku .O ( n ⋅ lg( n ) )O(n⋅lg⁡(n))O(n\cdot\lg(n)) Zamiany najgorszym przypadku .O ( n )O(n)O(n) …
4
Algorytmy sortowania, które akceptują losowy komparator
Ogólne algorytmy sortowania zazwyczaj wymagają zestawu danych do sortowania i funkcji komparatora, która może porównywać dwa pojedyncze elementy. Jeśli komparator jest relacją rzędu¹, to wynikiem działania algorytmu jest posortowana lista / tablica. Zastanawiam się jednak, które algorytmy sortowania faktycznie działałyby z komparatorem, który nie jest relacją rzędu (w szczególności, który …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.