Rendezett adatok, avagy a rend átláthatóbb

Az egyes programozás feladatok forrásai nagyban különböznek egymástól. A források különbözősége tekintetében nem akarok túlzottan részletekbe bocsátkozni, pusztán egyetlen szempontot vizsgálnék, hogy az adatok rendezett vagy nem rendezett formában állnak rendelkezésre.

Miért jó, ha rendezettek az adataink?

Mert sokkal több információt tartalmaz egy rendezett adathalmaz a rendezetlenhez képest. Lássunk erre egy egyszerű példát.

Adott egy tömb, ami mondjuk a [0;9] intervallumból tartalmaz véletlen egész számokat. Ránézésre milyen számok hiányoznak a következő tömbből?

{5,6,2,1,7,1,1,9,8,9,5,2,3,7,6,5,6,2}

Kicsit macerás megmondani. Nem lehetetlen, de azért beletelik egy kis időbe. Na és most?

{1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9}

A két tömb ugyanazokat az értékeket tartalmazza, csak a második esetben a számok növekvő sorrendben állnak.

Nem egy ilyen eset van, amikor valamilyen feladatot könnyebben meg tudunk oldani abban az esetben, ha rendezett adatokkal dolgozunk. Ez a lecke arról szól, hogy milyen típusú feladatokra kaphatunk rendezett tömbök esetén könnyebben (vagy másképp) választ a kevert sorrendű adatokhoz képest.

Oké, kicsit csaltam, mert például az előző kérdésre van egy olyan megoldás, ami leegyszerűsíti a feladatot. Ráadásul ez a megoldás többféle feladattípusra is használható. Egy gond van, volt már olyan emelt érettségi feladat, ahol ezeket a megoldásokat nem lehetett használni, mert tilos volt tárolni az adatokat. Akkor bizony menet közben kellett feldolgozni őket.

Miért tömb, miért nem lista?

Adattárolásra a feladatok többségében tömböket használunk. Most jöhetnél azzal, hogy a listák sok tekintetben jobbak a tömböknél, ezt senki nem vitatja. A helyzet azonban az, hogy a listákkal a tanulás során sokszor idő hiányában nincs időnk foglalkozni, örülünk, ha a tömbökkel végzünk. Szóval egyelőre maradunk a tömböknél. Amik itt elhangzanak, azok a listákra is igazak lesznek. A listát nagyon szeretjük, mert néhány feladatra még akár egyéb beépített megoldások is léteznek, amik leegyszerűsítik annak megoldását.

Rendezni, de hogyan?

A feladatok több esetben is olyan forrást biztosítanak, ahol az adatok bizonyos szempont szerint rendezettek. Összetett adatok esetén, ami nyilván jóval gyakoribb, a rendezés sokféle szempont történhet, és nem biztos, hogy pont olyan módon rendezettek az adatok, amire nekünk éppen szükségünk lenne.

Amennyiben összetett adatokról beszélünk (objektumok), a rendezés több rész-adatra is megvalósítható, ezek az adatok ráadásul nem kell, hogy azonos típusúak legyenek. Képzeld el, hogy a forrásban egy-egy autó adatai szerepelnek, az autó márkája, és az autó által futott km. Az adatokat most csak nyers formában vágom be ide:

Toyota;70337
Suzuki;80852
Honda;96352
Skoda;27825
Renault;29802
Honda;76084
Opel;34258
Suzuki;64809
Suzuki;17348
Toyota;10469
Opel;20875

Ezeket az adatokat rendezhetem csak km szerint növekvő sorrendbe, vagy márka szerint abc és azon belül km szerint növekvő sorrendbe. Hogy ez utóbbit hogyan oldhatod meg, ebben a leckében megtalálod.

A rendezett adatok tehát sokkal több információt hordoznak a kevert adatokhoz képest. Lássuk például milyeneket!

Rendezett tömbök rejtett információi

Ha az adatok eredetileg kevertek, akkor mindenképpen rendezni kell, hogy ezek a megoldások működjenek. A rendezés iránya (növekvő vagy csökkenő) nem minden feladatnál számít, de egyes esetekben kicsit módosít néhány utasításon. A következőkben pár példát mutatnék be, hogy mi minden határozható meg egy rendezett tömbből. A megoldások lényegi részét alaphelyzetben elrejtem, csak a kiinduló adatokat mutatom meg. Mindezt pusztán azért, hogy te is próbálkozhass, mielőtt megnéznéd a megoldást.

