Új hozzászólás Aktív témák

• Karma félisten

  #4049

  #4047 Davs

  2013-03-31 20:49:20

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  Karma

  félisten

  #4047 Davs

  #4047 Davs

  Hali!
  Tombot szerertnek sorba rendezni. Legvegsobb esetben megirnam magam az algoritmust, de azert erdekel, hogy van-e direkt az en problemamra mar letezo algoritmus.
  Van egy tombom, aminek minden eleme egy pointer egy strukturara, amiben van egy int, ami szerint rendezni kell. qsort() segitsegevel sorba is tudtam rakni a tombot, viszont nagyon fontos lenne, hogy ha ket elemben az a bizonyos int _egyenlo_, akkor a sorbarendezes utan megmaradjon az _eredeti_ sorrend. Szoval ha a 2. es a 7. elem erteke is pl 9, akkor a rendezett tombben eloszor a 2., utana pedig a 7. elem szerepeljen. Utanaolvastam a quicksortnak, ami ugy feldarabolja a tombot es aprankent rendezi (ha jol ertettem) ami miatt az utobbi kriterium nem teljesul. Valami otlet?

  Ha nem lenne megfelelo beepitett sorbarendezesi funkcio, akkor gondolom ugy kellene csinalnom, hogy vegigjarom a tombot n! - szor es minden iteracioban megkeresem a legnagyobb szam elso helyet amit aztan elore teszek..vagy volna egyszerubb megoldas is?

  A C standard qsort függvény tényleg nem stabil, azaz átrendezheti az egyenlő elemeket.

  Viszont nem kell n!-szor végigjárnod a tömböt (ez még a legegyszerűbb beszúrásos rendezésnél is rosszabb gondolat, ami csak n^2-es lépésszámú).

  Nézz szét a rendezési algoritmusok között, keress egyet ami tetszik és stabil, és implementált. Javaslom az összefésüléses rendezést, ahogy a wiki is említi, a C++ STL-ben ez érhető el stable_sort néven.

  (De ha kicsit keresgélsz, találhatsz implementációt készen is. Nem teszteltem.)

Új hozzászólás Aktív témák