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

• #15585 axioma veterán pmonitor #15582

  Új Válasz 2021-02-26 16:39:41 #15585

  Ú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

  Privát üzenet küldése

  

  axioma

  veterán

  válasz pmonitor #15582 üzenetére

  En egy dolgot megneztem benne: mar amikor nekem tanitottak a "tiszta" rendezesi algoritmusokat, akkor mondtak hogy a valosagban nem ilyet hasznalnak (letezo library-k), hanem egy kevert algot: ha a hossz ma'r <=5, akkor a rekurziv hivas koltsege tobb, mint az nlogn es n^2 kozotti kulonbseg, ezert azokat a darabokat egy sima buborekkal/kivalasztasossal vagy barmi ilyesmivel lerendezik, es csak felette jon a felezes. Ha szeretsz ilyenekkel jatszani, probald ki. Azota lehet hogy van tobb mas trukk is.
  Amugy a mar leglevo algoritmusoknal celhoz kototten tudsz jobb algoritmust irni (felteve ha nem annyira altalanos hogy van ra lib ), vagyis ha barmi tobbet tudsz az adataidrol. Peldaul ha csupa 1000 es 10000 kozotti szamok 10ezres nagysagrendben (adatbazisban amcsi iranyitoszamok volt a pelda, az me'g egy kb. 80-as evekben irt konyvben), akkor jobban jarsz ha egy masik tombben megszamolod melyikbol mennyi van/bevodrozod hogy hol (indexek), es utana vegigfutsz rajta vissza-flatten-elni, igy van linearis megoldas.

• #15584 kovisoft őstag pmonitor #15582

  Új Válasz 2021-02-26 15:53:23 #15584

  Ú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

  Privát üzenet küldése

  

  kovisoft

  őstag

  válasz pmonitor #15582 üzenetére

  Még régebben írtam egy rövid függvényt, ami kiírja a N szám permutációit rendezett formában. Most sehol sem találom, de emlékeim alapján megpróbáltam újra lekódolni C-ben:

  int a[50];
int n=5;
int i, j, temp;

// az 1 2 3 ... n sorozatbol indulunk ki
for (i=0; i<n; i++)
a[i] = i+1;

for (;;)
{
// kiirjuk az aktualis permutaciot
for (i=0; i<n; i++)
printf("%d ", a[i]);
printf("\n");

// megkeressuk, hol kezdodik az utolso monoton csokkeno reszsorozat
for (i=n-2; i>=0 && a[i]>a[i+1]; i--);

// ha a teljes sorozat monoton csokkeno, akkor vegeztunk
if (i < 0)
break;

// a csokkeno reszsorozat elotti elemet ki kell cserelnunk a reszsorozatban nagysag szerint rakovetkezovel
for (j=n-1; a[j]<a[i]; j--);
temp=a[i]; a[i]=a[j]; a[j]=temp;

// tovabbra is monoton csokkeno a reszsorozatunk, forditsuk meg, hogy monoton novekedo legyen
for (j=i+1; j<n+i-j; j++)
{
temp=a[j]; a[j]=a[n+i-j]; a[n+i-j]=temp;
}
}

  Nem teszteltem a sebességét, nem állítom, hogy ez a létező leggyorsabb módszer, de viszonylag rövid és egyszerű. Egyébként most, hogy jobban megnézem, ez majdnem az a módszer, mint amiben a quicksort van. Az igazat megvallva soha nem értettem, hogy miért kell itt meghívni egy quicksortot, hiszen amikor ide érünk, akkor a sorozat vége már rendezve van, csak éppen csökkenő sorrendben, tehát elég szimplán megfordítani.

• #15583 K1nG HuNp őstag pmonitor #15582

  Új Válasz 2021-02-26 13:50:55 #15583

  Ú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

  Privát üzenet küldése

  

  K1nG HuNp

  őstag

  válasz pmonitor #15582 üzenetére

  senki sem fogja az i, j, k valtozonevekkel ellatott kododat ordo csekkolni hogy van e erre jobb megoldas, de roviden, igen, mindig van egy robosztus, teljesen tesztelt open source lib ami ezt es tobbet is tud jobban

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