• Hányféle egyedi érték van?
• Melyik értékből van a legtöbb?
• Melyik értékből van a legkevesebb?
• Van-e hiányzó érték?
• Mennyi a legnagyobb különbség?
• Mennyi a legkisebb különbség?
• Melyik a legnagyobb?
• Melyik a legkisebb?
• Mekkora az intervallum?

Hányféle egyedi érték van a tömbben?

Sokszor szükségünk lehet arra, hogy meghatározzuk, hányféle egyedi adat található egy tömbben. Ez a szám nem feltétlenül egyezik meg a tömb méretével, hiszen az adatokban ismétlődések is előfordulhatnak.

Hányféle szám van a tömbben?

int[] tomb = new int[] { 1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9 };

int db = 1;
for( int i = 0; i < tomb.length - 1; i++ )
{
  if( tomb[i] != tomb[i + 1] )
  {
    db++;
  }
}
System.out.println("A tombben " + db + " kulonfele ertek van.");

Magyarázat:

Ez a feladat valójában egy megszámlálás, de nem a már ismert alap algoritmus. Itt az adatok különbözőségét számoljuk meg. Abból indulok ki, hogy legalább egyféle érték van a tömbben (mind ugyanaz), ezért a számlálót 1-ről indítom. Ez persze kapásból ellentmond a megszámlálás alap algoritmusának, de ez nem pontosan az, hanem annak kibővítése. Azt számolom meg, hogy hányszor változik az szám az előzőhöz képest. azért kell 1-ről indítani a számlálót, mert egyfajta szám biztosan van a tömbben, lehet, hogy mind egyforma. Itt a rendezés iránya nem is számít, hiszen csak azt számoljuk, hány szomszédos érték nem ugyanaz.

Ez a módszer ráadásul nem csak számokra, szövegekre is működik, feltételezve, hogy azokat már rendeztük:

String[] nevek = new String[]{ "Bela", "Eva", "Eva", "Pal", "Pal" };

int db = 1;
for( int i = 0; i < nevek.length - 1; i++ )
{
  if( !nevek[i].equals(nevek[i + 1]) )
  {
    db++;
  }
}
System.out.println("A tombben " + db + " kulonfele nev van.");

Nem is kell több magyarázat az előző példához, hiszen az alap logika ugyanaz. Csak egyet ne feledj: Stringek esetén == helyett equals()!

Melyik értékből van a legtöbb?

A nagy kérdés az, hogy melyik szám fordul elő legtöbbször a tömbben?

int[] tomb = new int[] { 1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9};

int db = 1;
int maxDb = 1;
int mibol = tomb[0];
for( int i = 0; i < tomb.length - 1; i++ )
{
  if( tomb[i] == tomb[i + 1] )
  {
    db++;
    if( db > maxDb )
    {
      maxDb = db;
      mibol = tomb[i];
    }
  }
  else
  {
    db = 1;
  }
}
System.out.println("A tombben a legtobb a " + mibol 
  + " szambol van: " + maxDb + " db.");

Magyarázat:

Az előzőhöz kismértékben hasonlít. Ez egyfajta maximumkeresés, de nem egy konkrét maximális értéket keresek, hanem a tömbben lévő számok darabszámának maximumát. A válasz ráadásul nem a darabszám, hanem az, hogy ez melyik számhoz tartozik. Oké, erre is használható lenne könnyítésként a többszörös megszámlálás, de most azért sem használom 😛 Nemsokára megmondom, miért.

Az egyszerű megszámlálástól ez annyiban bonyolultabb, hogy itt minden érték esetén meg kell számolni azok darabszámát, de mindig csak az érdekel, amelyikből eddig a legtöbb volt. Abból indulok ki, hogy rendezett tömb esetén az egyforma számok egymás mellett vannak, a rendezés iránya lényegtelen. Lássuk mire van szükségem már rögtön az elején.

1. Arra vagyok kíváncsi, hogy az egymás melletti egyforma értékekből hány darab van. Emiatt szükségem van egy számlálóra, amit 1-ről indítok, mert az első számból biztosan van legalább egy a tömbben.
2. Nyilván kell tartanom, hogy eddig mennyi volt a legnagyobb darabszám az egymás melletti egyforma számokból, ami logikusan szintén 1-ről indul.
3. Tudnom kell, hogy eddig melyik számból volt a legtöbb, ami induláskor nyilván a tömb első eleme lesz.

