Algorithmensammlung: Sortierverfahren: Heapsort

Aus Wikibooks

Wechseln zu: Navigation, Suche

Algorithmensammlung: Sortierverfahren

Inhaltsverzeichnis

[Bearbeiten] Heapsort

Heapsort ist ein Sortieralgorithmus, der die Datenstruktur der Wikipedia-logo.png Halde ausnutzt, um in-place zu sortieren. Der Algorithmus ist dabei auch im Worst-Case in der Komplexitätsklasse \mathcal{O}(n \cdot \log(n)) und damit in diesem Fall schneller als Quicksort.

Für weitere Informationen siehe Wikipedia-logo.png Heapsort.


Qsicon inArbeit.png
todo
Quelltexte nach Deutsch übersetzen


[Bearbeiten] C++

#include <iterator>
 
template< typename Iterator >
void adjust_heap( Iterator first
                  , typename std::iterator_traits< Iterator >::difference_type current
                  , typename std::iterator_traits< Iterator >::difference_type size
                  , typename std::iterator_traits< Iterator >::value_type tmp )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
 
    diff_t top = current, next = 2 * current + 2;
 
    for ( ; next < size; current = next, next = 2 * next + 2 )
    {
        if ( *(first + next) < *(first + next - 1) )
            --next;
        *(first + current) = *(first + next);
    }
 
    if ( next == size )
        *(first + current) = *(first + size - 1), current = size - 1;
 
    for ( next = (current - 1) / 2;
          top < current && *(first + next) < tmp;
          current = next, next = (current - 1) / 2 )
    {
        *(first + current) = *(first + next);
    }
    *(first + current) = tmp;
}
 
template< typename Iterator >
void pop_heap( Iterator first, Iterator last)
{
    typedef typename std::iterator_traits< Iterator >::value_type value_t;
 
    value_t tmp = *--last;
    *last = *first;
    adjust_heap( first, 0, last - first, tmp );
}
 
template< typename Iterator >
void heap_sort( Iterator first, Iterator last )
{
    typedef typename std::iterator_traits< Iterator >::difference_type diff_t;
    for ( diff_t current = (last - first) / 2 - 1; current >= 0; --current )
        adjust_heap( first, current, last - first, *(first + current) );
 
    while ( first < last )
        pop_heap( first, last-- );
}

[Bearbeiten] Java

/**  
 * sortiert ein Array mit heapsort
 * @param a das array
 */
private static void heapSort(int[] a) {
	generateMaxHeap(a);
 
	//hier wird sortiert
	for(int i = a.length -1 ; i > 0 ; i--) {
		vertausche(a, i, 0);
		versenke(a, 0,i);
	}
}
 
/**
 * Erstellt einen MaxHeap Baum im Array 
 * @param a das array
 */
private static void generateMaxHeap(int[] a) {
	//starte von der Mitte rückwärts.
	for(int i = (a.length / 2) - 1; i >= 0 ; i--) {
		versenke(a,i,a.length);
	}
}
 
/**
 * versenkt ein element im baum
 * @param a Das Array
 * @param i Das zu versenkende Element
 * @param n Die letzte Stelle im Baum die beachtet werden soll
 */
private static void versenke(int[] a, int i,int n) {
	while(i <= (n / 2) - 1) {
		int kindIndex = ((i+1) * 2) - 1; // berechnet den Index des linken kind
 
		//bestimme ob ein rechtes Kind existiert
		if(kindIndex + 1 <= n -1) {
			//rechtes kind existiert
			if(a[kindIndex] < a[kindIndex+1]) {
				kindIndex++; // wenn rechtes kind größer ist nimm das 
			}
		}
 
		//teste ob element sinken muss 
		if(a[i] < a[kindIndex]) {
			vertausche(a,i,kindIndex); //element versenken
			i = kindIndex; // wiederhole den vorgang mit der neuen position
		} else break;
	}
}
 
/**
 * Vertauscht die arraypositionen von i und kindIndex
 * @param a Das Array in dem getauscht wird
 * @param i der erste index
 * @param kindIndex der 2. index
 */
private static void vertausche(int[] a, int i, int kindIndex) {
	int z = a[i];
	a[i] = a[kindIndex];
	a[kindIndex] = z;
}

[Bearbeiten] Pascal

