Imię ..........Piotr
Nazwisko ........Lewicki
Wiek ..
Wzrost 72.4409449 inch
Waga ...2574.9728 oz
Narodowość .........Polska

28-06-2010

Sortowanie przez kopcowanie – Kopiec zupełny – HeapSort – Java

Filed under: Java — Tagi: , , — Levik @ 17:00

Hej, dzisiaj zaliczyłem ostatni przedmiot, kurs. Także sesja GAME OVER czytaj. „Mission Accomplished”. Tekst rodem z RED ALERT.

sesja zaliczona

Zapewne wrzucę jeszcze kilka swoich kodów na stronkę. Dzisiaj sortowanie przez kopcowanie zaimplementowane obiektowo. Struktura kopca zupełnego znajduje się w pliku heap.java, a jego przykładowe zastosowanie (tutaj sortowanie) w pliku test.java.

Oto kod:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

//********************************
//wierzchołek   1
//lewy potomek  2*i
//prawy potomek 2*i+1
//********************************
public class Heap {
 
	private int tab[];
	private int size = 0;
 
	public Heap(int size){
		tab = new int[size+1];
	}
 
	public void insert(int val){
		tab[++size]=val;
		up();
	}
 
	public void up(){
		int temp=tab[size];
		int n=size;
 
		while( (n!=1) && (tab[n/2]<=temp) ){
			tab[n] = tab[n/2];
			n=n/2;
		}
		tab[n]=temp;
	}
 
	public int getFirst(){
		int temp=tab[1];
		tab[1]=tab[size--];
		down();
		return temp;
	}
 
	public void down(){
		int i=1;
		while(true){
			int pos=2*i;
 
			if(pos>size)
				break;
 
			if(pos+1<=size)
				if(tab[pos]<tab[pos+1])
					pos++;
 
			if(tab[i]>=tab[pos])
				break;
 
			int temp = tab[pos];
			tab[pos]=tab[i];
			tab[i]=temp;
 
			i=pos;
		}
	}
}

…a teraz kod przykładu…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class Test {
 
	public static void main(String[] args){
		int tab[] = {32,43,2,46,23,1,0,-34,54,230};
 
		Heap heap = new Heap(10);
 
		for(int i=0;i<tab.length;i++)
			heap.insert(tab[i]);
 
		for(int i=tab.length;i>0;i--)
			tab[i-1]=heap.getFirst();
 
		System.out.println("Tablica posortowana");
 
		for(int i=0;i<tab.length;i++)
			System.out.println(tab[i]);
	}
 
}

Brak komentarzy »

Brak komentarzy.

Dodaj komentarz

Obraz CAPTCHY

- by levik@wp.pl L3VIK -

Jesteś gościem numer - Twój adres IP to: 38.107.179.214