A megoldás során azt vizsgálom, hogy egymás mellett egyforma számok vannak-e. Amennyiben igen, növelem a megfelelő számlálót. Közvetlenül ezután azt is meg kell vizsgálni, hogy az aktuálisan vizsgált számokból a növelés után több lett-e, mint az eddigi maximum. Amennyiben igen, megjegyzem az új maximumot, és a hozzá tartozó értéket. Ha a következő szám nem ugyanaz, mint az előző, akkor az aktuális számok darabszámát ismét 1-re állítom, hiszen új szám következik, azokat újra meg kell számolnom.

Oké-oké, de miért kellett ennyire megbonyolítani ennek a feladatnak a megoldását az előzőleg emlegetett többszörös megszámláláshoz képest?

Próbáld csak meg valós számokra alkalmazni! Sok sikert 🙂 Hogy a String-eket már ne is emlegessem… Az egyetlen fontos kitétele az előzőleg ismertetett megoldásnak, hogy az elemek közvetlenül összehasonlíthatóak legyenek, hogy ugyanazok-e vagy sem. Akár objektumok is, megfelelő equals() metódussal felvértezve.

Melyik értékből van a legkevesebb?

Az előző feladathoz nagyon hasonló, a kérdés ezúttal az, hogy melyik értékből van a legkevesebb. Már tisztáztuk, hogy ennek a megoldásnak az erőssége, hogy gyakorlatilag bármilyen összehasonlítható adattípusra működik, nem csak egész számokra. A megoldást továbbra is számokra adom meg, de megfelelő összehasonlítás után bármilyen adattípusra használható.

int[] tomb = new int[] { 1,1,1,2,2,2,3,5,5,5,6,6,6,7,7,8,9,9};

int db = 1;
int minDb = tomb.length;
int mibol = tomb[0];
for( int i = 0; i < tomb.length - 1; i++ )
{
  if( tomb[i] == tomb[i + 1] )
  {
    db++;
  }
  else
  {
    if( db < minDb )
    {
      minDb = db;
      mibol = tomb[i];
    }
    db = 1;
  }
}

if( db < minDb )
{
  minDb = db;
  mibol = tomb[tomb.length - 1];
}

System.out.println("A tombben a legkevesebb a " + mibol 
  + " szambol van: " + minDb + " db.");

Magyarázat:

Míg a minimum és maximumkeresés esetén a két megoldás között egyetlen relációs jel a különbség, itt azt láthatjuk, hogy szerkezetileg eléggé eltérő a két megoldás. Nézzük mire van szükségem az elején:

1. Itt is kell egy számláló, melyben nyilvántartom, hogy az aktuális számból hány darabot találtam eddig, a kezdőérték itt is 1.
2. Nyilván kell tartanom, hogy eddig mennyi volt a minimális darabszám az egyforma számokból, ami viszont már teljesen más kezdőértéket kap. Itt nem tekinthetem 1-nek az elején, mert lehet, hogy nincs is olyan szám, amiből csak egy van. Akkor mit feltételezhetek? Azt, hogy minden szám ugyanaz. Ha majd találok különbözőket, akkor módosítom ezt a darabszámot.
3. Tudnom kell, hogy eddig melyik számból volt a legkevesebb, tehát az értéket is tárolnom kell. Ennek kezdőértéke ismét a tömb első eleme.

A megoldás során azt vizsgálom, hogy egymás mellett egyforma számok vannak-e. Amennyiben igen, növelem a megfelelő számlálót. Itt nincs is más teendőm. Azt, hogy az éppen számolt számok darabszáma kevesebb-e, mint az eddigi legkevesebb, akkor dönthetem el, ha az egyformákból mindet megszámoltam, vagyis amikor új szám következik. Ha tehát a következő szám már nem ugyanaz, akkor megnézem, hogy az előzőleg megszámolt számok darabszáma kisebb-e, mint az eddigi minimum. Ha igen, megjegyzem a tömb aktuális értékét (tomb[i]), ami az egymás melletti egyforma számok közül a utolsó lesz. Ez az “egyformák közül az utolsó” még hamarosan visszaköszön.

