Powrót

Insertsort (sortowanie przez wstawianie)

Algorytm ten nie różni się wiele od poprzedniego. Tu podchodzimy do tego problemu od drugiej strony. Mianowicie na początku traktujemy pierwszy element tablicy jako dobrze posortowany ciąg. W kolejnych iteracjach zwiększamy nasze pole widzenia o jeden element. Jeśli się okaże, że jest on źle ułożony względem poprzednich, zamieniamy go z sąsiadami, do momentu gdy znajdzie się na miejscu. Teraz przykład.

	public static void Sort(int[] array) {

            for (int startPointer = 1; startPointer < array.Length; startPointer++) {

                int pointer = startPointer;

                while (pointer > 0 && array[pointer] < array[pointer - 1]) {
                    int temp = array[pointer];
                    array[pointer] = array[pointer - 1];
                    array[pointer - 1] = temp;
                    pointer--;
                }
            }
        }
	

startPointer to jest wskaźnik na najdalszy element jaki musimy rozpatrzeć. W każdym obrocie pętli przesuwamy go o krok dalej. Natomiast pętla wewnętrzna przesuwa element na który wskazuje startPointer w lewo do momentu gdy będzie dobrze uporządkowany. Dodatkowy warunek pointer > 0 gwarantuje nam, że jeśli rozpatrzamy najmniejszy element, to nie wyskoczymy poza tablicę. To chyba tyle wyjaśnień. Zbadajmy szybkość działania.

Nie trudno zauważyć, że szybkość tego algorytmu jest identyczna jak sortowania bąbelkowego. Przeanalizujmy go (tak jak poprzednio) od końca. W ostatnim obrocie wykonujemy conajmniej n - 1 porównań. W przedostatnim n - 2, itd. W pierwszym 1 porównanie, więc znowu wzór na sumę ciągu arytmetycznego i dostaniemy (n * (n - 1)) / 2.

Oczywiście widać, że nie zawsze będzie tych operacji aż tyle. Znowu będzie źle jeśli ciąg jest posortowany odwrotnie. Teraz zobaczymy dużo ciekawsze i przede wszystkim szybsze algorytmy.

Sposób użycia:

	using Infoporadnik.Sort;
	.
	.
	.
	int[] tablica = new int[5] = {4, 2, 1, 5, 3};
	InsertSort.Sort(tablica);
	

Sposób użycia dla wersji generycznej:

	using Infoporadnik.Sort.Generic;
	.
	.
	.
	MojObiekt[] tablica = new MojObiekt[2] = {new MojObiekt(), new MojObiekt() };
	InsertSort.Sort<MojObiekt>(tablica);
	

Uwaga! Obiekty muszą implementować interfejs IComparable.

Powrót