Program sortowania przez scalanie w Javie: różnica między sortowaniem przez scalanie a szybkim sortowaniem

Wprowadzenie do programu sortowania przez scalanie w JAVA

Jak sama nazwa wskazuje, program sortowania przez scalanie w JAVA jest algorytmem sortującym. Został klasycznie skonceptualizowany jako algorytm dziel i zwyciężaj w JAVA. Program sortowania przez scalanie w Javie działa na zasadzie rekursywnego dzielenia tablicy wejściowej na dwa lub więcej składających się na nią problemów cząstkowych, dopóki nie będą one wystarczająco proste, aby można je było rozwiązać bezpośrednio.

Podproblemy składowe mogą być podobne lub w pewnym stopniu związane z problemem macierzystym. Indywidualne rozwiązania każdego podproblemu są następnie łączone w celu uzyskania rozwiązania pierwotnego problemu rodzicielskiego.

Jak działa program sortowania przez scalanie w Javie?

Jak wspomniano wcześniej, program sortowania przez scalanie w JAVA jest algorytmem dziel i zwyciężaj. Jest to sortowanie stabilne, co oznacza, że ​​elementy tablicy zachowują swoje pierwotne pozycje względem siebie przez cały proces sortowania.

• Dzielić: Na tym etapie tablica wejściowa jest dzielona na dwie części składowe. Ten etap jest ciągle powtarzany dla wszystkich wynikowych połówek macierzy, aż nie będzie już więcej połówek macierzy do dalszego podziału.
• Conquer: W tym kroku podzielone tablice są sortowane i łączone od dołu do góry, aby osiągnąć ostatecznie posortowaną tablicę.

Różnica między programem Quicksort a Merge Sort w Javie

Chociaż funkcjonalnie podobne, należy położyć odpowiedni nacisk na podstawową różnicę między sortowaniem szybkim a sortowaniem przez scalanie w JAVA.

• Mechanizm : Quicksort to wewnętrzny algorytm sortowania w miejscu, podczas gdy sortowanie scalające to zewnętrzny algorytm sortowania w miejscu. W quicksort elementy są sortowane na podstawie kluczowego elementu znanego jako element obrotowy. Przegub jest zazwyczaj wartością środkową w tablicy wejściowej. Elementy o wartości mniejszej niż oś są przesuwane po lewej stronie osi, a elementy o większej wartości po prawej stronie. Tutaj lewa strona jest określana jako lewa partycja, a prawa strona jest określana jako prawa partycja. Wręcz przeciwnie, mergesort dzieli tablicę na dwie podtablice (n/2) wielokrotnie, aż pozostanie tylko jeden element. Następnie łączy podtablice, tworząc posortowaną tablicę.
• Zastosowanie: Chociaż funkcja quicksort jest odpowiednia dla małych tablic, funkcja mergesort działa z każdą tablicą, niezależnie od jej rozmiaru.
• Szybkość : w przypadku szybkiego sortowania im mniejszy zestaw danych, tym szybszy algorytm. Z drugiej strony Mergesort działa ze stałą szybkością dla wszystkich zestawów danych.
• Zapotrzebowanie na miejsce i użycie pamięci: Jak wspomniano wcześniej, sortowanie przez scalanie to zewnętrzny algorytm sortowania poza miejscem. Jego złożoność przestrzenna to O (n). Dlatego wymaga dodatkowej pamięci (O (n)) do sortowania tablicy pomocniczej.

Przeczytaj także: Rodzaje literałów w Javie z przykładami

Analiza złożoności czasowej programu sortowania przez scalanie w JAVA

Program sortowania przez scalanie w JAVA ma złożoność czasową O (n*log n). Według Binary Search, ilekroć liczba jest dzielona na pół na każdym kroku, może być reprezentowana przez funkcję logarytmiczną „log n”. Liczba kroków (co najwyżej) może być reprezentowana przez log n +1. Środek każdej podtablicy to O (1).

Tak więc, aby scalić podtablice, wymagany będzie czas działania O (n). Stąd całkowity czas programu sortowania przez scalanie w JAVA wynosi n (log n +1). Sprowadza się to do złożoności czasowej O (n*log n) we wszystkich trzech przypadkach (najgorszy, średni i najlepszy), ponieważ sortowanie przez scalanie zawsze zajmuje liniowy czas na scalenie dwóch połówek.

Ucz się kursów oprogramowania online z najlepszych światowych uniwersytetów. Zdobywaj programy Executive PG, Advanced Certificate Programs lub Masters Programs, aby przyspieszyć swoją karierę.

Podsumowując

Tak jak posortowane dane dla ludzi są logiczne i łatwiejsze do zrozumienia, tak posortowane macierze są łatwiejsze w zarządzaniu dla komputerów. W tym miejscu program sortowania przez scalanie w JAVA okazuje się korzystny. Jest to wydajny, uniwersalny algorytm sortowania oparty na porównaniach.

Jeśli chcesz dowiedzieć się więcej na temat Java, pełnego stosu oprogramowania, sprawdź program Executive PG UpGrad i IIIT-B w zakresie pełnego stosu oprogramowania, który jest przeznaczony dla pracujących profesjonalistów i oferuje ponad 500 godzin rygorystycznego szkolenia, 9+ projekty i zadania, status absolwentów IIIT-B, praktyczne praktyczne projekty zwieńczenia i pomoc w pracy z najlepszymi firmami.