|
Dakle, vjerujem da ima i jednostavnijih rješenja, no ja sam riješio ovako pa se nadam da će nekome pomoći...
Koji je princip tj. algoritam funkcije?
1. Uzimamo prvi element u redu
2. Uspoređujemo sve elemente s prvim koji smo uzeli (dakle sve dok ne ispraznimo red). Sve elemente šaljem na stog.
3. Vrati sve elemente osim najmanjeg u red. Varijabla brojac broji koliko jednakih elemenata ima. Ako ima jedan takav element onda samo njega nećemo vratiti, a ako ima više od jednog onda vraćamo sve osim jednog (dakle, ako imamo tri osmice, vraćamo dvije).
4. Stavljamo najmanji element na stog.
Nakon toga sve to ponavljamo dok red ne bude prazan. Kako to osiguravamo? Primijetite da uvijek radimo s jednim elementom manje...
Na kraju sve elemente stoga prebacujemo nazad u red.
[code:1]void kjusort(QUEUE *Q) {
STACK stog;
int brojac, gotovo=0, brojac_elemenata=0;
elementtype x, min;
MAKE_NULL(&stog);
while (!gotovo) {
brojac_elemenata=0;
gotovo=brojac=0;
if (!Q_EMPTY(*Q)) {
// Korak 1. Uzimamo prvi element
min=Q_FRONT(*Q);
// Korak 2: Isprazni Q i usporedi s prvim elementom.
while(!Q_EMPTY(*Q)) {
brojac_elemenata++;
x=Q_FRONT(*Q);
Q_DEQUEUE(Q);
PUSH(x, &stog);
if (x<=min) min=x;
}
// Korak 3: Vrati sve elemente osim najmanjeg u red
while (brojac_elemenata-1>=0) {
brojac_elemenata--;
if (TOP(stog)==min) brojac++;
if (brojac==1 && TOP(stog)==min) POP(&stog);
else {
Q_ENQUEUE(TOP(stog), Q);
POP(&stog);
}
}
// Korak 4: Stavi najmanji element na stog
PUSH(min, &stog);
}
else gotovo=1;
}
// Svi elementi stoga se prebacuju na red
while (!EMPTY(stog)) {
Q_ENQUEUE (TOP(stog), Q);
POP(&stog);
}
}[/code:1]
That's it.
Dakle, vjerujem da ima i jednostavnijih rješenja, no ja sam riješio ovako pa se nadam da će nekome pomoći...
Koji je princip tj. algoritam funkcije?
1. Uzimamo prvi element u redu
2. Uspoređujemo sve elemente s prvim koji smo uzeli (dakle sve dok ne ispraznimo red). Sve elemente šaljem na stog.
3. Vrati sve elemente osim najmanjeg u red. Varijabla brojac broji koliko jednakih elemenata ima. Ako ima jedan takav element onda samo njega nećemo vratiti, a ako ima više od jednog onda vraćamo sve osim jednog (dakle, ako imamo tri osmice, vraćamo dvije).
4. Stavljamo najmanji element na stog.
Nakon toga sve to ponavljamo dok red ne bude prazan. Kako to osiguravamo? Primijetite da uvijek radimo s jednim elementom manje...
Na kraju sve elemente stoga prebacujemo nazad u red.
| Kod: | void kjusort(QUEUE *Q) {
STACK stog;
int brojac, gotovo=0, brojac_elemenata=0;
elementtype x, min;
MAKE_NULL(&stog);
while (!gotovo) {
brojac_elemenata=0;
gotovo=brojac=0;
if (!Q_EMPTY(*Q)) {
// Korak 1. Uzimamo prvi element
min=Q_FRONT(*Q);
// Korak 2: Isprazni Q i usporedi s prvim elementom.
while(!Q_EMPTY(*Q)) {
brojac_elemenata++;
x=Q_FRONT(*Q);
Q_DEQUEUE(Q);
PUSH(x, &stog);
if (x<=min) min=x;
}
// Korak 3: Vrati sve elemente osim najmanjeg u red
while (brojac_elemenata-1>=0) {
brojac_elemenata--;
if (TOP(stog)==min) brojac++;
if (brojac==1 && TOP(stog)==min) POP(&stog);
else {
Q_ENQUEUE(TOP(stog), Q);
POP(&stog);
}
}
// Korak 4: Stavi najmanji element na stog
PUSH(min, &stog);
}
else gotovo=1;
}
// Svi elementi stoga se prebacuju na red
while (!EMPTY(stog)) {
Q_ENQUEUE (TOP(stog), Q);
POP(&stog);
}
} |
That's it.
_________________
"It's hard work. You show up every morning. You work hard every day, you give your best effort. There is no pressure if you prepare yourself." - Kobe Bryant
|