const SIZE = 20000;
type TFeld = array[1..SIZE] of integer;
 
procedure heapsort(var f:TFeld);
 
    procedure genheap(var f:TFeld);             { Heap (mit linearem Aufwand) aufbauen }
    var i,j,max,temp:integer;
    begin
        for i := SIZE div 2 downto 2 do begin   { zweite Hälfte des Feldes braucht nicht betrachtet werden }
            j:=i;
            while j <= SIZE div 2 do begin
                max := j * 2 + 1;               { finde Maximum der (beiden) Söhne }
                if max > SIZE then dec(max)
                else if f[max-1] > f[max] then dec(max);
                if f[j] < f[max] then begin     { ggf. tauschen }
                    temp := f[j];
                    f[j] := f[max];
                    f[max] := temp;
                end;
                j := max;
            end;
        end;
    end;
 
    function popmax(var f:TFeld;heapsize:integer):integer;
    var i,max,temp:integer;
    begin
        popmax := f[1];
        f[1] := f[heapsize];
        i := 1;
        while i <= (heapsize div 2) do begin { letztes Element an Anfang setzen und versickern lassen }
            max := i * 2 + 1;               { finde Maximum der (beiden) Söhne }
            if max > heapsize then dec(max)
            else if f[max-1] > f[max] then dec(max);
            if f[i] < f[max] then begin     { ggf. tauschen }
                temp := f[i];
                f[i] := f[max];
                f[max] := temp;
            end;
            i := max;
        end;
    end;
   var i:integer;
begin
    genheap(f);
    for i:=SIZE downto 1 do f[i] := popmax(f,i);
end;

[Bearbeiten] Python

 from math import *
 import random
 
 class tree:
   # initialize tree
   def __init__(this,list):
     this.list = list
 
   # Exchange-Operation
   def exch(this, i,j):
     tmp = this.list[i]
     this.list[i] = this.list[j]
     this.list[j] = tmp
 
   # sink item
   # die iterative Variante frei nach Robert Sedgewick
   def sink(this,index):
     N = len(this.list)
     k = index+1
 
     while(2*k <= N):
       j=2*k
       if j<N and this.list[j-1] < this.list[j]:
         j += 1
       if this.list[k-1] >= this.list[j-1]:
         break
       this.exch(k-1,j-1)
       k = j
 
   def getHighest(this):
     a = this.list[0]
     this.exch(0,len(this.list)-1)
     del this.list[len(this.list)-1]
     this.sink(0)
     return a
 
 # Generating random numbers
 a = []
 for i in range(0,100):
   a.append(random.randint(1,10000))
 a = tree(a)
 print a.list
 
 # Build Heap
 tmp = range(len(a.list))
 tmp.reverse()
 for i in tmp:
   a.sink(i)
 
 # UnBuild Heap to view as sorted list
 out = []
 for i in range(len(a.list)): 
   out.append(a.getHighest())
 
 out.reverse()
 print out


[Bearbeiten] Fortran

 # Die Implementierung wurde der JAVA-Version nachempfunden
 
subroutine vertausche (a, size, x, y)
  integer x, y, z, size
  integer a(size)
 
  z = a(x)
  a(x) = a(y)
  a(y) = z
 
  return
end
 
subroutine versickere (a, size, i) 
  integer i, size, ln, j
  integer a(size)
 
  j = i
  do while (j.LE.(size/2))
     ln = 2*j
     if (ln.LT.size) then
        if ((a(ln+1)).GT.(a(ln))) ln = ln+1
     end if
 
     if ((a(ln)).GT.(a(j))) then
        call vertausche(a,Size,j,ln)
        j = ln
     else
        j = size
     end if
  end do
 
  return
end
 
subroutine ueberfuehreInHeap (a, size)
  integer size, i
  integer a(size)
 
  do i = size /2 , 1 , -1
     call versickere (a, size, i)
  end do
 
  return
end
 
subroutine heapSort (a, size) 
  integer size
  integer a(size)
 
  call ueberfuehreInHeap(a,size)
 
  do i=size, 1, -1
     call vertausche(a, size, 1, i)
     call versickere(a, i-1, 1)
  end do
 
  return
end
Von „http://de.wikibooks.org/wiki/Algorithmensammlung:_Sortierverfahren:_Heapsort“
Persönliche Werkzeuge