Maximum és minimum kiválasztás (algoritmus)

A Programozás Wiki wikiből

[szerkesztés] Maximum kiválasztás

Maximum kiválasztásnál általában egy adathalmaz ( tömb vagy más adatszerkezet) elemei közül az (egyik) legnagyobb megkereséséről van szó. Amennyiben az adathalmaz rendezett a kiválasztás alapjául is szolgáló szempont szerint, úgy a maximum a halmaz első (csökkenő rendezés esetében) vagy utolsó elemének (növekvő rendezés esetében) kiolvasásával megállapítható. Ha az adatok nincsenek rendezve - vagy nem a maximukiválasztás alapjául szolgáló szempont szerint vannak rendezve -, akkor a maximumot csakis az adathalmaz teljes bejárásával tudjuk meghatározni.

[szerkesztés] Minimum kiválasztás

A minimum kiválasztás algoritmusa nagyon hasonló a maximum kiválasztáshoz, csak a legnagyobb elem helyett a legkisebbet keressük. A (C) forráskódban a (második) relációs jel fordítva kell szerepeljen.

[szerkesztés] Szélső esetek

Üres (vagy másképpen nulla hosszú) bemenet esetén a minimum és maximum értékek nem értelmezettek. Ezt az esetet kezelhetjük hibajelzéssel, vagy dokumentálhatjuk, hogy az algoritmus nem hívható üres bemenettel.

Egyetlen bemenő elem esetén a minimum és a maximum is egyenlő a bemenő elemmel.

Lehetséges, hogy a minimum illetve maximum értéke többször is előfordul a bemenetben. Ekkor a szokásos megoldás a legelső előfordulás visszaadása, de a legutolsó előfordulás visszaadása is egyszerűen megvalósítható.

[szerkesztés] Érdekességek

[szerkesztés] Maximum kiválasztás összehasonlítás nélkül

Nemnegatív valós számokból álló adathalmaz esetén van lehetőség összehasonlítás nélkül történő maximum kiválasztásra, ennek azonban a gyakorlati haszna csekély, ellenben az elméleti (elsősorban matematikai) haszna jelentős.

Az eljárás annyiból áll, hogy a sorozat összes tagját n-edik hatványra emeljük, ahol n tart a végtelenhez, összeadjuk őket, majd az összegből n-edik gyököt vonunk. Ebben az esetben, mivel az adathalmaz legnagyobb tagja konvergál (aszimptotikusan is) leggyorsabban a végtelenhez, ezért nagy n-ek esetén a halmaz többi tagja már elhanyagolható hozzá képest.

Így, amikor gyököt vonunk az összegből a sorozat legnagyobb tagját kapjuk eredményül.

Ennek a "módszernek" egyébként a hivatalos elnevezése végtelen-norma, de hívják sakktávolságnak is.

Egy példa (n = végtelen helyett n = 1000, de már így is látható a lényeg)

[szerkesztés] Maximum kiválasztás megvalósítása különböző nyelveken

[szerkesztés] C

   /* Nem kezeli az üres bemenetet */
   int findmax( int [] arr, int size, int * index ) {
      int i;
      int res = arr[0];
      *index = 0;
      for ( i = 1; i < size; ++i ) 
         if (res < arr[i]) {
            *index = i;
            res = arr[i];
         }
      return res;
   }

[szerkesztés] Visual Basic

   Private Sub Max()
      Dim i As Integer    ' Futóindex
      Dim x(1 To 1000) As Double    'A tömb, amelyből keresünk
      Dim max As Double    ' A megtalált maximum érték
      Dim p As Integer     ' A maximum érték tömb-sorszáma
   
         For i = 1 To 1000 Step 1
            If max < x(i) Then 
               max = x(i)
               p = i
            Else
            End If
         Next i
      ' A Keresett maximum érték kiírása
         msgbox max & ", az elem száma: " & p
   End Sub

[szerkesztés] Go

func max(arr []int) (int,int) {
        max_i := 0
        for i,v := range arr {
                if arr[max_i] < v {
                        max_i = i
                }
        }
        return max_i,arr[max_i]
}