Sortowanie metodą naiwną

Sortowanie naiwne jest również bardzo złym algorytmem sortującym, lecz daje zawsze poprawne wyniki. Zasada działania jest bardzo prosta:

Przeglądamy kolejne pary sąsiednich elementów sortowanego zbioru. Jeśli bieżąco przeglądana para elementów jest w złej kolejności, elementy pary zamieniamy miejscami i całą operację rozpoczynamy od początku zbioru. Jeśli przeglądniemy wszystkie pary, zbiór będzie posortowany.

Naiwność (lub, jak wolą niektórzy, głupota) algorytmu wyraża się tym, iż po napotkaniu nieposortowanych elementów algorytm zamienia je miejscami, a następnie rozpoczyna całą pracę od początku zbioru. Złożoność obliczeniowa algorytmu przy sortowaniu zbioru nieuporządkowanego ma klasę O(n³). Sortowanie odbywa się w miejscu.

Algorytm sortowania naiwnego występuje w dwóch wersjach - rekurencyjnej oraz iteracyjnej. Wersja rekurencyjna jest jeszcze gorsza od iteracyjnej, gdyż dodatkowo zajmuje pamięć na kolejne poziomy wywołań rekurencyjnych, dlatego nie będziemy się nią zajmować .

Lista kroków:

Przykład:

teskt=bbabbbaabb, n=10

wzorzec=aab, m=3

dla i=1 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.

dla i=2 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.

dla i=3 nastąpi wejście do zagnieżdżonej pętli while, ale dla j=1 nastąpi wyjście, po tym wyjściu warunek if będzie niespełniony,

dla i=4..6 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.

dla i=7 nastąpi wejście do zagnieżdżonej pętli while, która wykonywana będzie aż do j=3, po tym wyjściu warunek if jest spełniony tzn. znaleziono dopasowanie.

dla i=8 nie nastąpi wejście do zagnieżdżonej pętli while, nie jest również spełniony warunek if.

dla i=9 nie jest spełniony główny warunek, algorytm zostaje zakończony.

Program:

public class AlgorytmN {

public static void main(String[] args) {

String wzorzec;

String tekst;

int m,n,i,j;

System.out.println("Podaj tekst");

tekst = Console.readString("?");

System.out.println("Podaj wzorzec");

wzorzec = Console.readString("?");

n = tekst.length();

m = wzorzec.length();

System.out.println("Indeksy wystapien wzorca w tekscie");

i=0;

while (i<=n-m)

{

j=0;

while ((j<m) &&

(wzorzec.charAt(j) == tekst.charAt(i+j))) j++;

if (j==m) System.out.println(i+1);

i++;

}

}

}