Érdekes a db változó 1-re állítása. Ezt akkor tehetem meg, amikor új szám következik, vagyis a következő érték nem egyezik az aktuálissal (else ág). Ezt mindenképpen az else-en belüli minimum vizsgálat (if) után lehet megtenni, hiszen a minimum vizsgálathoz még szükség van az előzőleg megszámolt egyforma számok darabszámára.

De itt még nem végeztünk!

Gondolj bele, mi van akkor, ha a tömb két vagy több utolsó száma megegyezik? Ilyenkor gond van, mert ugyan befejezzük a számok megszámlálását, de az utolsó ciklusban kimarad az else ág. Ezzel kimarad a minimum vizsgálat, hogy az utoljára gyűjtött darabszám kisebb-e, mint az eddigi legkisebb. Vizsgálni muszáj, mert lehet, hogy pont ezek azok az egyforma számok, amelyekből a legkevesebb van, mert előtte mindegyikből ezeknél több volt! Ezt a ciklus befejezése után mindenképpen meg kell vizsgálni! Ha valóban ezekből a számokból van a legkevesebb, akkor itt a tömb utolsó elemét írjuk ki, ami ugye megint az utolsó az egyforma értékek közül. “Egyformák közül az utolsó.”

Ha jobban belegondolsz, egy probléma még mindig lehet…

És ha csak az utolsó szám különbözik az előzőtől, vagyis egyedi érték? Mi van, ha előtte még egyik számból sem volt egyetlen darab? Akkor is helyesen működik az algoritmus. Ha az utolsó érték egy új szám, akkor az utolsó ciklusban az else ág futott le. Megnézte, hogy az utolsó előtti számból kevesebb volt-e, mint eddig, majd a db változót 1-re állította. A ciklus megállása után a db pontosan az utolsó szám darabszámát adja meg. Ilyenkor is helyesen működik az előző esetben említett cikluson kívüli vizsgálat, mert pont a tömb utolsó eleme az, amiből a legkevesebb volt. “Egyformák közül az utolsó.” (oké, befejeztem)

Sok feladatra igaz az, hogy a tömbökre megadott megoldások a tömb végén, esetleg elején lévő elemre vagy elemekre nem működnek, ezért mindig gondold át, hogy ezeken a pontokon is helyes-e az algoritmus, vagy ezeket valamiféle kivételként külön kezelned kell. Amit akár az általános megoldást adó ciklus előtt kell megoldanod!

Van-e hiányzó érték?

Ez a rész megint nem lesz olyan egyszerű. Hiányzó értékekről egy rendezett tömb esetében akkor beszélhetünk, ha két érték között egyértelműen meghatározhatóak a köztes értékek.

• Egész számokra esetében ez igaz, hiszen egyértelmű, hogy 22 és 83 között milyen számok találhatók, de valós számok esetén ez már nem oldható meg.
• Karaktereknél (konkrétabban betűk) szintén lehet működő megoldásokat készíteni, hiszen ott is meg tudjuk mondani, milyen karakterek hiányoznak mondjuk a c és h betűk között. Azért oldható meg, mert a karakterek valójában egész számok.
• Stringek esetében speciálisan generálhatóak köztes értékek, amennyiben rögzített a String hossza és szerkezete. Gondolj mondjuk olyan rendszámokra, amelyeknél az elején kikötjük, hogy mindig 3 betűből, és utána 3 számból állnak. Itt, még ha nem is egyszerűen, de legenerálhatóak két rendszám között a többiek, csak itt kicsit keverni kell a karakterek és számok kezelését. Nem mondom, hogy egyszerű, de jó kis agytorna ezt elkészíteni. Erre hamarosan készítek egy feladatot is.

A következő két megoldás egész számokra működik, aminek megoldása két kérdés alapján két részre bontható:

1. Csak a tömb belső hiányzó elemeire vagyok kíváncsi. (Ez az egyszerűbb)
2. Tudom, hogy milyen értékkészletből kellett feltölteni a tömböt, és minden hiányzó szám érdekel.

Belső hiányzó értékek meghatározása:

Ez a megoldás csak a tömb belső hiányzó elemeit adja meg. A kérdés: Milyen számok hiányoznak a tömb elemei között? A megoldásnál nem tudjuk, vagy nem fontos, hogy 8 és 9 is lehetett volna a tömbben, csak a két szélső elemet tekintjük a határoknak, és a közöttük lévő hiányzó értékeket keressük.

