algorytm.org

Implementacja w C/C++



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 C/C++
Ocena użytkownikóww: *****  / 14
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.

algorytm Hoare.cpp:
//algorytm Hoare'a
//www.algorytm.org
//Tomasz Lubiński (c)2003

#include <stdio.h>
#include <conio.h>

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


int partition(int c[100], 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;
}


void main()
{
printf("Podaj liczbe elementow ciagu\n");
scanf("%d",&n);
for (i=0; i<n; i++)
        {
        printf("Podaj %d element ciagu\n", i+1);
        scanf("%d",&c[i]);
        }
printf("Podaj ktory element obliczyc\n");
scanf("%d",&w);

//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;
                }
	}
printf("%d element ciagu to %d", n, c[i]);
getch();
}


Komentarze
photo
-1 # ~Adrian 2011-05-08 09:21
W algorytmie Hoarea'a k nie może być jednocześnie >= w i < w wiec proponował bym dać else if żeby nie potrzebnie nie sprawdzać drugiego warunku.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz