Ta metoda jest szeroko stosowana podczas gry w karty. Elementy (mapy) dzielimy mentalnie na już „gotową” sekwencję A 1 , A 2 ,…, A i -1 , oraz na „pozostałą” (nie posortowaną) część: A i , A i +1 ,…, A N .

Istota metody polega na tym, że na każdym i-tym kroku (zaczynając od i = 2), i-ty element jest wyciągany z części nieposortowanej i umieszczany w części „gotowej”, podczas gdy jest wstawiany na Właściwe miejsce.

Metoda algorytmu tekstowego:

1. Zacznij.

2. Pętla, gdy i ma wartości od 2 do N,
krok = 1:

a) i-ty element (A(i)) jest umieszczony w komórce A(0);

b) przypisz j = -1, czyli j jest równe numerowi elementu znajdującego się na lewo od podmiotu (i-tego), a więc stojącego w „skończonej” sekwencji;

c) jeśli A(0) ≥ A(j), to umieść element A(0) w komórce A(j+1), w przeciwnym razie umieść element A(j) w komórce A(j+1), zmniejsz wartość j o jeden i powtórz krok c).

Na ryc. 1 przedstawia schemat blokowy metody sortowania bezpośrednie połączenie.

Metoda działa w następujący sposób: w i-tym kroku (zaczynając od i = 2), i-ty element jest umieszczany w wolnej komórce (np. A(0)). Ten element jest porównywany z elementem znajdującym się w „wykończonej” części po jego lewej stronie. Jeżeli element A(0) jest mniejszy, to porównywany (j-ty element) jest przesuwany w prawo o jedną pozycję, po czym do porównania brany jest kolejny element. Jeśli element A(0) okaże się nie mniejszy niż w porównaniu, to jest umieszczany w miejscu bezpośrednio po porównywanym elemencie.

Ryż. 1. Schemat blokowy bezpośredniego sortowania inkluzji

Na ryc. 2 przedstawia przykład sortowania przez bezpośrednie włączenie.

Sekwencja źródłowa
	(0)
ja = 2
ja = 3
ja = 4
I=5
ja = 6
ja = 7
ja = 8
Wynik

Ryż. 2. Przykład sortowania przez bezpośrednie włączenie

Sortowanie z bezpośrednim włączeniem jest bardziej odpowiednie w przypadku, gdy sortowane dane przychodzą sekwencyjnie (jeden po drugim).

Wybór bezpośredni Sortuj

Istota metody jest następująca. Najmniejszy element w „pozostałej” (nieposortowanej) części jest wybierany i zamieniany z pierwszym elementem (w tej samej nieposortowanej części). Następnie długość nieposortowanej części zmniejsza się o jeden element (o pierwszy), a cały proces jest kontynuowany z (n - 1) elementami, następnie z (n - 2) elementami itd., aż pozostanie jeden, największy element.

Ta metoda jest w pewnym sensie przeciwieństwem metody bezpośredniego włączenia. W metodzie inkluzji bezpośredniej na każdym etapie uwzględniany jest tylko jeden kolejny element i wszystkie elementy już „zakończonej” części sekwencji, wśród których znajduje się punkt włączenia tego kolejnego elementu. A w metodzie selekcji bezpośredniej, aby znaleźć jeden (minimalny) element, przeszukuje się wszystkie elementy części nieposortowanej i ten minimalny element jest umieszczany jako kolejny element w już „gotowej” części.

Metoda algorytmu tekstowego:

1. Zacznij.

2. Pętla, gdy i ma wartości od 1 do N - 1,
krok = 1:

a) umieść bieżący (i-ty) element w jakiejś komórce pamięci (X) i zapamiętaj numer seryjny(i) bieżący element (w zmiennej K);

b) pętla, podczas gdy j ma wartości od i+1 (czyli od elementu po i) do N, stride = +1:

treść pętli: jeśli X > A(j), to umieść element A(j) w komórce X i zapamiętaj jego numer w komórce K;

c) przypisz A(K) = A(i) i A(i) = X.

Na ryc. 3 przedstawia przykład sortowania metodą selekcji bezpośredniej.

Ryż. 3. Przykład sortowania metodą selekcji bezpośredniej