int[] tomb = new int[] { 1,1,1,3,3,3,7,7,7 };

for( int i = 0; i < tomb.length - 1; i++ )
{
  if( tomb[i + 1] - tomb[i] > 1 )
  {
    for( int j = tomb[i] + 1; j < tomb[i + 1]; j++ )
    {
      System.out.print(j + " ");
    }
  }
}
System.out.println();

Magyarázat:

Azt vizsgálom, hogy a szomszédos elemek között hiányzik-e valami. Ha két szomszédos elem különbsége 1-nél nagyobb, akkor egy belső ciklussal kiírom a két szomszédos elem közötti számokat. A belső ciklusnál azért nagyon figyelj, hogy mit jelent az i, és mit jelent a j. Az i az eredeti tömb elemeinek helye, a j pedig a két elem közötti hiányzó számokat jelenti.

Összes hiányzó érték meghatározása:

Ez a megoldás abból indul ki, hogy tudjuk, milyen számok lehetnének a tömbben, mondjuk az [1;9] intervallumból bármi. A kérdés az, hogy ezek közül melyik maradt ki?

int[] tomb = new int[] { 3,3,3,6,7,7,7 };

int also = 1;
int felso = 9;

if( tomb[0] > also )
{
  for( int i = also; i < tomb[0]; i++ )
  {
    System.out.print(i + " ");
  }
}

for( int i = 0; i < tomb.length - 1; i++ )
{
  if( tomb[i + 1] - tomb[i] > 1 )
  {
    for( int j = tomb[i] + 1; j < tomb[i + 1]; j++ )
    {
      System.out.print(j + " ");
    }
  }
}

if( tomb[tomb.length - 1] < felso )
{
  for( int i = tomb[tomb.length - 1] + 1; i <= felso; i++ )
  {
    System.out.print(i + " ");
  }
}
System.out.println();

Magyarázat:

Itt gyakorlatilag az előző megoldást kell kiegészíteni az alulról és felülről hiányzó elemek meghatározásával.

• 4-10 – Ha a tömb első eleme nagyobb az alsó határnál, indítok egy ciklust az alulról hiányzó elemek meghatározására.
• 12-20 – A belső hiányzó elemek meghatározása ugyanaz, mint az előző kérdés megoldása.
• 22-28 – Ha a tömb utolsó eleme kisebb a felső határnál, indítok egy ciklust az felülről hiányzó elemek meghatározására.

Mennyi a legnagyobb különbség?

Ennél a feladatnál arra vagyunk kíváncsiak, hogy a szomszédos eleme között mekkora a legnagyobb különbség. Ennek nyilván számok esetén van értelme, amik lehetnek akár valós számok is. Ez eddig rendben is van, de az egész feladat nem rendezett tömbnél is megoldható, ugyanúgy értelmezhető a szomszédos elemek különbsége. Mikor értelme van akkor a rendezésnek?

Tegyük fel, hogy adott egy kevert tömb egy hónap napjait tartalmazza, amiket valami okból rögzítettünk, és az a kérdés, hogy mekkora volt a legnagyobb szünet két nap között. Ezt már csak rendezett tömbként lehet megoldani, mert így tudom meghatározni az egymás után következő napok különbségét. A rendezés iránya gyakorlatilag mindegy, csak a különbség képzésnél kell odafigyelni, hogy melyikből melyiket vonjuk ki.

int[] tomb = new int[] { 3,8,11,12,15,22,25,31 };

int maxKulonbseg = tomb[1] - tomb[0];
for( int i = 1; i < tomb.length - 1; i++ )
{
  if( tomb[i + 1] - tomb[i] > maxKulonbseg )
  {
    maxKulonbseg = tomb[i + 1] - tomb[i];
  }
}
System.out.println(maxKulonbseg);

Magyarázat:

Ebben igazából semmi rendkívüli dolog nincs. A legnagyobb különbség kezdőértékének nyugodtan beállíthatom az első két elem különbségét. Utána viszont célszerű (bár nem kötelező) 1-től indítani a ciklust, hogy ugyanannak a két számnak a különbségét ne vizsgáljam meg újra.

