Ćwiczenia 6 - Sortowanie cd.

1. Sortowanie bąbelkowe
   T.length ∈ N
   T[i] ∈ R
   

   BUBBLE-SORT(T)
   	for j = T.length downto 2
   		for i = 1 to j - 1
   			if T[i] > T[i + 1]
   				tmp = T[i]
   				T[i] = T[i + 1]
   				T[i + 1] = tmp
   

2. Scalanie dwóch ciągów uporządkowanych
   p,q,r ∈ N
   T[i] ∈ R
   

   MERGE(T,p,q,r)
   	i = p
   	j = q + 1
   	l = p
   	while i ≤ q AND j ≤ r
   		if T[i] ≤ T[j]
   			A[l] = T[i]
   			i = i + 1
   		else
   			A[l] = T[j]
   			j = j + 1
   		l = l + 1
   	while i ≤ q
   		A[l] = T[i]
   		i = i + 1
   		l = l + 1
   	while j ≤ r
   		A[l] = T[j]
   		j = j + 1
   		l = l + 1
   	for i = p to r
   		T[i] = A[i]
   

3. Sortowanie przez scalanie
   T.length, l, p ∈ N
   T[i] ∈ R
   

   MERGE-SORT(T,l,p)
   	if l < p
   		q = (l + p) DIV 2
   		MERGE-SORT(T,l,q)
   		MERGE-SORT(T,q + 1,p)
   		MERGE(T,l,q,p)
   

4. Sortowanie szybkie
   T.length, l, p ∈ N
   T[i] ∈ R
   

   DIV(T,l,p)
   	x = T[p]
   	i = l - 1
   	for j = l to p - 1
   		if T[j] ≤ x
   			i = i + 1
   			tmp = T[i]
   			T[i] = T[j]
   			T[j] = tmp
   	tmp = T[i + 1]
   	T[i + 1] = T[p]
   	T[p] = tmp
   	return i + 1
   

   QUICK-SORT(T,l,p)
   	if l < p
   		q = DIV(T,l,p)
   		QUICK-SORT(T,l,q - 1)
   		QUICK-SORT(T,q + 1,p)
   

5. Sortowanie przez zliczanie
   T.length ∈ N
   T[i] ∈ R
   k ∈ N i k < T.length
   

   COUNT-SORT(T,k)
   	for i = 1 to k
   		C[i] = 0
   	for i = 1 to T.length
   		C[T[i]] = C[T[i]] + 1
   	for i = 2 to k
   		C[i] = C[i] + C[i - 1]
   	for i = T.length downto 1
   		B[C[T[i]]] = T[i]
   		C[T[i]] = C[T[i]] - 1
   	for i = 1 to T.length
   		T[i] = B[i]