Temat 6. Algorytmy sortowania.

 

Porządkowanie: algorytmy, złożoność algorytmów (czasowa i pamięciowa), poprawność realizacji algorytmu (niezmienniki i zbieżniki).

 

Istnieje wiele różnych algorytmów sortowania. Aby móc je porównywać należy ustalić własności (kryteria) według których będziemy to robić. Najważniejsze z nich to:

 

- stopień skomplikowania algorytmu

- szybkość działania (złożoność obliczeniowa – optymistyczna, średnia i pesymistyczna)

- zapotrzebowanie na dodatkową pamięć (złożoność pamięciowa)

- stabilność algorytmu (czy elementy o jednakowych kluczach zachowają pierwotną kolejność)

- przydatność do sortowania różnych struktur danych (tablice, listy, pliki).

Oczywiście każdy z algorytmów może mieć wiele różnych realizacji. Raczej nie można powiedzieć, że istnieje jeden najlepszy algorytm (czy też jego realizacja), tak więc dobierając algorytm sortowania do konkretnego przypadku należy uwzględnić takie czynniki jak:

 

- rodzaj i wielkość porządkowanej struktury (tablica, lista, plik)

- złożoność porównania kluczy

- złożoność przepisywania elementów (wielkość elementu) - w javie ma to znaczenie tylko wtedy gdy tworzymy kopie elementów

- początkowe uporządkowanie danych (dane uporządkowane, losowe, prawie uporządkowane, odwrotnie uporządkowane, o tej samej wartości)

- wielkość dostępnej pamięci operacyjnej

- wymagania dotyczące stabilności itp.

 

Najpełniejszy przegląd zagadnień związanych z sortowaniem można znaleźć w:

Knuth D. E. The art of computer programming. Vol 3. Sorting and Searching.

 

Warto również zajrzeć do:

1.Wirth N. Algorytmy + struktury danych = programy.

2.Reingold E. M., Nievergelt J., Deo N. Algorytmy kombinatoryczne.

3.Aho A. V., Hopcroft J. E., Ullman J. D. Projektowanie i analiza algorytmów komputerowych.

4.Banachowski L., Kreczmar A. Elementy analizy algorytmów.

5.Banachowski L, Diks K, Rytter W Algorytmy i struktury danych.

6. Cormen T H, Leiserson Ch E, Rivest R L: Wprowadzenie do algorytmów.

7. Sedgewick R.: „Algorytmy w C++”

8. Bentley J.: „Perełki oprogramowania”

 

Większość (ale nie wszystkie) algorytmów ustala kolejność elementów na podstawie porównań wartości elementów. Możemy wykorzystać porządek naturalny (wyznaczony przez metodę compareTo) lub użyć odpowiednich komparatorów. Drugie rozwiązanie jest bardziej uniwersalne i je będziemy wykorzystywać.

 

Aby sortować w porządku naturalnym elementy sorowane muszą implementować interface Comparable:

 

public interface Comparable

{ public int compareTo(Object other); }

 

czyli mieć zdefiniowaną metodę compareTo (wynik <0 oznacza this<other; = 0 this = other i >0 this > other).

W drugim przypadku musimy zaimplementować interface Comparator:

 

public interface Comparator

{ public int compare(Object left, Object right) throws ClassCastException; }

 

Metoda compare ma wyniki takie jak compareTo.

Można zdefiniować komparator wyznaczający porządek naturalny:

 

package sorting;

public final class NaturalComparator implements Comparator {

// wykorzystuje wzorzec singleton

public static final NaturalComparator INSTANCE = new NaturalComparator();

 

private NaturalComparator() { }

 

public int compare(Object left, Object right) throws ClassCastException

{ return ((Comparable) left).compareTo(right); }

}

 

Równie łatwo można utworzyć komparator odwrotny:

 

package sorting;

public class ReverseComparator implements Comparator {

// podstawowy komparator

private final Comparator _comparator;

 

public ReverseComparator(Comparator comparator)

{ _comparator = comparator; }

 

public int compare(Object left, Object right) throws ClassCastException

{ return _comparator.compare(right, left); }

}

 

W przypadkach bardziej złożonych można komplikować metodę compare lub zbudować komparator złożony wykorzystujący istniejące, proste komparatory. Pozwala to czasami uzyskać stabilne sortowanie nawet dla algorytmów niestabilnych.

