Scal sort w C
Program Scalesort, napisany normalnie, jest porównywalny (pod względem prędkości) z funkcją sort () dostarczonej przez C ++ w bibliotece algorytmu. Scal-sort jest również programem komercyjnym ogólnego przeznaczenia.
W tym artykule wyjaśniono, jak napisać program scalsort w języku C.
Algorytm podziału
W szerokim znaczeniu szereg elementów jest podzielony na dwie połowy: lewą połowę i prawą połowę. Jeśli całkowita liczba elementów do sortowania jest dziwna, wówczas lewa połowa jest większa niż prawa połowa, o 1 jednostkę. W przeciwnym razie obie połówki mają tę samą długość. Dwie połówki są następnie scalane podczas sortowania, aby utworzyć jedną sortowaną tablicę. Łączenie/sortowanie. Rozważ następujące znaki, które mają zostać posortowane:
Q w e r t y u i o pDzielenie tego zestawu postaci alfabetycznych na dwie połowy, daje:
Q w e r t y u i o pTablica podrzędna nazywa się biegiem. Więc lewa tablica podrzędna „Q w e r t” to uruchomienie, a prawy podpomór „y u i o p” jest również biegiem. Bieg może również mieć tylko jeden element.
Scalanie/sortowanie (pokonanie) Obie połówki w jeden zestaw daje:
E i o p q r t u yKod podzielony przez 2 to:
int iMiddle = (ibegin + iend) / 2;To jest podział całkowitego. Tak więc część wyniku jest pobierana. Z tym, jeśli całkowita liczba elementów w zestawie jest dziwna, lewa połowa byłaby większa niż w prawej połowie, o 1 jednostkę dla indeksowania opartego na zero.
Dla powyższego stwierdzenia i zestawu, „q”, „w”, „e”, „r”, „t”, „y”, „u”, „i”, „o”, „p”, ibegin = 0, ieend = 10 (czyli ostatni indeks 9, plus 1), imiddle = 5;
Kod do scalania/sortowania (podbij) to:
int i = ibegin;int j = imiddle;
for (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
w przeciwnym razie
Q [k] = p [j];
j = j + 1;
P jest podaną tablicą. Q miałby posortowany tablica, w tym przypadku.
Jeśli ten kod jest zastosowany do zestawu, 'q', ',', 'e', 'r', ',', 'y', ',', 'i', 'o', 'p' , nastąpi połączenie podzielonych połówek, ale nie ma sortowania (ponieważ każdy element w lewym biegu jest mniejszy niż „y”). Ten kod jest ponownie powtórzony, aby pokazać jego skuteczność w sortowaniu kolejnej pary biegów.
Praktyczny algorytm podziału i koniunktury
Cały program Mergesort może być napisany odgórny lub oddolny. W tym artykule program jest napisany, odgórny.
Scalesort działa koncepcyjnie w następujący sposób:
1) Podziel niezastrojony zestaw na N podzbiory (przebiegi), gdzie każdy ma jeden element. Zauważ, że zestaw z tylko jednym elementem jest uważany za posortowany.
2) Wielokrotnie scalaj podzbiory, aby uzyskać nowe sortowane podzbiory, aż pozostanie tylko jeden podzbiór. To jest sortowany zestaw.
Z tymi dwoma punktami dany zestaw nieporządkowany jest podzielony na dwa biegi. Każdy z tych dwóch przebiegów jest rejestrowany w pamięci w celu połączenia/sortowania razem, ale nie scalona ani sortowana. Każdy bieg ponownie po obu stronach, jest podzielony na dwa. Kolejne pary przebiegów są rejestrowane do łączenia/sortowania, ale jeszcze nie scalane lub sortowane. Ten podział na dwa i nagranie w celu połączenia/sortowania kolejnych par jest powtarzane, aż będzie tylko jeden element na bieg.
Nagrywanie w pamięci w celu połączenia/sortowania kolejnych przebiegów odbywa się poprzez wywołanie powyższego kodu sortowania rekurencyjnego po podziale. Kod sortowania jest w funkcji oddzielonej. Oświadczenie podziału i wywołanie funkcji sortowania (która również scalenia) znajduje.
Gdy podział osiągnie stan przebiegów pojedynczego elementu, funkcje scalania/sortowania zapisane w pamięci są wywoływane w odwrotnej kolejności. Jest to jedna funkcja scalania/sortowania, która była wielokrotnie rejestrowana w pamięci z różnymi argumentami. Kolejne pary pojedynczych elementów są najpierw sortowane, łącząc się jednocześnie. Sortowanie i scalanie kolejnych przebiegów trwa do momentu sortowania całego zestawu. Tak więc sortowanie nie dotyczy rozmieszczenia elementów, jak pierwotnie podano.
W C potrzebuje drugiej tablicy, której długość jest tak długa, jak podana tablica. Początkowo należy wykonać wszystkie elementy tej drugiej tablicy, domyślna wartość typu danych. Elementy danej tablicy są sortowane w tej drugiej tablicy. Następnie skopiował się do danej tablicy, zastępując nieprojektowane elementy.
W przypadku postaci ta druga tablica można utworzyć i zainicjować w następujący sposób:
char p [] = „q”, „w”, „e”, „r”, „t”, „y”, „u”, „i”, „o”, „p”;int sz = sizeof (p)/sizeof (p [0]);
char q [sz];
dla (int i = 0; i
Tutaj podana tablica to P, a druga tablica to Q. Ten kod może być w głównej funkcji. W C/C ++ domyślnym znakiem jest „, a nie przestrzeń (”). Ponieważ jednak kompilator G ++ nie pozwoliłby na przypisanie „do q [i], pojedynczej przestrzeni (”),.
Zauważ, że domyślne wartości elementów q tablicy nie są tak naprawdę konieczne dla pełnego programu scalania, ponieważ nadal zostaną zastąpione przez elementy zainteresowania. Deklarowanie tablicy q o swoim rozmiarze, SZ wystarczy.
Zestaw, „q”, „w”, „e”, „r”, „t”, „y”, „u”, „i”, „o”, „p”, jest używany do wyjaśnienia, jak wyjaśnić, jak wyjaśnić, jak wyjaśnić, jak wyjaśnić, w jaki sposób Scalesort jest osiągany praktycznie w tym rozdziale. W tym artykule nauczono wartości domyślnych tablicy Q jako dodatkowej wiedzy.
Zestaw jest podzielony na dwa zestawy:
„Q”, „w”, „e”, „r”, 't' i 'y', 'u', 'i', ',', 'p'Powyższy kod scalania/sortowania jest wywoływany jako funkcja, ale sortowanie i scalanie nie odbywa się. W prawdziwym programie sortowanie i scalanie tych dwóch przebiegów są rejestrowane w pamięci, najpierw. Sortowanie i scalanie niekoniecznie niekoniecznie zostaną wykonane na tych dwóch szczególnych aranżacjach postaci.
Powyższe dwa podzbiory są, dalej podzielone na dwa, aby mieć:
'Q', 'w', 'e' i 'r', 't' i 'y', 'u', 'i' i 'o', 'p'Zauważ, że dla każdej nowej dywizji lewy podzbiór jest dłuższy niż prawy podzbiór według jednej jednostki.
Powyższy kod scalania/sortowania jest nazywany funkcją, dla kolejnych par tych nowych podzbiorów. Ale sortowanie i łączenie się nie odbywa się natychmiast. Sortowanie i scalanie tych kolejnych par przebiegów jest rejestrowane w pamięci komputera. Sortowanie i łączenie się niekoniecznie, koniecznie, na konkretnym układzie postaci tych kolejnych par biegów.
Powyższe podzbiory są, dalej podzielone na dwa, aby mieć:
'Q', 'w' i 'e' i 'r' i 't' i 'y', 'u' i 'i' i 'o' i 'P'Sortowanie i łączenie kolejnych par jest rejestrowane.
Tutaj niektórych podzbiorów nie można już podzielić, ponieważ każdy z nich składa się z jednego elementu. Następnie podział ponad jednej długości powyżej, prowadzi do:
'Q' i 'w' i 'e' i 'r' i 't' i 'y' i 'u' i 'i' i ' O ' i ' p 'Sortowanie i łączenie kolejnych par jest rejestrowane.
Funkcja sortowania i scalania jest kodowana w sposób rekurencyjny. I tak będzie nazywane w kolejności odwróconej, ponieważ wiele razy został zarejestrowany.
Więc 'q' i 'w' zostaną sortowane i scalone w 'q', 'w'. 'E' i 'r' zostaną posortowane i scalone w 'e', 'r'. 'T'. 'Y' zostanie posortowane i scalone w 't', 'y'. 'U' i 'i' zostaną posortowane i scalone w 'i', 'u'. 'O'. 'P' zostanie posortowane i scalone w 'o', 'p'. Powyższa funkcja scalania i sortowania jest używana tutaj; i jest używany przez cały czas.
Dalej: 'q', ' i ' e ',' r ' zostaną posortowane i scalone w ' e ',', ',' r ',' w '. 'T', 'y' i 'i', 'u' zostaną posortowane i scalone w, 'i', 't', 'u', 'y'. Na tym etapie „o”, „p” nie jest połączone z żadnymi poprzednimi podzbiorami dwóch. Powyższa funkcja scalania i sortowania została tu używana i jest używana przez cały czas.
Następny etap: „e”, „q”, „r”, ' i ' i ',' t ',' u ',' są sortowane i scalone w 'e', ',', ',', ',', ',', ',', ',', '. I ', „q”, „r”, „t”, „u”, „w”, „y”. Na tym etapie „o”, „p” ponownie nie jest połączony z żadnym z poprzednich podzbiorów.
Ostatni etap: „e”, „i”, „q”, „r”, „t”, „u”, „w”, „y” i 'o', p ' są sortowane i scalone do „e”, „i”, „o”, „p”, „q”, „r”, „t”, „u”, „w”, „y”. Niepustowany zestaw został posortowany.
Kodowanie mersort w c
Zadaniem jest sortowanie tablicy P, a nie tablicy Q. Tak więc, dla całego programu Mergesort, Array Q jest najpierw wykonana kopia Array P. Następnie program sortuje tablicę Q do tablicy P. To nie jest to, co jest insynuowane powyżej. Istnieją cztery funkcje pełnego programu scalania.
Funkcja do podzielenia i scalania
To jest główna funkcja w programie. Przypomnij sobie, że połączenie obejmuje również sortowanie lewej i prawej kolejnej kolejności. To połączenie jest w pamięci i faktycznie zaczyna się, gdy tablica została podzielona przez dwa i dwa i dwa. Dopóki nie będzie tylko jeden element na bieg. Więc sortowanie i łączenie zaczyna się na tym etapie z parą dla jednego elementu na bieg. Szkielet funkcji sortowania jest:
void topdownSplitmerge (char q [], int ibegin, int iend, char p [])|. |
// Podziel podzbiór dłuższy niż 1 element na dwa
int iMiddle = (ibegin + iend) / 2; // imiddle jest punktem środkowym
|. |
|. |
|. |
// scal powstałe podzbiory z tablicy q [] w p []
topdownmerge (q, ibegin, imiddle, iend, p);
Ta funkcja przyjmuje podaną tablicę jako Q, która w tym przypadku jest w rzeczywistości tablicą kopii q. Brakuje również tablicy kopii jako P, która w tym przypadku jest właściwie podana tablica P. Dla pierwszego wywołania tej funkcji ibegin = 0 i ieend = n, gdzie n jest rozmiarem obu tablic. Są one z powodu zatrudnienia tablicy indeksowanej zero.
Po drugiej dywizji Ibegin będzie pierwszym indeksem lewego biegu, a IEND będzie ostatnim indeksem kolejnego prawego biegu. Podział na dwa daje całkowitą, imiddle, ignorując resztę. Jest to ostatni indeks lewego biegu, a także pierwszy indeks prawego biegu. Ta dwuznaczność jest eliminowana przez kod sortowania.
Ostatnie stwierdzenie w powyższym kodzie jest wywołanie funkcji precyzyjnej scalania i sortowania. To wezwanie trafia do pamięci, gdy jest wywoływane. Zostanie wykonany w kolejności odwróconej dla wszystkich jego połączeń, ponieważ jest to rekurencyjne wezwanie. Bierze zmienne jako argumenty. Q, Ibegin, Iend i P, otrzymane przez zewnętrzną funkcję kodowaną. imiddle, który jest również jednym z jego argumentów, jest tworzony w zewnętrznej funkcji kodowanej, powyżej wywołania.
Wewnątrz tej zewnętrznej funkcji kodowanej należy zidentyfikować lewe i prawe przebiegi (podzielone). Najlepiej to zrobić, wykonując rekurencyjne wywołanie zewnętrznej kodowanej funkcji w następujący sposób (niektóre kod zawarty w definicji funkcji):
void topdownSplitmerge (char q [], int ibegin, int iend, char p [])// Podziel podzbiór dłuższy niż 1 element na dwa
int iMiddle = (ibegin + iend) / 2; // imiddle jest punktem środkowym
// rekurencyjnie sortuje oba działanie z tablicy A [] na B []
TopdownSplitmerge (P, Ibegin, imiddle, q); // Podziel lewy podzbiór na dwa w celu sortowania, po zapamiętywaniu
TopdownSplitmerge (P, imiddle, Iend, Q); // Podziel prawy podzbiór na dwa w celu sortowania, po zapamiętywaniu
// scal powstałe podzbiory z tablicy q [] w p []
topdownmerge (q, ibegin, imiddle, iend, p);
Dwa nowe połączenia rekurencyjne zostały wpisane nad połączeniem rekurencyjnym TopDownMerge (). Te dwa połączenia zostaną zapamiętane wraz z TopDownMerge () i wywołane tyle razy, ile to konieczne, każdy w odwrotnej kolejności.
Jeśli podana tablica nie ma elementu, nie powinno być sortowania. Jeśli liczba elementów w danej tablicy wynosi 1, wówczas tablica jest już sortowana i nie powinno odbywać się sortowanie. Zajmuje się tym w jednym stwierdzeniu w środku, ale na górze zewnętrznej funkcji kodowanej, TopDownSplitmerge () w następujący sposób:
void topdownSplitmerge (char q [], int ibegin, int iend, char p [])if (Iend - ibegin<= 1)
powrót;
int iMiddle = (ibegin + iend) / 2;
TopdownSplitmerge (P, Ibegin, imiddle, q);
TopdownSplitmerge (P, imiddle, Iend, Q);
topdownmerge (q, ibegin, imiddle, iend, p);
Dokładna funkcja do scalania i sortowania
Nazwa tej funkcji to topdownmerge (). Nazywa się to rekurencyjnie przez topdownSplitmerge (). Kod to:
void topdownmerge (char p [], int ibegin, int imiddle, int ieend, char q [])// podczas gdy istnieją elementy w lewym lub prawym podzbiorze…
int i = ibegin;
int j = imiddle;
for (int k = ibegin; k
Q [k] = p [i];
i = i + 1;
w przeciwnym razie
Q [k] = p [j];
j = j + 1;
Teoretycznie funkcja ta itera od początku lewego przebiegu (podzbiór) do końca prawego przebiegu (podzbiór). Zwróć uwagę, w jaki sposób wspomniana powyżej niejednoznaczność została zaopiekowana przez while konstruktu if-konstrukt.
Wykonanie jednorazowej kopii dla wszystkich elementów
Na początku programu, po poniższej funkcji (niniejszej sekcji), wszystkie elementy danej tablicy muszą zostać skopiowane do tablicy, Q. Kod to:
void copyarray (char p [], int ibegin, int ieend, char q [])for (int i = ibegin; i
Jest wywoływany raz z następującej funkcji. Zakłada się to jako argumenty, podana tablica, p, a następnie 0, a następnie n, a druga tablica Q, która teoretycznie jest pusta, ale ma już taką samą liczbę elementów jak p. Iend, który jest taki sam jak n, tutaj, jest długością pierwotnie podanej tablicy.
Funkcja rozpoczęcia programu
Funkcja rozpoczęcia programu jest:
void topdownmergesort (char p [], char q [], int n)CopyArray (P, 0, N, Q); // p [] jest kopiowany do q [] raz
TopdownSplitmerge (q, 0, n, p);
Wywołuje funkcję copyArray () z oczekiwanymi argumentami. Wzywa następną funkcję główną, TopdownSplitmerge (), z pozycjami tablic, P i Q, zamieniony. Dlatego w kodzie topdownmerge () sortowane wartości są wysyłane do Q, a nie do p.
Umieszczenie kodu
Jeśli powyższe cztery zakodowane funkcje są wpisane w następującej kolejności,
- void topdownmerge ()
- void topdownSplitmerge ()
- copyArray ()
- TopdownMergesort ()
Następnie program Scalesort (składający się głównie z tych czterech funkcji) bez problemu będzie działał w kompilatorze C.
C Główna funkcja
Odpowiednią główną funkcją C dla tego programu jest:
int main (int argc, char ** argv)char p [] = „q”, „w”, „e”, „r”, „t”, „y”, „u”, „i”, „o”, „p”;
int sz = sizeof (p)/sizeof (p [0]);
char q [sz];
dla (int i = 0; i
TopdownMergesort (P, Q, SZ);
dla (int i = 0; i
printf („\ n”);
powrót 0;
Wniosek
Podziel i podbij algorytm dzieli problem na mniejsze kawałki, z nadzieją na niezależne ich rozwiązanie. Po rozwiązaniu wszystkich mniejszych elementów ich roztwory łączą się w jedno główne roztwór. W przypadku scal-sortowego istnieje ciągły podział przez dwa, dopóki każdy podzbiór będzie długi jeden element i automatycznie już posortowany. Łączenie tych pojedynczych elementów obejmuje funkcje rekurencyjne i faktyczne sortowanie, zaczynając od par pojedynczych elementów.