Mi van, ha az is a kérdés része, hogy melyik két nap között volt a legnagyobb különbség? Csak ki kell egészíteni azzal, hogy meg kell jegyezni a különbség első napjának az indexét. Lássuk ezzel kiegészítve:

int[] tomb = new int[] { 3,8,11,12,15,22,25,31 };

int maxKulonbseg = tomb[1] - tomb[0];
int maxIdx = 0;
for( int i = 0; i < tomb.length - 1; i++ )
{
  if( tomb[i + 1] - tomb[i] > maxKulonbseg )
  {
    maxKulonbseg = tomb[i + 1] - tomb[i];
    maxIdx = i;
  }
}
System.out.println(maxKulonbseg);
System.out.println(tomb[maxIdx] + " - " + tomb[maxIdx + 1]);

A két kiemelt sorban látható a kiegészítés, a legnagyobb különbségű tagok közül az első indexét jegyzem meg, abból már megvan a másik is.

Mennyi a legkisebb különbség?

Ennél a feladatnál arra vagyunk kíváncsiak, hogy a rendezett tömb szomszédos elemei között mekkora a legkisebb különbség. Az előzőhöz hasonlóan szintén csak számok esetén van értelme, amik lehetnek akár valós számok is. A rendezés iránya mindegy, csak itt is figyelni kell arra, hogy melyikből melyiket vonjuk ki. Emlékszel, hogy a legtöbb-legkevesebb problémánál is a legkevesebb megoldása jóval bonyolultabb volt a másiknál? Lehet már ott motoszkál benned, hogy itt sem úszod meg könnyen a dolgot. A helyzet az, hogy igazából a két megoldás különbsége ugyanaz, mint az alap minimum és maximumkeresés esetén, egyetlen relációs jel. De lássuk akkor ennek a megoldását.

int[] tomb = new int[] { 3,8,11,12,15,22,25,31 };

int minKulonbseg = tomb[1] - tomb[0];
for( int i = 1; i < tomb.length - 1; i++ )
{
  if( tomb[i + 1] - tomb[i] < minKulonbseg )
  {
    minKulonbseg = tomb[i + 1] - tomb[i];
  }
}
System.out.println(minKulonbseg);

Az egyetlen különbség a 4-es sorban található relációs jel (a változók nevein kívül).

És ha a két napra is szükség van, melyek különbsége a legkisebb?

int[] tomb = new int[] { 3,8,11,12,15,22,25,31 };

int minKulonbseg = tomb[1] - tomb[0];
int minIdx = 0;
for( int i = 1; i < tomb.length - 1; i++ )
{
  if( tomb[i + 1] - tomb[i] < minKulonbseg )
  {
    minKulonbseg = tomb[i + 1] - tomb[i];
    minIdx = i;
  }
}
System.out.println(minKulonbseg);
System.out.println(tomb[minIdx] + " - " + tomb[minIdx + 1] );

Ugyanúgy megjegyezzük a megfelelő indexet, abból már megvan a két elem is.

Melyik a legnagyobb? Melyik a legkisebb?

Nem véletlenül tárgyalom a két kérdést egyetlen pontban. Ezt a feladatot megoldásra sem méltatom 🙂 Az alábbi felsorolás alapján úgyis egyértelmű lesz (remélhetőleg). Pár dolgot azért megjegyeznék ezzel kapcsolatban:

• Ha eredetileg rendezett tömbünk van, akkor a rendezés irányától függően a legkisebb elem mindig a tömb megfelelő végén van.
  • Növekvő rendezés esetén a legnagyobb mindig az utolsó elem, a legkisebb pedig az első.
  • Csökkenő rendezés esetén a legnagyobb mindig az első elem, a legkisebb pedig az utolsó.
• Ha eredetileg NEM rendezett tömbünk van, a rendezés után valamelyik végén találjuk meg a legnagyobb vagy legkisebb elemet, de ezzel elveszítjük azt az információt, hogy eredetileg ez pontosan melyik helyen volt eredetileg.
• Ha a kérdést kombináljuk egyfajta rangsorral is, akkor a rendezett tömbben könnyel választ kaphatunk a hasonló kérdésekre:
  • Melyik a tömb második legnagyobb eleme?
  • Melyik a tömb harmadik legkisebb eleme?
  • Stb.
• Ha az előző kérdések esetén az eredeti tömb nem rendezett, akkor a rendezés után természetesen ismét elveszítjük a megtalált 2. legnagyobb, 3. legkisebb, stb elemek eredeti helyét.