package sorting;

import iterators.Iterator;

import lists.ArrayList;

import lists.List;

 

public class CompoundComparator implements Comparator {

//tablica komparatorów; od najważniejszego

private final List _comparators = new ArrayList();

 

public void addComparator(Comparator comparator)

{ _comparators.add(comparator); }

 

public int compare(Object left, Object right) throws ClassCastException {

int result = 0;

Iterator i = _comparators.iterator();

for (i.first();!i.isDone()&&

(result = ((Comparator) i.current()).compare(left, right))==0; i.next());

return result;

}

}

 

Algorytmy sortowania.

Rozpoczynamy od algorytmów klasycznych (o kwdratowej złożoności średniej).

 

- Na początek najprostszy, ale najgorszy algorytm sortowania przez zamianę (BubbleSort)

 

Idea algorytmu: 1. powtarzaj aż do całkowitego uporządkowania ciągu

porównuj parę elementów i jeśli ich kolejność jest nieprawidłowa to je zamień

 

Jego podstawowa realizacja wygląda tak:

 

Najpierw definicja interfejsu ułatwiającego wykorzystanie algorytmów sortowania:

package sorting;

import lists.List;

 

public interface ListSorter

// wynikiem jest nowa lista lub stara posortowana

{ public List sort(List list); }

 

Teraz sortowanie bąbelkowe:

 

package sorting;

import lists.List;

 

public class BubbleSort implements ListSorter {

private final Comparator _comparator;

 

public BubbleSort(Comparator comparator)

{ _comparator = comparator; }

// wynikiem jest posortowana lista pierwotna

 

// najbardziej prymitywna wersja

public List sort(List list) {

int size = list.size();

 

for (int pass = 1; pass < size; ++pass) {

for (int left = 0; left < (size - pass); ++left) {

int right = left + 1;

if (_comparator.compare(list.get(left), list.get(right)) > 0)

swap(list, left, right);

}

}

return list;

}

 

private void swap(List list, int left, int right) {

Object temp = list.get(left);

list.set(left, list.get(right));

list.set(right, temp);

}

}

 

Jest to algorytm prosty ale wolny. Można go przyspieszyć na kilka sposobów:

- ograniczyć pętlę zewnętrzną przez wykrywanie czy ciąg nie został uporządkowany wcześniej

- ograniczyć pętlę wewnętrzną przez zapamiętanie pozycji ostatniej zamiany w poprzednim przebiegu

- zastąpić ciąg zamian elementów ciągiem przepisań

- przechodząc ciąg na przemian w obu kierunkach (ShakerSort).

 

 

Wprowadzając pierwsze trzy usprawnienia otrzymujemy:

 

package sorting;

import lists.List;

 

public class BubbleSort1 implements ListSorter {

private final Comparator _comparator;

 

public BubbleSort1(Comparator comparator)

{ _comparator = comparator; }

// wynikiem jest posortowana lista pierwotna

 

//wersja ulepszona wykorywająca wcześniejsze uporządkowanie

public List sort(List list) {

int lastSwap = list.size()-1; //pozycja ostatniej zamiany

while(lastSwap>0){

int end=lastSwap;

lastSwap=0;

for (int left = 0; left < end; ++left) {

if (_comparator.compare(list.get(left), list.get(left+1)) > 0)

{ //ciąg zamian jest zastąpiony ciągiem przepisań

Object temp=list.get(left);

while(left<end && _comparator.compare(temp, list.get(left+1)) > 0)

{ list.set(left, list.get(left+1)); left++; }

lastSwap=left;

list.set(left,temp);

}

}

}

return list;

}

}

Przykład sortowania listy zawodników według nazwisk i punktów:

//klasa zawodnik uzupełniona o metody porównujące

package iteracje;

import iterators.*;

 

public class Zawodnik

{String nazw;

int punkty;

public Zawodnik(String n, int p)

{nazw=n; punkty=p;}

 

public String toString() { return nazw+" "+punkty;}

 

public int porNazw(Zawodnik z) { return nazw.compareTo(z.nazw);}

 

public int porPunkty(Zawodnik z) { return punkty-z.punkty;}

}

//klasy komparatorów