Ta metoda jest szeroko stosowana podczas gry w karty. Elementy (mapy) są mentalnie podzielone na już „gotową” sekwencję A1…An i oryginalną sekwencję Ai…An. Na każdym kroku, zaczynając od i=2 i zwiększając I za każdym razem o jeden, z oryginalnego ciągu jest wyodrębniany i-ty element i przesunięty do gotowej sekwencji, gdy jest wstawiany we właściwym miejscu.

Powyższe przedstawia jako przykład proces sortowania poprzez uwzględnienie ośmiu losowo wybranych liczb: Algorytm tego sortowania wygląda następująco:

FOR i:=2 TO n DO

włączenie x w odpowiednim miejscu wśród ... a[j];

W rzeczywistym procesie poszukiwania odpowiedniego miejsca wygodnie jest, naprzemienne porównania i ruchy w kolejności, przesiać X, tj. X jest porównywany z kolejnym elementem aj, a następnie albo X jest wstawiany na wolne miejsce lub aj jest przesunięty (przeniesiony) w prawo, a proces „odchodzi” w lewo. Należy pamiętać, że proces przesiewania może się zakończyć, gdy spełniony jest jeden z dwóch następujących warunków:

1. Element aj znajduje się z kluczem mniejszym niż klucz X.

2. Osiągnięto lewy koniec gotowej sekwencji.

Ten typowy przypadek powtarzającego się procesu z dwoma warunkami zakończenia pozwala nam zastosować dobrze znaną sztuczkę barierową (wartownik). Tutaj łatwo to zastosować, ustawiając barierę a0 o wartości X. (Zauważ, że w tym celu konieczne jest rozszerzenie zakresu indeksu w opisie zmiennej a do 0 ... n.)

Analiza metody inkluzji bezpośredniej. Liczba kluczowych porównań (Ci) w i-tym przesiewaniu wynosi co najwyżej i – 1, co najmniej – 1; jeśli założymy, że wszystkie permutacje n kluczy są jednakowo prawdopodobne, to średnia liczba porównań wynosi i/2. Liczba transferów (przypisania elementów) Mi jest równa Ci + 2 (łącznie z barierą). Dlatego Łączna porównania i liczba przelewów przedstawiają się następująco:

Zapisz = (n2 + n - 2)/4,

Cmax = (n2 + n - 4)/4,

M min \u003d Z * (n - 1),

M ave \u003d (n2 + 9n - 10) / 4,

M max = (n2 + 3n - 4)/2.

Oszacowania minimalne występują w przypadku już uporządkowanej początkowej sekwencji elementów, natomiast najgorsze oszacowania występują, gdy są one początkowo ułożone w odwrotnej kolejności. W pewnym sensie sortowanie według inkluzji wykazuje naprawdę naturalne zachowanie. Oczywiste jest, że powyższy algorytm opisuje stabilny proces sortowania: kolejność elementów o równych kluczach pozostaje niezmieniona.

