| ZER DAKIDAN: Arrayekin lan egiteko hainbat algoritmo ezagutzen dut. ZER IKASIKO DUDAN: Array desordenatu bat ordenatzen edo sailkatzen ikasiko dut orain. |
Zenbaki osoen array bat irudikatzen dute dantzariek, aukeraketa algoritmoa aplikatuz arraya sailkatuko dute
Demagun array dimentsiobakar bat dugula (bektore bat) eta bere elementuak zenbaki errealak direla, 0-tik 9-ra bitarteko alde osoa eta 0-tik 9-ra dezimal bakarra duten zenbaki errealak alegia.
Sailkatzeko algoritmo desberdinetatik aukeraketa algoritmoa azalduko dugu ulerterraza delako, une bakoitzean zenbakirik txikiena aukeratuko dugu. Hauxe litzateke algoritmoaren irudia:
Eta hauxe da algoritmoaren azalpena...
Goiko eskeman ikus daitekeenez k kontagailuaren laugarren iterazioan gaude, ordurako array sailkatuaren lehen hiru elementuak zehaztu dira, eta iterazio honetan aurkituko den minimoa gelaxka ilunean kokatuko dugu (k=4 posizioan alegia). Laugarren iterazioari dagokion minimoa bilatzeko, arrayaren sailkatu/ordenatu gabeko aldean begiratu beharra dago eta horretarako j kontagailua erabiliko da.
| Zer dakigun k iterazioan: sailkatzeko hurrengo elementua non kokatuko den, arrayaren k posizioan. Zer ez dakigun k iterazioan: arrayaren bigarren zatiko elementuen artean zein da sailkatzeko hurrengo elementua (bai badakigu balio minimoa duen elementua dela, baina ez zein den bere posizioa). |
k=4 iterazioari dagokion minimoa zehazteko Min eta Pos aldagai laguntzaileen bitartez egiten da. Hasiera batean Min aldagaian sailkatu/ordenatu gabeko tartearen lehen elementuaren balioa gordetzen da, hots, Min aldagaian A[k] elementuaren balioa gordetzen da eta Pos aldagaian elementu horri dagokion k posizioa. Hasieraketak egin ondoren, barneko FOR-DO bitartez sailkatu/ordenatu gabeko aldea aztertzen da elementurik txikiena zehaztuz (bere balioa eta bere posizioa zehaztuz). Laugarren iterazioan minimoa zein den jakitean, array sailkatuan dagokion tokira (k=4 posiziora) eraman behar da, horregatik k eta Pos indizedun elementuak elkar trukatu egin behar dira.
Hona hemen array bat sailkatzen duen iturburu-programa:
/* 11a-ArrayBatSailkatzea: Zenbaki errealean array bat auzaz bete
ondoren, txikitik handira sailkatu. */
// Zenbaki errealen array bat auzazko datuz bete ondoren, arrayaren elementuak
// ordenatu balio txikienetik balio handienera "aukeraketa" algoritmoa erabiliz.
// Aukeraketaren algoritoaren funtsa da elementurik txikiena aukeratzea iterazio
// bakoitzean. Iterazio jakin batean arrayaren aurreko zatia ordenaturik dago
// arrayaren bukaerako zatia desordenaturik dago. Desordenatua den bigarren zati
// honetan "aukeratu" behar da hurrengo elementua zati ordenatuan. Sailkatzea
// balio txikienetik balio handienera bada "aukeratu" aditzaren esanahia da
// minimoaren posizioa zehaztu. Sailkatzea balio handienetik balio txikienera
// bada, orduan "aukeratu" aditzaren esanahia da maximoaren posizioa zehaztu.
#include <stdio.h>
#include <stdlib.h> // srand() eta rand() funtzioetarako
#include <time.h> // time() funtziorako
#define LUZERAMAX 8
typedef float tafZerrenda[LUZERAMAX]; // gehienez 9 zenbaki gordetzeko arrayak
float fMoldatu(float fDatua);
void ArrayaBete(tafZerrenda afBekt, int *iLuzera);
void ArrayaIkusi(const tafZerrenda afBekt, int iLuzera);
void AukeraketazOrdenatu(tafZerrenda afBekt, int iLuzera);
int main()
{
tafZerrenda afBekt;
int iLuzera;
ArrayaBete(afBekt, &iLuzera);
printf("Ordenatu baino lehen ");
ArrayaIkusi(afBekt, iLuzera);
printf("----------------------------------------------------------------\n");
AukeraketazOrdenatu(afBekt, iLuzera);
printf("----------------------------------------------------------------\n");
printf("Ordenaturik, ");
ArrayaIkusi(afBekt, iLuzera);
return 0;
}
// Zenbaki erreal bat moldatu:
// Alde osorik ez duen zenbaki erreal bat hartu eta alde
// osoan digitu bakarra eta dezimal bakarra duen zenbaki
// erreala itzultzen duen funtzioa: 0.12345 ---> 1.2
float fMoldatu(float fDatua)
{
fDatua = fDatua * 100;
fDatua = (int)fDatua;
return fDatua / 10;
}
// Arraya ausazko balioekin bete:
// Lehenengo parametroa array bat delako eta irteerakoa
// delako erreferentziaz pasatzen da. iLuzera luzera
// erreferentziaz ere balioa prozeduran hartzen duelako
void ArrayaBete(tafZerrenda afBekt, int *iLuzera)
{
srand(time(NULL));
*iLuzera = rand() % LUZERAMAX + 1; // gehienez 9 elementu, indizeak 0-tik 8-ra
if (*iLuzera < 4)
*iLuzera = 4; // gutxienez 4 elementu, indizeak 0-tik 3-ra
printf("Arrayan %d datu gordetzen...\n", *iLuzera);
for (int i = 0; i < *iLuzera; i++)
{
afBekt[i] = (float)rand() / RAND_MAX;
printf("\n%d. auzaz: afBekt[i]=%f", i, afBekt[i]);
afBekt[i] = fMoldatu(afBekt[i]); // 0.0 eta 9.9 artekoak
printf(" moldatuta: afBekt[i]=%.3f", afBekt[i]);
}
printf("\n\n");
}
// Arrayaren edukia pantailaratu:
// Nahiz eta parametro biak sarrerakoak izan, lehenengoa
// array bat delako erreferentziaz pasatzen da const marka
// gehituz aldaketak ekiditeko. Bigarrena berriz balioz
void ArrayaIkusi(const tafZerrenda afBekt, int iLuzera)
{
printf("Arrayaren edukia:\n");
for (int i = 0; i < iLuzera; i++)
{
printf("%8.1f", afBekt[i]);
}
printf("\n");
}
// Arraya aukeraketaz ordenatu:
// Parametro bat irteerakoa den bitartean bestea sarrerakoa
// da. Horregatik, aldatuko den afBekt arraya erreferentziaz
// pasatzen da, baina aldatuko ez den iLuzera luzera logikoari
// dagokion osoa balioz pasarazaten da
void AukeraketazOrdenatu(tafZerrenda afBekt, int iLuzera)
{
int k, j;
int iPos;
float fMin;
for (k = 0; k < iLuzera - 1; k++) // kanpoko begizta, minimoa dagokion posizioan kokatzeko
{
fMin = afBekt[k];
iPos = k;
for (j = k + 1; j < iLuzera; j++) // barruko begizta, minimoa non dagoen zehazteko
{
if (fMin > afBekt[j])
{
fMin = afBekt[j];
iPos = j;
}
}
// bi elementuak trukatu
afBekt[iPos] = afBekt[k];
afBekt[k] = fMin;
// iterazio bakoitza erakutsi
printf("%d. iterazioan, ", k);
ArrayaIkusi(afBekt, iLuzera);
}
printf("%d. iterazioa soberan, arraya sailkaturik dagoelako\n", k);
}
Gauza bera egin daiteke erregistroen bektore batekin. Ikus dezagun adibidez ondoko erregistroan oinarritutako bektore bat nola sailkatzen den bi eremuen informazioaren arabera:
...
#define MAX_IKASLEAK 12
#define MAX_STR49 50
typedef char tsKate49[MAX_STR49]; // ikaslearen izena gordetzeko 49 karaktere gehi null mugatzailea
typedef struct
{
tsKate49 sNor;
int iDeialdia;
float fKalifikazioa;
} trdIkasle;
typedef trdIkasle tardIkasleak[MAX_IKASLEAK];
...
Hona hemen erregistroen array bat sailkatzen bi eremuen arabera. Sailkatze nagusia iDeialdia eremuaren araberakoa da, eta deialdi berdineko elementuak sNor eremuaren arabera ordenatuko dira:
/* 11b-SailkatzeAurreratua: Erregistroen array bat sailkatu bi
eremuko informazioa arabera. */
// Arrayaren hasierako informazioa desordenaturik dago eta ordenatu
// behar da, lehenik deialdien arabera eta ondoren abizenen arabera.
#include <stdio.h>
#include <string.h> // strcmp() funtziorako
#define MAX_IKASLEAK 12
#define MAX_STR49 50
typedef char tsKate49[MAX_STR49]; // ikaslearen izena gordetzeko 49 karaktere gehi null mugatzailea
typedef struct
{
tsKate49 sNor;
int iDeialdia;
float fKalifikazioa;
} trdIkasle;
typedef trdIkasle tardIkasleak[MAX_IKASLEAK];
void ArrayaBete(tardIkasleak ardHasierakoak, int iLuzera);
void DatuakIkusi(const tardIkasleak ardIkasleak, int iLuzera);
void ArrayaSailkatu(tardIkasleak ardHasierakoak, int iLuzera);
// ikasleen izenak, deialdiak eta notak array konstanteetan
const tsKate49 asIZENAK[MAX_IKASLEAK] =
{
"EGIGUREN MARKINEZ, IRUNE", // 0
"GARTZIA DE ALZA GIL, KATALIN", // 1
"HERRANZ MARTINEZ, REBECA", // 2
"CANO RUIZ DE HEREDIA, JULIAN", // 3
"IRAGORRI COTANO, MARTIN", // 4
"FERNANDEZ FEITO, FELIX", // 5
"DIAZ DE ULZURRUN, ROY, LEONOR", // 6
"AGIRRE ROMERO, UNAI", // 7
"ERKIAGA ANDONEGI, IKER", // 8
"BIKARREGI IGLESIAS, JULEN", // 9
"ANGULEMA CARAZO, JON ANDER", // 10
"CORRAL EGIA, JOSEBA ANDONI" // 11
};
const int aiDeialdiaK[MAX_IKASLEAK] = {3, 1, 2, 2, 1, 3, 1, 2, 3, 2, 3, 1};
const float afKALIFIKAZIOAK[MAX_IKASLEAK] = {4.6, 3.2, 5.7, 4.8, 5.1, 6.1, 7.3, 7.6, 2.8, 9.2, 2.9, 8.5};
int main()
{
tardIkasleak ardIkasleak;
int iLuzera;
iLuzera = MAX_IKASLEAK;
ArrayaBete(ardIkasleak, iLuzera);
printf("\n---Arraya sailkatu aurretik-----------------------------------------\n");
DatuakIkusi(ardIkasleak, iLuzera);
ArrayaSailkatu(ardIkasleak, iLuzera);
printf("\n===Array ordenatuaren edukia========================================\n");
DatuakIkusi(ardIkasleak, iLuzera);
return 0;
}
// hasierako arraya bete ikasleen datuekin
void ArrayaBete(tardIkasleak ardIkasleak, int iLuzera)
{
trdIkasle rdIkasleBat;
int k;
for (k = 0; k < iLuzera; k++)
{
strcpy(rdIkasleBat.sNor, asIZENAK[k]);
//printf("\nasIZENAK[k]=%s| rdIkasleBat.sNor=%s|", asIZENAK[k], rdIkasleBat.sNor);
rdIkasleBat.iDeialdia = aiDeialdiaK[k];
rdIkasleBat.fKalifikazioa = afKALIFIKAZIOAK[k];
ardIkasleak[k] = rdIkasleBat;
}
}
// arrayaren edukia pantailaratu
void DatuakIkusi(const tardIkasleak ardIkasleak, int iLuzera)
{
for (int k = 0; k < iLuzera; k++)
{
printf("%4d. ikaslea: %-35s %5d %8.1f\n", k, ardIkasleak[k].sNor,
ardIkasleak[k].iDeialdia,
ardIkasleak[k].fKalifikazioa);
}
}
void ArrayaSailkatu(tardIkasleak ardIkasleak, int iLuzera)
{
//trdIkasle rdIkasleBat;
int k, j;
int iPosMin;
trdIkasle rdMin;
for (k = 0; k < iLuzera; k++) // minimoa kokatzeko posizioa k izango da
{
rdMin = ardIkasleak[k];
//printf("\nrdMin.sNor=%s|\nrdMin.iDeialdia=%d rdMin.fKalifikazioa=%.2f\n", rdMin.sNor, rdMin.iDeialdia, rdMin.fKalifikazioa);
iPosMin = k;
for (j = k+1; j < iLuzera; j++) // ordenatu gabekoen artean minimoa non dagoen zehaztu
{
if (
(rdMin.iDeialdia > ardIkasleak[j].iDeialdia) ||
(
(rdMin.iDeialdia == ardIkasleak[j].iDeialdia) && // rdMin.iDeialdia berdina denean eta...
(strcmp(rdMin.sNor, ardIkasleak[j].sNor) > 0) // rdMin.sNor handiagoa denean...
)
)
{
rdMin = ardIkasleak[j];
iPosMin = j;
}
}
ardIkasleak[iPosMin] = ardIkasleak[k]; // trukatu, tokiz aldatuz
ardIkasleak[k] = rdMin;
}
}
iruzkinik ez:
Argitaratu iruzkina