package iteracje;

import sorting.*;

public final class NameComparator implements Comparator {

// wykorzystuje wzorzec singleton

public static final NameComparator INSTANCE = new NameComparator();

 

private NameComparator() { }

 

public int compare(Object left, Object right) throws ClassCastException

{ return ((Zawodnik)left).porNazw((Zawodnik)right); }

}

 

package iteracje;

import sorting.*;

 

public final class PointsComparator implements Comparator {

// wykorzystuje wzorzec singleton

public static final PointsComparator INSTANCE = new PointsComparator();

 

private PointsComparator() { }

 

public int compare(Object left, Object right) throws ClassCastException

{ return ((Zawodnik)left).porPunkty((Zawodnik)right); }

}

 

//sortowanie listy zawodników; najpierw wg nazwisk a potem wg punktów

package iteracje;

 

import iterators.*;

import lists.*;

import sorting.*;

 

public class Zawody

{ List lista = new ArrayList();

public Zawody() { }

 

public void testBubbleSort()

{ // wypełnienie listy

 

//sortowanie wg nazwisk

ListSorter ls=new BubbleSort(NameComparator.INSTANCE);

lista=ls.sort(lista);

System.out.println(lista);

System.out.println();

// wg punktów

ls=new BubbleSort(PointsComparator.INSTANCE);

lista=ls.sort(lista);

System.out.println(lista);

System.out.println();

//wg punktów i nazwisk (przy równych punktach decyduje nazwisko)

Comparator cc=new CompoundComparator();

cc.add(NameComparator.INSTANCE);

cc.add(PointComparator.INSTANCE);

 

ls=new BubbleSort(cc);

lista=ls.sort(lista);

System.out.println(lista);

System.out.println();

}

 

Wolne działanie tego algorytmu wynika z faktu że pojedyncza zamiana sąsiednich elementów zmienia stopień nieuporządkowania ciągu (liczony jako liczba inwersji - ile razy wartość większa występuje przed mniejszą) tylko o 1. Zamiana elementów odległych o h mogłaby zmniejszyć liczbę inwersji nawet o h.

 

Wykorzystał to w 1959 roku Shell do opracowania sortowania z malejącymi przyrostami (ShellSort)

Idea: Wybieramy ciąg malejących przyrostów h₁,...,h_t spełniający warunek: h_t=1 oraz h_i < h_j dla i >j;

Dla i od 1 do t wykonaj

Przyjmij przyrost h_i

Przez proste wstawianie (lub zamianę) uporządkuj wszystkie podciągi elementów odległych od siebie o h_i

 

Niestety nie wiadomo jak dobrać dla konkretnego przypadku najlepszy ciąg przyrostów. Ponieważ skomplikowanie tego algorytmu nie jest duże, a złożoność obliczeniowa nie jest najgorsza więc chętnie jest stosowany praktycznie.

Przykładowa realizacja z ciągiem przyrostów: 1,4,13,40,121,364,1093,3280,9841.......(h_j+1 =3* h_j +1), liczbę przyrostów wyznacza się tak aby sortowane podciągi zawierały conajmniej 3 elementy.

 

package sorting;

import lists.List;

 

public class ShellSort implements ListSorter {

private final Comparator _comparator;

 

// przyrost

private int _h = 1;

 

public ShellSort(Comparator comparator)

{ _comparator = comparator; }

 

// ciąg przyrostów: h[0]=1; h[i]=3*h[i-1]+1

// minimalna długość podciągu: 3

// sortowanie podciągów: InsertSort

 

public List sort(List list) {

int size=list.size();

hMaxSet(size); //znajdź największy przyrost

do { //dla malejących kolejno przyrostów

for(int i=_h;i<size;i++) //wstawiaj kolejne elementy na podlistach

insert(list,i);

}while ((_h/=3) >0);

return list;

}

 

private void hMaxSet(int size){

while(_h < size/9)

_h=3*_h+1;

}

private void insert(List list, int poz) {

Object temp,value=list.get(poz);

while(poz>=_h && _comparator.compare(value,temp=list.get(poz-_h)) < 0)

{list.set(poz,temp); poz-=_h; }

list.set(poz,value);

}

}

Dla tego ciągu liczba porównań wynosi O(n^3/2). Inne stosowane ciągi można znaleźć w książce Sedgewicka.

 

Dwa inne elementarne (klasyczne) algorytmy: sortowanie przez wstawianie (InsertSort) oraz sortowanie przez wybór (SelectSort).

 

1. Sortowanie przez wstawianie - sposób preferowany przez karciarzy

idea: 1. powtarzaj n - razy

weź kolejny element z ciągu nieuporządkowanego

wstaw go na właściwe miejsce w ciągu uporządkowanym

 

2. Sortowanie przez wybór

idea: 1. powtarzaj n - razy

zabierz najmniejszy element z ciągu nieuporządkowanego

wpisz go na koniec ciągu już uporządkowanego

 

Są to dwa bardzo proste, ale wolne (złożoność kwadratowa) algorytmy – stosowane często do niewielkich ciągów. Mimo podobnej budowy mają bardzo różne własności (jakie? patrz literatura lub słuchaj wykładu).

 

Przykładowe realizacje:

package sorting;

import lists.List;

 

public class InsertSort implements ListSorter {

private final Comparator _comparator;

 

public InsertSort(Comparator comparator) { _comparator = comparator; }

 

public List sort(List list) {

for (int i = 1; i < list.size(); ++i) {

Object value = list.get(i),temp;

int j;

for (j = i; j > 0&& _comparator.compare(value, temp=list.get(j - 1))< 0; --j)

list.set(j,temp);

list.set(j, value);

}

return list;

}

}

 

Jak widać algorytm jest bardzo prosty, nie potrzebuje dodatkowej pamięci. Jest jednak wolny (dużo porównań i tyle samo przepisań). Silnie zależy od natury porządkowanego ciągu (lubi uporządkowane ciągi), zachowuje przy tym naturalną kolejność elementów równych. Można poprawić jego efektywność przez zmniejszenie liczby porównań (wyszukiwanie binarne).

package sorting;

import lists.List;

 

public class SelectSort implements ListSorter {

private final Comparator _comparator;

 

public SelectSort(Comparator comparator) { _comparator = comparator; }

 

public List sort(List list) {

int size = list.size();

for (int slot = 0; slot < size - 1; ++slot) {

int smallest = slot;

for (int check = slot + 1; check < size; ++check)

if (_comparator.compare(list.get(check), list.get(smallest)) < 0)

smallest = check;

swap(list, smallest, slot);

}

return list;

}

private void swap(List list, int left, int right) {

if (left!= right) { // podejście optymisty

Object temp = list.get(left);

list.set(left, list.get(right));

list.set(right, temp);

}

}

}

 

 

Prosty, wolny (ale ma najmniejszą możliwą liczbę przepisań),nie zależy od uporządkowania danych, nie jest stabilny - czyli nie zachowuje kolejności elementów równych. Można go przyspieszyć znajdując jednocześnie elementy maks i min (szybciej można znaleźć maks i min jednocześnie niż szukając ich po kolei) wystarczy 1.5n porównań zamiast 2n.

 

 

Złożone algorytmy sortowania (liniowo-logarytmiczne): sortowanie szybkie (QuickSort) sortowanie przez scalanie (MergeSort) oraz sortowanie stogowe (HeapSort).

Sortowanie szybkie

Opracowany w 1962 roku przez Hoare'a, jest jednym z najlepiej poznanych (matematycznie) algorytmów. Oparty jest na zasadzie "divide et impera". Jej sens jest następujący: Aby rozwiązać problem wielkości N, rozwiąż rekurencyjnie dwa podproblemy wielkości N/2 i połącz ich wyniki by otrzymać rozwiązanie całego problemu.

 

Idea algorytmu jest następująca:

1. wybierz dowolny element z porządkowanego ciągu - X

2. podziel ciąg na podciąg zawierający elementy mniejsze od X i drugi zawierający pozostałe

3. tak samo posortuj pierwszy podciąg

4. posortuj drugi podciąg tą samą metodą

5.połącz rozwiązania

 

Sortowanie przez scalanie

idea: 1. podziel ciąg na dwa podciągi

2. uporządkuj pierwszy podciąg tą samą metodą

3. uporządkuj drugi podciąg tą samą metodą

4. połącz podciągi zachowując uporządkowanie

 

Przykładowe realizacje algorytmu szybkiego sortowania (różnią się sposobem podziału na podciągi):

- podział jednostronny zaproponowany przez Lomuto (najprostszy)

 

package sorting;

import lists.List;

 

public class QuickSort implements ListSorter {

private final Comparator _comparator;

 

public QuickSort(Comparator comparator) { _comparator = comparator; }

 

// wynikiem jest posortowana oryginalna lista

public List sort(List list) {

quicksort(list, 0, list.size() - 1);

return list;

}

 

private void quicksort(List list, int startIndex, int endIndex) {

if (endIndex > startIndex) {

int partition = partition(list, startIndex, endIndex);

quicksort(list, startIndex, partition);

quicksort(list, partition + 1, endIndex);

}

}

// podział według Lomuto

private int partition(List list, int left, int right) {

//jako element dzielący bierzemy ostatni

Object value=list.get(right);

int i=left-1;

while (left <= right){

if(_comparator.compare(list.get(left), value) <= 0)

swap(list, ++i,left);

++left;

}

 

return i<right? i:i-1;

}

 

private void swap(List list, int left, int right) {

if (left!= right) {

Object temp = list.get(left);

list.set(left, list.get(right));

list.set(right, temp);

}

}

}

- podział dwustronny (szybszy ale bardziej skomplikowany) - lekko zmodyfikowana wersja Harrisa i Rossa (styl!!)

// tylko metody które uległy zmianie

private void quicksort(List list, int startIndex, int endIndex) {

if (endIndex > startIndex) {

//jako element dzielący bierzemy ostatni

Object value=list.get(endIndex);

int partition = partition(list, value, startIndex, endIndex - 1);

if (_comparator.compare(list.get(partition), value) < 0)

++partition;

swap(list, partition, endIndex);

 

quicksort(list, startIndex, partition - 1);

quicksort(list, partition + 1, endIndex);

}

}

 

//styl!!

private int partition(List list, Object value, int left, int right) {

while (left < right) {

if(_comparator.compare(list.get(left), value) < 0)

{++left; continue;}

if(_comparator.compare(list.get(right), value) >= 0)

{--right; continue;}

swap(list, left, right); ++left;

}

return left;

}

 

- poprawiona wersja (w porządnym strukturalnym stylu)

private void quicksort(List list, int startIndex, int endIndex) {

if (endIndex > startIndex) {

//jako element dzielący bierzemy ostatni

int partition = partition(list, startIndex, endIndex);

quicksort(list, startIndex, partition - 1);

quicksort(list, partition + 1, endIndex);

}

}

 

private int partition(List list, int left, int right) {

Object value=list.get(right);

int i=left-1,j=right;

while (i < j) {

while(_comparator.compare(list.get(++i), value) < 0);

while((j>left) &&_comparator.compare(list.get(--j), value) > 0);

if(i < j)

swap(list, i, j);

}

swap(list,i,right);

return i;

}

 

Program jest prosty, bardzo szybki, potrzebuje niestety pamięci dla wywołań rekurencyjnych (można zmniejszyć głębokość rekurencji przez odpowiednie modyfikacje, albo zrealizować wersję iteracyjną), Jest jednak silnie zależny od początkowego uporządkowania ciągu (paradoksalnie, najgorszym przypadkiem jest ciąg już uporządkowany; również gdy wartości wielu elementów się powtarzają działa wolno).

Możliwości usprawnień:

1. efektywność tego algorytmu jest uzależniona od równomierności i szybkości podziału na podciągi – przegląd różnych metod podziału można znaleźć w {Bentley J. – „Perełki oprogramowania”]

2. QuickSort jest wyraźnie lepszy od innych przy długich ciągach, stąd pomysł aby przerywać rekurencję przy ciągach krótszych od M, a następnie wykorzystać prosty algorytm do ostatecznego posortowania (ciąg jest już prawie uporządkowany, więc dobry będzie InsertSort)

3. Można pozbyć się rekurencji używając własnego stosu do zapamiętania ciągów do posortowania, jeśli zastosujemy zasadę „odkładaj na stos dłuższy z podciągów, a krótszy obsłuż od razu” to zapewnimy sobie co najwyżej logarytmiczna wysokość stosu (normalnie może być liniowa – w najgorszym przypadku)

 

Prosta rekurencyjna realizacja algorytmu sortowania przez scalanie (wersja zstępująca - podział ciągu na coraz mniejsze podciągi, a następnie ich stopniowe scalanie):

 

package sorting;

import iterators.Iterator;

import lists.ArrayList;

import lists.List;

 

public class MergeSort implements ListSorter {

private final Comparator _comparator;

 

public MergeSort(Comparator comparator) { _comparator = comparator; }

 

// wynikiem jest nowa lista

public List sort(List list)

{ return mergesort(list, 0, list.size() - 1); }

 

private List mergesort(List list, int startIndex, int endIndex) {

if (startIndex == endIndex) {

List result = new ArrayList();

result.add(list.get(startIndex));

return result;

}

int splitIndex = startIndex + (endIndex - startIndex) / 2;

return merge(mergesort(list, startIndex, splitIndex),

mergesort(list, splitIndex + 1, endIndex));

}

 

private List merge(List left, List right) {

List result = new ArrayList();

Iterator l = left.iterator(); Iterator r = right.iterator();

l.first(); r.first();

while (!l.isDone() &&!r.isDone()) {

if (_comparator.compare(l.current(), r.current()) <= 0)

{ result.add(l.current()); l.next(); }

else { result.add(r.current()); r.next(); }

}

while(!l.isDone())

{ result.add(l.current()); l.next(); }

while(!r.isDone())

{ result.add(r.current()); r.next(); }

return result;

}

}

 

Można zastosować iteracyjny algorytm wstępujący (podstawowy jest zstępujący): podziel listę na listy jednoelementowe i umieść je w kolejce, następnie do uzyskania jednej listy wykonuj DoKolejki(Merge(Zkolejki,Zkolejki)) – w bardziej rozbudowanej wersji możemy w kolejce umieszczać nie pojedyncze elementy a serie (już uporządkowane podciągi kolejnych elementów) - wymaga to tylko przebudowy metody createQueue.

 

package sorting;

import iterators.Iterator;

import queues.*;

import lists.List;

 

 

public class IterativeMergeSort implements ListSorter {

private final Comparator _comparator;

public IterativeMergeSort(Comparator comparator) { _comparator = comparator; }

 

public List sort(List list)

{ return mergeSublists(createQueue(list)); }

 

private List mergeSublists(Queue q)

while (q.size() > 1)

q.enqueue(mergePair((List)q.dequeue(),(List)q.dequeue());

return (List)q.dequeue();

}

 

private Queue createQueue(List list) {

Queue result = new ListFifiQueue();

Iterator i = list.iterator();

i.first();

while (!i.isDone()) {

List singletonList = new ArrayList(1);

singletonList.add(i.current());

result.enqueue(singletonList);

i.next();

}

return result;

}

 

private List mergePair(List left, List right) {

List result = new ArrayList(left.size()+right.size());

Iterator l = left.iterator(); Iterator r = right.iterator();

l.first(); r.first();

while (!l.isDone() &&!r.isDone()) {

if (_comparator.compare(l.current(), r.current()) <= 0)

{ result.add(l.current()); l.next(); }

else { result.add(r.current()); r.next(); }

}

while(!l.isDone())

{ result.add(l.current()); l.next(); }

while(!r.isDone())

{ result.add(r.current()); r.next(); }

return result;

}

}

Sortowanie stogowe

Opis stogu i definicje metod realizujących działania na stogowej kolejce priorytetowej – (będzie) można znaleźć w wykładzie o kolejkach priorytetowych.

 

package sorting;

 

import iteration.Iterator;

import lists.ArrayList;

import lists.List;

import queues.HeapPriorityQueue;

import queues.Queue;

 

public class HeapSort implements ListSorter {

private final Comparator _comparator;

public HeapSort(Comparator comparator) {_comparator = comparator;}

 

public List sort(List list) {

Queue queue = createPriorityQueue(list);

List result = new ArrayList(list.size());

while (!queue.isEmpty()) {

result.add(queue.dequeue());

}

return result;

}

 

private Queue createPriorityQueue(List list) {

Comparator comparator = new ReverseComparator(_comparator);

Queue queue = new HeapPriorityQueue(comparator);

Iterator i = list.iterator();

i.first();

while (!i.isDone()) {

queue.enqueue(i.current());

i.next();

}

return queue;

}

}

 

Jeden z szybszych (ale wolniejszy od sortowania szybkiego) algorytmów (złożoność O(N*log N)),w porównaniudo najbardziej znanego sortowania szybkiego nie jest rekurencyjny (łatwiej go analizować), nie potrzebuje dodatkowej pamięci (rekurencja zawsze jej zużywa sporo) i nie jest wrażliwy na uporządkowanie danych wejściowych. Można go usprawnić optymalizując metody obsługi stogu, ale pogarsza się w ten sposób jego czytelność. Czy to się opłaca zależy od stopnia przyspieszenia i potrzeb.

 

1. można przyspieszyć fazę budowy stogu (do O(n)) – przez opuszczanie kolejnych elementów od (n div 2) do 0 na dół

2. można zmniejszyć liczbę porównań w fazie rozbierania stogu wykorzystując spostrzeżenie Floyda, że ostatni element wstawiany w miejsce korzenia prawie zawsze opada na dno stogu, będzie więc szybciej jeżeli będziemy schodzić od wierzchołka do dna przesuwając w górę większego z synów (na każdym poziomie), na wolne miejsce wstawiamy ostatni element stogu i przesuwamy go WGórę (rzadko zachodzi taka potrzeba)

Zadania:

17) Przeanalizuj zachowanie poszczególnych algorytmów sortowania przy porządkowaniu ciągu liter SORTOWANIE JEST PROSTE, zwróć uwagę na liczbę porównań i przepisań oraz stabilność.

