O bubble rodzaju vs seryjnej sortowania

Question

To pytanie wywiadzie, że Niedawno znalazłem w internecie:

Jeśli zamierzasz wdrożyć funkcję, która pobiera tablicę liczb całkowitych jako wejście i zwraca maksymalną, należy użyć sortowanie bąbelkowe lub scal sortuj, aby zaimplementować tę funkcję? Co się stanie, jeśli rozmiar tablicy jest mniejszy niż 1000? Co jeśli jest większy niż 1000?

ten sposób myślę o tym:

Po pierwsze, jest to naprawdę dziwne, aby użyć sortowania w celu realizacji powyższych funkcji. Możesz po prostu przejrzeć tablicę i znaleźć maksimum. Po drugie, jeśli musisz dokonać wyboru między tymi dwoma, to sortowanie bąbelkowe jest lepsze - nie musisz implementować całej procedury sortowania bąbelkowego, ale musisz wykonać tylko pierwsze podanie. To lepsze niż scalanie sortowania zarówno w czasie, jak iw przestrzeni.

Czy są jakieś błędy w mojej odpowiedzi? Czy coś ominąłem?

Answer 1

To podchwytliwe pytanie. Jeśli chcesz uzyskać maksymalną wartość (lub, w rzeczy samej, wartość k =, która obejmuje znalezienie mediany), istnieje całkiem niezły algorytm: O(n). Sortowanie to strata czasu. Właśnie tego chcą usłyszeć.

Tak jak mówisz, algorytm maksymalny jest naprawdę trywialny. Aby uzyskać takie pytanie, powinieneś mieć gotowy algorytm szybkiego wyboru, a także być w stanie zasugerować strukturę danych sterty na wypadek, gdybyś musiał zmienić listę wartości i zawsze był w stanie wytworzyć maksimum szybko.

Answer 2

Po pierwsze zgadzam się ze wszystkim, co powiedziałeś, ale być może pytasz o znajomość złożoności algorytmów i jak duży jest rozmiar wejściowy, w którym będzie najszybszy.

Sortowanie bąbelkowe to O(n2), a sortowanie scalone to O(nlogn). Tak więc, na małym zestawie nie będzie tak różnie, ale w przypadku wielu danych sortowanie bąbelkowe będzie znacznie wolniejsze.

Answer 3

Właśnie wyszukałem algorytmy. Sortowanie bąbelkowe wygrywa w obu sytuacjach ze względu na największą korzyść polegającą na tym, że wystarczy tylko raz go przepuścić. Sortowanie scalone nie może ciąć żadnych skrótów, ponieważ wystarczy obliczyć największą liczbę. Scalenie bierze długość listy, znajduje środkową, a następnie wszystkie liczby poniżej środka porównują się do lewej, a wszystkie wyżej do prawej; w przeciwieństwie do tworzenia unikalnych par do porównania. Znaczenie dla każdej liczby pozostałych w tablicy wymaga równej liczby porównań. Oprócz tego każda liczba jest porównywana dwukrotnie, więc najniższa liczba tablic najprawdopodobniej zostanie wyeliminowana w obu porównywanych. Oznacza tylko jedną liczbę mniej w tablicy po wykonaniu dwóch porównań w wielu sytuacjach. Bąbel będzie dominować

Answer 4

Blokowanie części maksymalnej, sortowanie bąbelkowe jest wolniejsze asymptotycznie, ale ma dużą zaletę dla małego n, ponieważ nie wymaga scalania/tworzenia nowych tablic. W niektórych implementacjach może to przyspieszyć w czasie rzeczywistym.

Answer 5

potrzebne jest tylko jedno przejście dla najgorszego przypadku, aby znaleźć maksymalnie u prostu trzeba przemierzać cały szereg, więc bańka będzie lepiej ..

Answer 6

Merge sortowania jest łatwy do komputera, aby posortować elementy i je zajmuje mniej czasu na sortowanie niż sortowanie bąbelkowe. Najlepszy przypadek sortowania korespondencji to n*log2n, a najgorszy przypadek to n*log2n. Najlepszym przypadkiem w przypadku sortowania bąbelkowego jest O(n), a najgorszy przypadek to O(n2).