Algorytm z bezpośrednimi wtrąceniami można łatwo poprawić, jeśli zwrócisz uwagę na to, że skończona sekwencja (a1 ... ai-1 , do której chcesz wstawić nowy element, jest już zamówiony. Naturalne jest zatrzymanie się na wyszukiwaniu binarnym, w którym próbuje się porównać ze środkiem gotowego ciągu, a następnie proces dzielenia na pół trwa aż do znalezienia punktu włączenia. Tak zmodyfikowany algorytm sortowania nazywa się binarną metodą wstawiania.

Sortowanie to uporządkowanie danych w pamięci w sposób regularny według wybranego parametru. Za regularność uważa się wzrost (spadek) wartości parametru od początku do końca tablicy danych.

Podczas przetwarzania danych ważna jest znajomość pola informacyjnego danych i jego umiejscowienia w maszynie.

Rozróżnij sortowanie wewnętrzne i zewnętrzne:

Sortowanie wewnętrzne - sortuj w pamięć o dostępie swobodnym;

Sortowanie zewnętrzne - sortowanie w pamięci zewnętrznej.

Jeśli sortowane rekordy zajmują dużą ilość pamięci, ich przenoszenie jest kosztowne. Aby je zmniejszyć, sortowanie odbywa się w kluczowa tablica adresów, to znaczy wykonują permutację wskaźników, a sama tablica się nie porusza. To - metoda sortowania tabeli adresów.

Podczas sortowania mogą wystąpić te same klucze. W takim przypadku pożądane jest ułożenie tych samych kluczy po sortowaniu w takiej samej kolejności, jak w pliku źródłowym.To - stabilne sortowanie.

Rozważymy tylko rodzaje, które nie używają dodatkowej pamięci RAM. Takie rodzaje nazywają się "w tym samym miejscu".

Wydajność sortowania można rozpatrywać według kilku kryteriów:

Czas spędzony na sortowaniu;

Ilość pamięci RAM wymagana do sortowania;

Czas spędzony przez programistę na pisaniu programu.

Wyróżniamy pierwsze kryterium. Można wziąć pod uwagę ekwiwalent czasu spędzonego na sortowaniu liczba porównań oraz liczba ruchów podczas sortowania.

Kolejność liczby porównań i ruchów podczas sortowania leży w granicach

Od O (n log n) do O (n 2);

O(n) to przypadek idealny i nieosiągalny.

Istnieją następujące metody sortowania:

Metody ścisłe (bezpośrednie);

Ulepszone metody.

Surowe metody:

Metoda bezpośredniego połączenia;

Metoda selekcji bezpośredniej;

metoda bezpośredniej wymiany.

Skuteczność ścisłych metod jest mniej więcej taka sama.

Bezpośrednie sortowanie z uwzględnieniem

Elementy są mentalnie podzielone na gotowy ciąg a 1 ,...,a i-1 oraz ciąg oryginalny.

W każdym kroku, zaczynając od i = 2 i zwiększając i za każdym razem o jeden, i-ty element jest wyodrębniany z oryginalnej sekwencji i przenoszony do gotowej sekwencji, podczas gdy jest wstawiany we właściwym miejscu.

Istota algorytmu jest następująca:

dla i = 2 do n

X = a(i)

Znajdujemy miejsce wśród (1) ... a (i), aby uwzględnić x

następny ja

Istnieją dwa algorytmy sortowania z bezpośrednim włączeniem. Po pierwsze - bez bariery

Algorytm sortowania bezpośredniego włączenia bez barier

dla i = 2 do n

X = a(i)

Dla j = i - 1 aż do 1

Jeśli x< a(j)

Wtedy a(j + 1) = a(j)

W przeciwnym razie przejdź do L

endif

Następny j

L: a(j + 1) = x

następny ja

zwrócić

Wadą powyższego algorytmu jest naruszenie technologii programowanie strukturalne, przy którym niepożądane jest stosowanie skoków bezwarunkowych. Jeśli pętla wewnętrzna jest zorganizowana jako pętla while, to konieczne jest ustawienie „bariery”, bez której przy ujemnych wartościach kluczy następuje utrata znaczenia i „zamrożenie” komputera.

Algorytm sortowania z bezpośrednim włączeniem bariery

dla i = 2 do n

X = a(i)

A(0) = x (a(0) - bariera)

J = ja - 1

Dopóki x< a(j) do

A(j+1) = a(j)

J = j - 1

Koniec

A(j+1) = x

następny ja

zwrócić

Wydajność algorytmu bezpośredniego włączenia

Liczba kluczowych porównań Ci w i-tym badaniu przesiewowym wynosi co najwyżej i-1, co najmniej -1; jeśli założymy, że wszystkie permutacje N kluczy są jednakowo prawdopodobne, to średnia liczba porównań = i/2. Liczba transferów to Mi=Ci+3 (łącznie z barierą). Oszacowania minimalne występują w przypadku już uporządkowanej początkowej sekwencji elementów, natomiast najgorsze oszacowania występują, gdy są one początkowo ułożone w odwrotnej kolejności. W pewnym sensie sortowanie według włączenia wykazuje naprawdę naturalne zachowanie. Oczywiste jest, że powyższy algorytm opisuje stabilny proces sortowania: kolejność elementów o równych kluczach pozostaje niezmieniona.

Liczba porównań w najgorszym przypadku, gdy tablica jest posortowana odwrotnie, C max = n (n - 1) / 2, czyli - O (n 2). Liczba permutacji M max = C max + 3(n-1), tj. - O (n 2). Jeśli tablica jest już posortowana, to liczba porównań i permutacji jest minimalna: C min = n-1; Mmin = =3(n-1).

Sortuj według wymiany bezpośredniej (sortowanie bąbelkowe)

W ta sekcja opisano metodę, w której najbardziej charakterystyczną cechą procesu jest zamiana miejsc dwóch elementów. Opisany poniżej algorytm bezpośredniej wymiany opiera się na porównaniu i zamianie miejsc na parę sąsiednie elementy i kontynuowanie tego procesu do momentu uporządkowania wszystkich elementów.

Iterujemy po tablicy, za każdym razem przesuwając najmniejszy element pozostałej sekwencji na lewy koniec tablicy. Jeśli weźmiemy pod uwagę tablice jako konstrukcje pionowe, a nie poziome, to elementy mogą być interpretowane jako bąbelki w kadzi z wodą, przy czym waga każdego z nich odpowiada jego kluczowi. W tym przypadku przy każdym przejściu jedna bańka unosi się niejako do poziomu odpowiadającego jego wadze (patrz ilustracja na poniższym rysunku).

C min = n - 1, rząd O(n),

i żadnego ruchu.

Analiza porównawcza metod sortowania bezpośredniego pokazuje, że „sortowanie” wymienne w swojej klasycznej postaci jest skrzyżowaniem sortowania z wykorzystaniem inkluzji i selekcji. Jeśli wprowadzi się w nim powyższe ulepszenia, to dla odpowiednio uporządkowanych tablic sortowanie bąbelkowe ma nawet przewagę.

Ta metoda jest powszechnie znana jako „sortowanie bąbelkowe”.

Algorytm metody bezpośredniej wymiany

dla j = n do i krok -1

jeśli a(j)< a(j - 1) then

W naszym przypadku dostaliśmy jedno przejście „bezczynne”. Aby nie oglądać ponownie elementów, a tym samym dokonywać porównań, spędzając na tym czas, możesz wpisać checkbox fl, który pozostaje w wartości fałszywy, jeśli podczas następnego przejazdu nie nastąpi wymiana. W poniższym algorytmie dodatki zaznaczono pogrubioną czcionką.

fl = prawda

jeśli fl = false to zwróć

fl=fałsz

dla j = n do i krok -1

jeśli a(j)< a(j - 1) then

fl = prawda

Udoskonalenie sortowania bąbelkowego to sortowanie z wytrząsaniem, w którym po każdym przejściu kierunek jest odwracany w wewnętrznej pętli.

Wydajność algorytmu sortowania bezpośredniej wymiany

Liczba porównań C max = n(n-1)/2 , rząd O(n 2).

Liczba ruchów M max \u003d 3C max \u003d 3n (n-1) / 2, kolejność O (n 2).

Jeśli tablica jest już posortowana i zastosowany algorytm flagi, to wystarczy tylko jedno przejście, a wtedy otrzymujemy minimalną liczbę porównań

Sortowanie z włączeniem bezpośrednim, podobnie jak proste sortowanie przez wybór, jest zwykle używane w przypadku tablic, które nie zawierają zduplikowanych elementów.

Sortowanie metodą bezpośredniego włączenia, podobnie jak wszystkie opisane powyżej, odbywa się etapami. Na k -tym kroku uważa się, że część tablicy zawierająca pierwsze k-1 elementów jest już uporządkowana, czyli

a ≤ a ≤ ... ≤ a .

Następnie należy wziąć k -ty element i znaleźć dla niego miejsce w posortowanej części tablicy, aby po jego wstawieniu kolejność nie została naruszona, czyli trzeba znaleźć takie j (1 ≤ j ≤ k -1) że a [j] ≤ a[ k]< a. Затем вставить элемент а [k] на найденное место.

Z każdym krokiem posortowana część tablicy rośnie. Wykonanie pełnego sortowania wymaga n-1 kroków.

Spójrzmy na ten proces na przykładzie. Załóżmy, że wymagane jest posortowanie tablicy 10 elementów w kolejności rosnącej przy użyciu metody bezpośredniego włączenia

1 - krok

13 6 8 11 3 1 5 9 15 7

menta (13). Musisz włożyć drugi.

element tablicy (6) tak, aby

została zachowana. Od 6< 13, вставляем

6 na pierwszym miejscu. Posortowana część

tablica zawiera dwa elementy (6 13).

3 - krok

6 8 13 11 3 1 5 9 15 7 Następny element- 11. Jest napisane w uporządkowanej części tablicy na trzecim miejscu, ponieważ 11 > 8 , ale 11< 13.

5- krok

3 6 8 11 13 1 5 9 15 7 Z tego samego powodu do pierwszego zapisuje się 1

6 - krok

1 3 6 8 11 13 5 9 15 7 Od 5 > 3, ale 5< 6 то место 5 в упоря-

Część córka jest trzecią.

7 -krok

1 3 5 6 8 11 13 9 15 7 Miejsce cyfry 9 jest szóste.

8 -krok

1 3 5 6 8 9 11 13 15 7 Ustal miejsce na przedostatni

Element 15. Okazuje się, że ten element

Element tablicy jest już na swoim miejscu.

9 -krok

1 3 5 6 8 9 11 13 15 7 Pozostaje znaleźć odpowiednie miejsce dla

Ostatni element (7).

1 3 5 6 7 8 9 11 13 15 Tablica jest całkowicie posortowana.

Teraz możemy krótko opisać fragment algorytmu bezpośredniego sortowania inkluzji:

Dla k:= ​​2 To n Do

(bo zaczynam sortować od szukania dobrego miejsca na a, przechodzę od 2 do n )

„wstawić x w odpowiednim miejscu w , ..., a[k]”

Pozostaje odpowiedzieć na pytanie, jak szukać odpowiedniego miejsca dla elementu x. Zróbmy tak: przyjrzymy się elementom znajdującym się na lewo od x (czyli tym, które są już uporządkowane), przechodząc na początek tablicy. Konieczne jest przeskanowanie elementów a[ j ] , j zmienia się z k-1 na 1. Taki skan musi się zakończyć, gdy spełniony jest jeden z następujących warunków:

znaleziony element a[j]< x, что говорит о необходимости вставки x между a и a[j].

· Osiągnięto lewy koniec zamówionej części tablicy, dlatego należy wstawić x w pierwszej kolejności.

Dopóki nie zostanie spełniony jeden z tych warunków, przesuniemy oglądane elementy na pierwszą pozycję w prawo, dzięki czemu miejsce pod x zostanie zwolnione w posortowanej części.

Program bezpośredniego sortowania włączenia:

program n3; ( Sortuj w porządku malejącym )

wpisz ar=tablica liczb całkowitych;

sortowanie procedur3(var a:ar);

var i,j,x,k:liczba całkowita;

dla k:=2 do n do

x:=a[k]; j:=k-1;

while (j>0)i(x>=a[j]) do

writeln("Wprowadź tablicę źródłową:");

dla i:=1 do n wykonaj read(a[i]);

writeln("Posortowana tablica:");

dla i:=1 do n napisz(a[i]," ");

Cel Zbadaj sortowanie tablic metodą bezpośredniego włączania i oceń wydajność tego algorytmu.

Informacje ogólne

Sortowanie z włączeniem bezpośrednim, podobnie jak proste sortowanie przez wybór, jest zwykle używane w przypadku tablic, które nie zawierają zduplikowanych elementów. Sortowanie tą metodą odbywa się sekwencyjnie krok po kroku. Na k-ty krok uważa się, że część tablicy zawierająca pierwsze k-1 elementów jest już uporządkowana, to znaczy. Następnie musisz wziąć k-ty element i wybierz dla niego miejsce w posortowanej części tablicy tak, aby po jej wstawieniu kolejność nie została zakłócona, czyli musisz znaleźć taką rzecz. Następnie musisz wstawić element a[k] w znalezionym miejscu. Z każdym krokiem posortowana część tablicy rośnie. Wykonanie pełnego sortowania wymaga n-1 kroków. Pozostaje odpowiedzieć na pytanie, jak szukać odpowiedniego miejsca dla elementu x. Postępujemy następująco: przyjrzymy się elementom znajdującym się na lewo od x (czyli tym, które są już uporządkowane), przechodząc na początek tablicy. Należy przejrzeć elementy a[j], j zmienia się od k-l do 1. Takie wyszukiwanie zakończy się, gdy spełniony zostanie jeden z następujących warunków: zostanie znaleziony element a[j] Przykład Opiszmy krótko fragment algorytm sortowania z wykorzystaniem bezpośredniego włączenia: beginx:= a[k]; j:=k-1; (wstaw x w odpowiednim miejscu w a, ..., a[k] ) (w tym celu organizujemy pętlę, która działa while ) ( j > 0 i x

Zadanie kontrolne

Napisz program, który wstawi ostatni element tablicy po pierwszym ujemnym elemencie tej samej tablicy.

Opcje zadań

UWAGA!!! O ile wyraźnie nie zaznaczono inaczej, dane wejściowe (tablica źródłowa) i dane wyjściowe (tablica posortowana) są tworzone jako plik tekstowy, zawierające liczby całkowite! Dla wszystkich zadań napisz wstępnie procedurę sortowania tablicy za pomocą metody bezpośredniego dołączania. 1. Dany szereg zawierający n elementów. Posortuj je w porządku rosnącym, odrzucając wszystkie zduplikowane elementy. 2. Zdefiniuj modę ten rząd- wartość, która występuje najczęściej wśród jego elementów. 3. Oryginalny zbiór danych to sekwencja rekordów składająca się z nazwiska, wieku i stażu pracy. Wydrukuj tę listę: 1) w porządku alfabetycznym; 2) w kolejności rosnącej wieku; 3) w kolejności zwiększania doświadczenia zawodowego. 4. Napisz procedurę sortowania w porządku malejącym. 5. Dany szereg liczb całkowitych. Zbierz wszystko w porządku rosnącym różne liczby zawarte w tej serii. 6. Dostajesz serię n odrębnych liczb całkowitych. Uzyskaj różne liczby całkowite, takie, że 7. Podane liczby całkowite Znajdź najwyższa wartość w tej kolejności, po usunięciu z niej wszystkich członków o wartości 8. Biorąc pod uwagę naturalny Liczby to wyniki n zawodników mierzone w setnych sekundy w biegu na 100 m. Wyznacz drużynę czterech najlepszych biegaczy do udziału w sztafecie 4x100, tj. wskaż jedną z czterech liczb naturalnych i, j, k , l taki, że suma ma najmniejszą wartość. 9. Mając n niezależnych losowych punktów, o współrzędnych (xi; yi), równomiernie rozmieszczonych w okręgu o promieniu 1 wyśrodkowanym na początku. Napisz program, który uporządkuje punkty w kolejności rosnącej odległości od środka. 10. Otrzymasz n dodatnich dwucyfrowych liczb całkowitych. Traktując każdą liczbę jako parę cyfr z zakresu 0–9, posortuj je (liczby) w kolejności rosnącej. 11. Biorąc pod uwagę n punktów na płaszczyźnie. Określ (n-1)-łącza nieprzecinającą się zamkniętą polilinię przechodzącą przez wszystkie te punkty. (Sąsiadujące segmenty polilinii mogą leżeć na tej samej linii prostej.) Wskazówka. Weźmy punkt najbardziej na lewo (czyli punkt o najmniejszej współrzędnej x) i narysujmy z niego promienie do wszystkich pozostałych punktów. Teraz uporządkujmy te promienie od dołu do góry i uporządkujmy punkty na jednym promieniu według odległości od początku promienia (odbywa się to dla wszystkich promieni z wyjątkiem dolnych i górnych). Polilinia opuszcza wybrany (najbardziej lewy) punkt wzdłuż dolnego promienia, następnie wzdłuż wszystkich pozostałych promieni (w opisanej kolejności) i powraca wzdłuż górnego promienia. 12. Biorąc pod uwagę n punktów na płaszczyźnie. Skonstruuj ich wypukły kadłub - minimalną wypukłą figurę, która je zawiera. (Gumowy pierścień naciągnięty na gwoździe wbite w deskę jest ich wypukłą powłoką). Wskazanie. Posortujmy punkty. Następnie, biorąc pod uwagę kolejno punkty, zbudujemy wypukłą powłokę już rozpatrywanych punktów.