18) Na wykładzie przedstawiono uniwersalne algorytmy (umożliwiające sortowanie list bez względu na ich implementację). Zaproponuj bezpośrednie (definiując odpowiednie struktury danych i potrzebne metody w jednej klasie) implementacje algorytmów. Który sposób daje prostszy kod? Co z efektywnością?

19) Jeśli znamy kryterium początkowego sortowania można łatwo (przez wykorzystanie odpowiedniego komparatora złożonego) doprowadzić do stabilności każdego z algorytmów sortowania. Czy można zaproponować uniwersalne rozwiązanie zapewniające zachowanie stabilności?

 

Algorytmy sortowania specyficznych typów danych – bez porównywania elementów.

Sortowanie przez rozdział

Stosowany wtedy gdy porządkowane elementy (ich klucze) pochodzą z niezbyt dużego zbioru z wyznaczonym porządkiem liniowym. Załóżmy że klucze mają wartości liczbowe od 1 do M. Elementów do uporządkowania jest N. Zazwyczaj N >> M. Utwórzmy strukturę M kolejek.

 

idea: 1. powtarzaj n - razy

weź kolejny element i umieść go w kolejce wyznaczonej przez wartość klucza

(jeśli klucz ma wartość i to w i-tej kolejce)

2. wyprowadź (połącz) wszystkie kolejki

 

 