Ezeknél a kérdéseknél mindig mérlegelni kell, hogy feltétlenül kell-e rendezni a tömböt a kérdés megoldásához, hiszen a maximum és minimumkeresést az alap algoritmusok leckéből megtanulhattad. A második legkisebb, és hasonló kérdéseknél pedig azt kell mérlegelned, hogy elég-e csak a konkrét értéket meghatároznod, vagy az adott érték pontos helye is fontos.

Természetesen megteheted azt, hogy a tömbről egy másolatot készítesz, és azzal már azt csinálsz, amit akarsz, az eredetit nem rontod el, de ez alapvetően csak a primitív értékeknél oldható meg:

int[] tomb = new int[] { 3,8,11,12,15,22,25,31 };
int[] masolat = tomb.clone();

Itt a második tömb az elsőnek egy pontos, érték szerinti másolata lesz. Így bármilyen műveletet végzel az egyikkel, az a másikra nincs hatással.

Ha azonban az alábbi módon oldanád meg a másolat elkészítését, azzal a két tömböt gyakorlatilag összekötöd referencia (memóriabeli hivatkozás) szerint, és bármelyiket változtatod, az mindkettőre hatással van, mert mindkét változó ugyanarra a tömbre mutat. Próbáld csak ki:

int[] tomb = new int[] { 3,8,11,12,15,22,25,31 };
int[] masolat = tomb;

tomb[0] = -100;

for( int i = 0; i < masolat.length; i++ )
{
  System.out.print(masolat[i] + " ");
}
System.out.println();

Mekkora az intervallum?

Ha adott egy tömb, amiben valamilyen számok vannak, akkor könnyen megadhatjuk, hogy valójában milyen intervallumbeli elemek vannak a tömbben. Amire szükségünk van, az a tömb legkisebb és legnagyobb eleme, tehát mindkettőre szükségünk van. Itt is csak megemlítenék pár gondolatot felsorolásszerűen.

• Ha a tömb eredetileg rendezett, akkor a legkisebb és legnagyobb elemek a tömb megfelelő szélein találhatóak. Nyilván itt is figyelembe kell venni a rendezés irányát.
• Ha a tömb nem rendezett, akkor rendezés után a széleken ott lesz az eredmény a rendezés irányának megfelelően. Fontos azonban figyelembe venni, hogy szükség van-e még az eredeti sorrendre, mert akkor nem így kellene megoldani.
• A legegyszerűbb módszer természetesen a tanult minimum és maximumkeresés alkalmazása, mert ez a tömb szerkezetétől és típusától teljesen független, és semmit nem változtat rajta.

Rendezzünk, vagy nem?

Magad is láthattad, hogy a rendezett tömbökből sok plusz információ kinyerhető. A gond az, hogy a tömb alapesetben nem mindig rendezett. Lehetnek olyan feladatok, ahol nagyon jól jönne a rendezés, de lehet, hogy későbbi feladatoknál pont azzal veszítünk információt, hogy az eredeti tömböt sorrendileg átalakítottuk.

Bizonyos esetekben készíthető a tömbről egy másolat, de objektumok esetén már nem ennyire triviális a dolog. Ott azzal az eszközzel élhetünk, hogy minden objektumhoz hozzáadunk egy plusz tulajdonságot, gyakorlatilag egy indexet, ami az eredeti sorrendjüket tartalmazza. Így bármikor bárhogy rendezhetjük őket, hogy egy adott rész feladatra egyszerűbben kapjunk választ, az eredeti indexek alapján bármikor visszarendezhetjük őket. Kérdés, hogy érdemes-e mindig ennyit rendezgetni az elemeinket. Nem biztos. Mérlegelni kell.

Ez a lecke nem azt sugallja – legalábbis nem ez volt a szándékom – hogy a rendezés mindig mindenre megoldás lesz, vagy nagyban megkönnyíti a dolgunk. Bizonyos típusfeladatokra ad megoldásokat, amelyek egy rendezett tömb esetén használhatóak. Nem tilos egy tömböt rendezni, hogy bizonyos feladatokat könnyebben oldhassunk meg vele kapcsolatban, csak mindig figyelni kell arra, hogy később okoz-e az eredeti sorrend megváltoztatása valamilyen problémát.