Ćwiczenia 6 - Sortowanie

1. Napisz definicję procedury sortowania tablicy A[1..n] zawierającej liczby przez porównanie każdej pary elementów tablicy.
2. Podać definicję procedury sortującej tablicę A[1..n] przez wybór elementów minimalnych.
   

   procedure MINIMUM-3(A,d,g,l)
   		integer d,g,l
   		real min
   		real array A[1..n]
   	min = A[d]
   	l = d
   	for i = d + 1 to g
   		if A[i] < min
   			min = A[i]
   			l = i

   .
3. Zapisać definicję procedury sortowania bąbelkowego tablicy A[1..n].
4. Napisz algorytm sortowania przez wstawianie tablicy A[1..n].
5. Napisz algorytm sortowania przez scalanie tablicy A[1..n].

   procedure SCAL-1(A,p,q,r)
   		integer p,q,r
   		real array A[1..r]
   		integer i,j,l
   		real array B[1..r]
   	i = p
   	j = q + 1
   	l = p
   	while (i ≤ q) and (j ≤ r)
   		if A[i] ≤ A[j]
   			B[l] = A[i]
   			i = i + 1
   		else
   			B[l] = A[j]
   			j = j + 1
   		l = l + 1
   	while i ≤ q
   		B[l] = A[i]
   		i = i + 1
   		l = l + 1
   	while j ≤ r
   		B[l] = A[j]
   		j = j + 1
   		l = l + 1
   	for i = p to r
   		A[i] = B[i]

   .
6. Napisz algorytm sortowania szybkiego tablicy A[1..n].

   procedure PODZIEL(A,p,r,q)
   		integer p,r,q,i
   		real array A[1..r]
   		real x
   	x = A[r]
   	i = p - 1
   	for j = p to r - 1
   		if A[j] ≤ x
   			i = i + 1
   			A[i] <-> A[j]
   	A[i + 1] <-> A[r]
   	q = i + 1

   .
7. Napisz algorytm sortowania przez zliczanie tablicy A[1..n].