1 - kubełkowe (BucketSort) [Aho,Banachowski]

 

Stosowane gdy wartości porządkowanych elementów pochodzą ze skończonego zbioru wartości np 1.. M. Wykorzystując kolejkę priorytetową z ograniczonym zbiorem wartości priorytetów (patrz wykład o kolejkach) możemy zapisać następujący algorytm (zakładamy, że najmniejsza wartość elementu daje najwyższy priorytet):

 

1. for (i =0; i<n; i++) DoKolejki(el[i]);

2. for (i=0; i<n; i++) ZKolejki(element)

Drukuj(element)

 

Gdy stosujemy ten algorytm do porządkowania tablicy zużywamy dużo dodatkowej pamięci (tyle ile zajmuje tablica + struktura kolejki), z tego względu algorytm nadaje się bardziej do sortowania list.

2 - wielolistowe (uogólnienie kubełkowego) [Banachowski]

 

W poprzednim przypadku mieliśmy do czynienia ze skończonym zbiorem wartości elementu. Rozważmy ciąg w którym elementy mają ograniczone wartości np. 0<=el < X, ale są liczbami rzeczywistymi (zbiór możliwych wartości jest nieskończony). Możemy wówczas wykorzystać tablicę M kolejek priorytetowych (o nieskończonym zbiorze wartości priorytetów (p.wykł. 3).

1. for (i=0; i<n; i++)

pr=floor (el[i]/X*M)

DoKolejki(pr,el[i])

2. for (pr=0; pr <M;pr++)

while (! PustaKolejka(pr))

ZKolejki(pr,elem)

Drukuj(elem)

 

Oba algorytmy są bardzo szybkie. Ciekawe, że w alg.1 nie wykonuje się żadnych porównań (a w 2 stosunkowo niewiele - przy wstawianiu do kolejki)

 

3 - pozycyjne (RadixSort) [Aho]

 

Sytuacja jest bardziej skomplikowana gdy klucz elementu jest określony przez ciąg P wartości z zakresu 0: M-1.

 

Możemy wykorzystać tablicę M zwykłych (FIFO) kolejek. Zakładając że mamy procedurę PolaczKolejki, która tworzy listę dołączając na jej koniec kolejne kolejki od 1 do P otrzymujemy następujący algorytm:

 

1. for(nrpoz=P; nrpoz >=0; nrpoz--)

for(i= 0; i<N;i++)

DoKolejki(el[i].klucz[nrpoz],el[i])

PolaczKolejki

 

UWAGA: oczywiście klucze (w alg. 1 i 3) nie muszą być liczbami całkowitymi (przyjęto tak dla uproszczenia), co więcej zakresy wartości dla poszczególnych pozycji klucza (alg. 3) mogą być różne.

 

 

Sortowanie przez zliczanie

idea: dla każdego elementu ciągu

oblicz ile jest elementów od niego mniejszych,

umieść element na wyznaczonej w ten sposób pozycji ciągu wynikowego.

 

Uwaga: naiwna realizacja tego algorytmu daje złożoność O(n²)

 

Realizacja algorytmu sortowania przez zliczanie (CountingSort) [Cormen]

Zakładamy, że każdy z n sortowanych elementów jest liczbą całkowitą z przedziału od 0 do K-1. Dane są umieszczone w tablicy A, wynik zapisujemy w tablicy C, używamy również pomocniczej tablicy liczników B.

 

void CountingSort(Tablica a, Tablica c, int n)

{ int b[K],i;

for(i=0;i<K;i++) b[i]=0;

for(i=0; i<n;i++) b[a[i]]++;

for(i=1;i<n;i++) b[i]+=b[i-1];

for (i=n-1;i>=0;i--) c[(b[a[i]]--]=a[i];

}

 

Jest to stabilny algorytm o złożoności O(n+k).

 

Sortowanie zewnętrzne - przeprowadzane bezpośrednio na danych umieszczonych w plikach.

 

Algorytmy tej klasy (wymienione poniżej) nie będą omawiane na wykładzie (ich szczegółowy opis można znaleźć w [Wirth "Algorytmy + Struktury Danych = Programy]). Dlaczego? Algorytmy te (co prawda efektywne ale dość skomplikowane) powstały przy założeniu, że sortowany ciąg znajduje się w pliku o dostępie sekwencyjnym (jego elementy można odczytywać tylko kolejno) i jest na tyle duży, że nie mieści się w całości w pamięci operacyjnej programu. Od czasu ich powstania sytuacja się nieco zmieniła:

1. znacznie zwiększyła się pamięć operacyjna dostępna dla programu,

2. używane pliki pozwalają na dostęp bezpośredni (w dowolnej kolejności - Seek) do ich elementów.

Czynnik drugi pozwala efektywnie wykorzystywać pliki indeksowe (specjalne pliki pokazujące uporządkowanie elementów pliku głównego). Przykład wykorzystania pliku indeksowego zostanie omówiony później.

Z kolei zwiększenie pamięci powoduje, że większość wykorzystywanych przez nas plików mieści się w pamięci, jeśli nie to jest duże prawdopodobieństwo, że zmieści się struktura zawierająca tylko klucz (zazwyczaj stanowi on niewielką część elementu pliku) i położenie elementu w pliku (numer rekordu) - wówczas wystarczy posortować taką strukturę i zgodnie z uporządkowaniem przepisać plik.

 

1 Sortowanie przez łączenie proste

2 Sortowanie przez łączenie naturalne

3 Sortowanie przez wielokierunkowe łączenie wyważone

Sortowanie polifazowe