Sort przez wstawianie Pętla zewnętrzna wybiera ze zbioru Kolejne elementy o indeksach od n - 1 do 1, pętla wewnętrzna szuka dla wybranych elementów miejsca wstawienia na liście uporządkowanej, po znalezieniu, którego pętla zewnętrzna wstawia wybrany element na listę. Gdy pętla zewnętrzna przebiegnie wszystkie elementy o indeksach od n - 1 do 1, zbiór będzie posortowany.	for(j = N - 2; j >= 0; j--) { x = d[j]; i = j + 1; while((i < N) && (x > d[i])) { d[i - 1] = d[i]; i++; } d[i - 1] = x; }
	Sort przez wybieranie • Pętla zewnętrzna sterowana zmienna j wyznacza kolejne elementy zbioru o indeksach od 1 do n - 1, w których zostaną umieszczone elementy minimalne. Na początku tej pętli zakładamy, iż elementem minimalnym jest element d[j] i zapamiętujemy jego indeks w zmiennej pmin. • W pętli numer 2 sterowanej zmienna i porównujemy pozostałe elementy zbioru z elementem d[pmin]. Jeśli element zbioru d[i] jest mniejszy od elementu d[pmin], to znaleźliśmy nowy element minimalny. W takim przypadku zapamiętujemy jego pozycje w pmin i kontynuujemy pętle wewnętrzną. • Po zakończeniu pętli wewnętrznej pmin zawiera indeks elementu minimalnego. Zamieniamy miejscami element d[j] z elementem d[pmin]. Dzięki tej operacji element minimalny znajduje sie na swojej docelowej pozycji. Zwiększamy j przechodząc do kolejnego elementu zbioru i kontynuujemy pętle zewnętrzną.	for(j = 0; j < N - 1; j++) { pmin = j; for(i = j + 1; i < N; i++) if(d[i] < d[pmin]) pmin = i; x = d[pmin]; d[pmin] = d[j]; d[j] = x; }
	Sortowanie bąbelkowe • Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Zasada działania opiera sie na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operacje te wykonujemy dotąd, aż cały zbiór zostanie posortowany. • Sortowanie wykonywane jest w dwóch zagnieżdżonych pętlach. Pętla zewnętrzna nr 1 kontrolowana jest przez zmienna j. Wykonuje sie ona n - 1 razy. Wewnątrz pętli nr 1 umieszczona jest pętla nr 2 sterowana przez zmienna i. Wykonuje się również n - 1 razy. W efekcie algorytm wykonuje w sumie: • T1(n) = (n - 1)2 = n2 - 2n + 1 obiegów pętli wewnętrznej, po których zakończeniu zbiór zostanie posortowany.	for(j = 0; j < N - 1; j++) { for(i = 0; i < N - 1; i++) { if(d[i] > d[i + 1]) { x = d[i]; d[i] = d[i + 1]; d[i + 1] = x; } }}
	• Algorytm sortowania metoda Shella jest ulepszonym algorytmem sortowania przez wstawianie. Aby sie o tym przekonać, wystarczy spojrzeć na schemat blokowy. Kolorem szarym zaznaczone są na nim bloki, które dokładnie odpowiadają algorytmowi sortowania przez wstawianie. Jedyna modyfikacja jest wprowadzenie odstępu h zamiast liczby 1. • Po wyznaczeniu h rozpoczynamy pętle warunkowa nr 1. Pętla ta jest wykonywana dotąd, aż odstęp h przyjmie wartość 0. Wtedy kończymy algorytm, zbiór będzie posortowany. • Wewnątrz pętli nr 1 umieszczony jest opisany wcześniej algorytm sortowania przez wstawianie, który dokonuje sortowania elementów poszczególnych podzbiorów wyznaczonych przez odstęp h. Po zakończeniu sortowania podzbiorów odstęp h jest zmniejszany i następuje powrót na początek pętli warunkowej nr 1.	#include<stdio.h> #include<stdlib.h> int main(void) { int i=0, j, N, x, d[100], h; printf("Podaj liczby do posortowania\n"); while(getchar()!='n') { scanf("%d", &d[i]); i++; } N=i; i=0; for(h = 1; h < N; h = 3 * h + 1); h /= 9; if(!h) h++; while(h) { for(j = N - h - 1; j >= 0; j--) { x = d[j]; i = j + h; while((i < N) && (x > d[i])) { d[i - h] = d[i]; i += h; } d[i - h] = x; } h /= 3; } for(j=0; j<N; j++) { printf("%3d", d[j]); } printf("\n"); system("pause"); }
	Sortowanie przez scalanie • Wynaleziony w 1945 roku przez Johna von Neumanna algorytm sortowania przez scalanie jest algorytmem rekurencyjnym. • Wykorzystuje zasadę dziel i zwyciężaj, która polega na podziale zadania głównego na zadania mniejsze dotąd, aż rozwiązanie stanie sie oczywiste. Algorytm sortujący dzieli porządkowany zbiór na kolejne połowy dopóki taki podział jest możliwy (tzn. podzbiór zawiera co najmniej dwa elementy). Następnie uzyskane w ten sposób części zbioru rekurencyjnie sortuje tym samym algorytmem. Posortowane części łączy ze sobą za pomocą scalania tak, aby wynikowy zbiór był posortowany.
	Scalanie zbiorów uporządkowanych • Podstawowa operacja algorytmu jest scalanie dwóch zbiorów uporządkowanych w jeden zbiór również uporządkowany. Operacje scalania realizujemy wykorzystując pomocniczy zbiór, w którym bedziemy tymczasowo odkładac scalane elementy dwóch zbiorów. Ogólna zasada jest nastepujaca: • Przygotuj pusty zbiór tymczasowy • Dopóki żaden ze scalanych zbiorów nie jest pusty, porównuj ze soba pierwsze elementy każdego z nich i w zbiorze tymczasowym umieszczaj mniejszy z elementów usuwajac go jednoczesnie ze scalanego zbioru. • W zbiorze tymczasowym umiesc zawartosc tego scalanego zbioru, który zawiera jeszcze elementy. • Zawartosc zbioru tymczasowego przepisz do zbioru wynikowego i zakoncz algorytm.
