algorytm.org

Implementacja w Java



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Hoare'a - Implementacja w Java
Ocena użytkownikóww: *****  / 4
SłabyŚwietny
Nadesłany przez Tomasz Lubiński, 27 lipca 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

AlgorytmHoare.java:
/**
 * algorytm Hoare'a
 * www.algorytm.org
 * Tomasz Lubiński (c)2005
 */
public class AlgorytmHoare {

	public static int partition(int c[], int a, int b)
	{
		int e,tmp;
		e=c[a];        //elemennt dzielacy
		while (a<b)
		        {
		        while ((a<b) && (c[b]>=e)) b--;
		        while ((a<b) && (c[a]<e)) a++;
		        if (a<b)
		                {
		                tmp=c[a];
		                c[a]=c[b];
		                c[b]=tmp;
		                }
		        }
		return a;
		}

	
	public static void main(String[] args) {

		int n,i,j,k,w;
		int c[] = new int[100];

		
		System.out.println("Podaj liczbe elementow ciagu");
		n = Console.readInt("?");
		for (i=0; i<n; i++) {
			System.out.println("Podaj "+ (i+1) +" element ciagu");
		    c[i] = Console.readInt("?");
		}
		System.out.println("Podaj ktory element obliczyc\n");
		w = Console.readInt("?");

//		algorytm Hoare'a
		i=0;
		j=n-1;
		n=w;
		while (i!=j)
			{
		        k=partition(c,i,j);
		        k=k-i+1;
		        if (k>=w) j=i+k-1;
		        if (k<w)
		                {
		                w-=k;
		                i+=k;
		                }
			}
		System.out.println(n + " element ciagu to " + c[i]);

	}
}
Dodaj komentarz