Rendező algoritmusok

Polynomial runtime algorithms:

Insertionsort(A)
	for j=2 to length[A]
		do key=A[j]
		>insert A[j] into the sorted sequence A[1...j-1]
		i=j-1
		while i>0 and A[i]>key
			do A[i+1]=A[i]
				i<i-1
		A[i+1]=key

Best case: O(n^2) Avarage case: O(n^2) Worst case: O(n^2)


Selectionsort(A)
for i = 0 to length[A] - 1
    for  j = i+1 to length[A]
        if A[i] > A[j]
            Temp = A[i]
            A[i] = A[j]
            A[j] = Temp
        End If
    j=j+1
i=i+1

Best case: O(n^2) Avarage case: O(n^2) Worst case: O(n^2)


BubbleSort(A)
   repeat
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Best case: O(n^2) Avarage case: O(n^2) Worst case: O(n^2)
________________________________________________________________________________________________

Linear runtime algorithms:

Countingsort(A,b,k)
	for i=1 to k
		do C[i]=0
	for j=1 to length[A]
		do C[A[j]]=C[A[j]]+1
	for i=2 to k
		do C[i]=C[i]+C[i-1]
	for j=length(A) downto 1
		do B[C[A[j]]]=A[j]
		   C[A[j]]=C[A[j]]-1

Best case: O(n+k) Avarage case: O(n+k) Worst case: O(n+k)


Radixsort(A, d)
	for i=1 to d
		do use a stable sort to sort array A on digit i

Best case: O(n) Avarage case: O(n) Worst case: O(n)


Bucketsort(A)
	n=length(A)
	for i=1 to n
	do insert A[i] into list B[⌊nA[i]⌋]
	for i=0 to n-1
	do sort list B[i] with insertion sort concatenate the list B[i]s together in order
	return the concatenated lists

Best case: O(n) Avarage case: O(n) Worst case: O(n)
________________________________________________________________________________________________

N logN runtime algorithms:

Heapsort(A) {
   BuildHeap(A)
   for i = length(A) downto 2 {
      exchange A[1] <-> A[i]
      heapsize = heapsize -1
      Heapify(A, 1)
}

BuildHeap(A) {
   heapsize = length(A)
   for i = floor( length/2 ) downto 1
      Heapify(A, i)
}

Heapify(A, i) {
   le = left(i)
   ri = right(i)
   if (le<=heapsize) and (A[le]>A[i])
      largest=le
   else
      largest=i
   if (ri<=heapsize) and (A[ri]>A[largest])
      largest=ri
   if (largest != i) {
      exchange A[i] <-> A[largest]
      Heapify(A, largest)
   }
}

Best case: O(n logn) Avarage case: O(n logn) Worst case: O(n logn)


Quicksort(A,p,r){
	if p<r
		then q=Partition(A,p,r)
			Quicksort(A,p,q-1)
			Quicksort(A,q+1,r)
}

Partition(A,p,r){
	x=A[r]
	i=p-1
	for j=p to r-1
		do if A[j]<=x
			then i=i+1;
				exchange A[i)<->A[j]
	exchange A[i+1]<->A[r]
	return i+1
}

Best case: O(n logn) Avarage case: O(n logn) Worst case: O(n^2)


Mergesort(A,p,r){
	ifp p<r
		then q=⌊(p+r)/2⌋
			Mergesort(A,p,q)
			Mergesort(A,q+1,r);
			Merge(A,p,q,r)
}

Merge(A,p,q,r){
	n1=q-p+1
	n2=r-q
	for i=1 to n1
		do L[i]=A[p+i-1]
	for j=1 to n2
		do R[j]=A[q+j]
	L[n1+1]=(infinity)
	L[n2+1]=(infinity)
	i=1;
	j=1;
	for k=p to r
		do if L[i] <= R[j]
			then A[k]=L[i]
				i=i+1
			else A[k]=R[j]
				j=j+1
}

Best case: O(n logn) Avarage case: O(n logn) Worst case: O(n logn)