Rekurencja • Obiekt zwany jest rekurencyjnym (ang. recursive), jeżeli czesciowo składa sie z siebie samego lub jego definicja odwołuje sie do jego samego. Rekursje spotykamy nie tylko w matematyce, ale także w życiu codziennym. • Rekursja jest szczególnie silnym narzedziem w definicjach matematycznych: • Liczby naturalne: a) 1 jest liczba naturalna; b) Nastepnik liczby naturalnej jest liczba naturalna. Funkcja silni n! (dla argumentów całkowitych, nieujemnych) 0! = 1; Jesli n>0, to n!=n*(n-1)! Siła rekursji wyraża sie w możliwosci definiowana nieskonczonego zbioru obiektów za pomoca skonczonego wyrażenia.	• Narzedziem umożliwiajacym tworzenie programów rekurencyjnych jest pojecie procedury (podprogramu). Pozwala ono nadac instrukcji nazwe, za pomoca której można uaktywnic te instrukcje. Jesli procedura P zawiera bezposrednie odwołanie do samej siebie, to P nazywa sie procedura bezposrednio rekurencyjna. Jeżeli P zawiera odwołanie do innej procedury Q, która zawiera bezposrednie lub posrednie odwołanie do P, to P nazywa sie procedura posrednio rekurencyjna. • Zazwyczaj z procedura wiaże sie pewien zbiór obiektów lokalnych, tj. zmiennych, stałych… zdefiniowanych lokalnie dla tej procedury i nie	istniejacych lub nie majacych poza nia znaczenia. Za każdym razem, gdy taka procedura jest uaktywniana rekurencyjnie, tworzy sie zbiór zmiennych lokalnych. • Algorytm wykorzystuje samego siebie ze zmienionym zestawem danych. • Jako przykład może posłużyc rekurencyjne obliczanie silni. Silnie liczby n należacej do zbioru liczb naturalnych definiujemy nastepujaco: • n! = 1 • 2 • 3 • ... • (n - 1) • n • Na przykład: 5! = 1 • 2 • 3 • 4 • 5 = 120
Przykładowy program #include <stdio.h> const int NMAX=15; long int silnia (long int n); int main() { long int n; long int sln[NMAX]; sln[0]=1; for (n=1;n<NMAX;n++) { sln[n]=n*sln[n-1]; printf(" sln[%ld]= %ld \n",n,sln[n]); printf(" silnia(%ld)= %ld \n",n,silnia(n)); } return 0; } long int silnia (long int n) { if (n<2) return 1; else return n*silnia(n-1); }	Dzieki rekurencji funkcja wyliczajaca wartosc silni staje sie niezwykle prosta. Najpierw sprawdzamy warunek zakonczenia rekurencji, tzn. sytuacje, gdy wynik dla otrzymanego zestawu danych jest oczywisty. W przypadku silni sytuacja taka wystapi dla n < 2 - silnia ma wartosc 1. Jesli warunek zakonczania rekurencji nie wystapi, to wartosc wyznaczamy za pomoca rekurencyjnego wywołania obliczania silni dla argumentu zmniejszonego o 1. Wynik tego wywołania mnożymy przez n i zwracamy jako wartosc silni dla n.
Sortowaniie szybkie • Algorytm sortowania szybkiego opiera sie na strategii "dziel i zwycieżaj" (ang. divide and conquer), która możemy krótko scharakteryzowac w trzech punktach: • DZIEL - problem główny zostaje podzielony na podproblemy • ZWYCIEżAJ - znajdujemy rozwiazanie podproblemów • POŁACZ - rozwiazania podproblemów zostaja połaczone w rozwiazanie problemu głównego	• Idea sortowania szybkiego jest nastepujaca: • (DZIEL): najpierw sortowany zbiór dzielimy na dwie czesci w taki sposób, aby wszystkie elementy leżace w pierwszej czesci (zwanej lewa partycja) były mniejsze lub równe od wszystkich elementów drugiej czesci zbioru (zwanej prawa partycja). • (ZWYCIEżAJ): każda z partycji sortujemy rekurencyjnie tym samym algorytmem. • (POŁACZ): połaczenie tych dwóch partycji w jeden zbiór daje w wyniku zbiór posortowany.
Tworzeniie partycji • Do utworzenia partycji musimy ze zbioru wybrac jeden z elementów, który nazwiemy piwotem. W lewej partycji znajda sie wszystkie elementy niewieksze od piwotu, a w prawej partycji umiescimy wszystkie elementy niemniejsze od piwotu. Położenie elementów równych nie wpływa na proces sortowania, zatem moga one wystepowac w obu artycjach. Również porzadek elementów w każdej z partycji nie jest ustalony. Jako piwot można wybierac element pierwszy, srodkowy, ostatni, mediane lub losowy. Dla naszych potrzeb wybierzemy element srodkowy: piwot d[(lewy + prawy) div 2] piwot - element podziałowy d[ ]- dzielony zbiór	lewy- indeks pierwszego elementu prawy - indeks ostatniego elementu Dzielenie na partycje polega na umieszczeniu dwóch wskazników na początku zbioru - i oraz j. Wskaznik i przebiega przez zbiór poszukujac wartości mniejszych od piwotu. Po znalezieniu takiej wartosci jest ona wymieniana z elementem na pozycji j. Po tej operacji wskaznik j jest przesuwany na nastepna pozycje. Wskaznik j zapamietuje pozycje, na która trafi nastepny element oraz na koncu wskazuje miejsce, gdzie znajdzie sie piwot.	W trakcie podziału piwot jest bezpiecznie rzechowywany na ostatniej pozycji w zbiorze. Po zakonczeniu podziału na partycje wskaznik j wyznacza pozycje piwotu. Lewa partycja zawiera elementy mniejsze od piwotu i rozciaga sie od poczatku zbioru do pozycji j - 1. Prawa partycja zawiera elementy wieksze lub równe piwotowi i rozciaga sie od pozycji j + 1 do konca zbioru.