C-ben tömb rendezése és eredeti index visszaadása
2019-07-19T13:21:28+02:00
2019-07-24T22:42:38+02:00
2022-08-11T13:50:31+02:00
Molnár László
Sziasztok!

A lehető legegyszerűbb C kóddal kellene megoldanom a következő problémát.

Adott egy tömb amiben számok vannak rendezetlenül.  Ezeknek a növekvően sorba rendezett indexeit kellene átadnom egy másik tömbnek.  Valami ilyesmire gondolok:
(tömb) -> (rendezett) -> (kimenet)
1 - 1 - 1
2 - 1 - 4
2 - 1 - 5
1 - 2 - 2
1 - 2 - 3

Született rá pár megoldásom, de mind akkor bukik el, ha vannak a tömbben azonos értékek is. Erre a fenti példa.
Addig eljutok, hogy létrehozok egy tömböt amiben a rendezett számok vannak.
De nem tudom megoldani, hogy a kettő összehasonlításával megkapjam a harmadik tömböt. 
A rendezett tömbre egyébként nincs szükségek csak más megoldást eddig nem találtam mint, hogy összehasonlítom a rendezett és rendezetlen tömböt. De így sem találom a megoldást.

Előre is köszönöm, ha valaki segít.
Mutasd a teljes hozzászólást!

  • Létrehozol egy sima tömböt az index-ekkel.
    Utána arra simán meghívod a C-s qsort-ot, aminek átadsz egy megfelelő compare függvényt, mely függvény nem az index-eket hasonlítja össze, hanem az eredeti tömbödben indexált elemeket.
    Mutasd a teljes hozzászólást!
  • PicoC -ben kell megoldanom. Nincs benne qsort(). 

    Mezei kódolással kellene megoldanom for, while, if használatával.
    Mutasd a teljes hozzászólást!
  • A kimeneti tömböt feltöltöd az indexekkel (mondjuk 1...5 helyett 0...4-et javasolnék).
    És utána ezt a tömböt úgy rendezed bármilyen ismert algoritmussal, hogy nem a tömbelemeket hasonlítod össze (0...4), hanem az adott indexű elemeket a kiinduló tömbben.
    Mutasd a teljes hozzászólást!
  • Akkor nincs mese, kénytelen leszel magadnak implementálni :)

    Sima rendezés implementálása megvan egész számokra?
    Ha igen, akkor csak annyit kell módosítanod az eredeti kódon, hogy a tényleges összehasonításnál nem a két egészet hasonítod össze, hanem bele indexelsz velük az eredeti tömbbe.

    Meg szabad tudni, hogy mihez készül ilyen környezetben kód? :)
    Mutasd a teljes hozzászólást!
  • Itt a kódod:

    Snippet
    int i, j, tmp1, tmp2;
    int arr1[5] = { 1, 2, 2, 1, 2 };
    int arr2[5] = { 0, 1, 2, 3, 4 };
    for (i = 0; i < 5; i++) {   
    for (j = 0; j < 5; j++)   {     
    if (arr1[j] > arr1)     {     
      tmp1 = arr1
    ;      
     arr1 = arr1[j];     
      arr1[j] = tmp1;      
     tmp2 = arr2
    ;      
     arr2 = arr2[j];      
     arr2[j] = tmp2;    
     }  
     }
    }
    Mutasd a teljes hozzászólást!
  • Most ez a kód fut, de nem teljesen jó:

    while(true) { int bemenetek, aiswap, aqswap, i, j; bemenetek = 5; float ai[bemenetek]; int aq[5] = {0, 1, 2, 3, 4}; // bemenetek ai[] tömbbe for(i = 0; i < bemenetek; i++) { ai[i] = getinput(i); } //ai[] tömb csökkenő rendezése és a aq[] beállítása for (i = 0 ; i < bemenetek ; i++) { for (j = 0; j < bemenetek; j++) { if (ai[i] < ai[j]) { aiswap = ai[i]; ai[i] = ai[j]; ai[j] = aiswap; aqswap = aq[i]; aq[i] = aq[j]; aq[j] = aqswap; } } } for(i = 0; i < bemenetek; i++) { setoutput( i, aq[i]+1 ); } sleeps(10); }

    Itt pl a gondom, ha több azonos érték van a bemeneten akkor is elcsúszik a sorszám.
    6, 6, 6, 6, 10 bemenetre a kimeneten 2,3,4,1,5 lesz az 1,2,3,4,5 helyett.

    És hibázik is. Pl.: 10, 5, 10, 10, 5 esetén a kimenet: 2, 5, 3, 4, 1 

    **G**  Ez egy programozható vezérlő ahol létrehoztam egy 5 be és 5 kimenetű blokkot.
    PicoC-ben lehet programozni.

    A bemenetre különböző fogyasztási adatokat adok és a kimeneten a bemeneti érték emelkedő sorrendű index helyes számok kellenek.
    Mutasd a teljes hozzászólást!
  • Itt pl a gondom, ha több azonos érték van a bemeneten akkor is elcsúszik a sorszám.
    6, 6, 6, 6, 10 bemenetre a kimeneten 2,3,4,1,5 lesz az 1,2,3,4,5 helyett.

    És hibázik is. Pl.: 10, 5, 10, 10, 5 esetén a kimenet: 2, 5, 3, 4, 1

    Amennyire én látom, ezek pedig mindketten helyes kimenetek. Lehet, hogy te nem ezekre gondoltál "helyes" válaszokként, de ha mondjuk a 10, 5, 10, 10, 5-ből veszed sorra a 2, 5, 3, 4, 1 indexeket, az eredmény 5, 5, 10, 10, 10, vagyis egy rendezett adathalmaz.

    Ha az eredeti pozíció is számít nálad, akkor a rendező algoritmusba is bele kéne venned. Mondjuk ha a két hasonlított szám egyenlő, akkor nézd meg az eredeti pozíciójukat is, és vedd azt kisebbnek, aminek kisebb volt az eredeti pozíciója. Így intuitívabb válaszokat fogsz kapni, például az eleve rendezett bemenetekre garantáltan 1, 2, 3, 4, 5 lesz a válasz.
    Mutasd a teljes hozzászólást!
  • Cserélgeted az ai tömb elemeit is, illetve az aq nem vesz részt az összehasonlításban.
    A javaslatom a jelenlegi változóiddal így nézne ki:

    if(ai[aq[i]]<ai[aq[j]]){ aqswap=aq[i]; aq[i]=aq[j]; aq[j]=aqswap; }
    Mutasd a teljes hozzászólást!
  • A javaslatom a jelenlegi változóiddal így nézne ki:

    Nekem ezzel minden sorszám 1 lesz.
    Mutasd a teljes hozzászólást!
  • Nos a következő kódot raktam össze ami úgy tűnik, hogy működik.
    Két baj van csak vele:
    1. Ha valamelyik bemenet nulla akkor a kimenet hibázhat. Konkrétan az fordulhat elő, hogy azonos sorszámok lesznek a kimeneten.
    2. Túl sok a ciklus. Ez a nagyobbik gondom. Ha valaki segítene egyszerűsíteni hálás lennék.

    while(true) { int bemenetek, swap, sorszam, i, j; bemenetek = 5; float ai[bemenetek], ai_rend[bemenetek]; int aq[bemenetek]; // bemenetek ai[] és ai_rend[] tömbbe for(i = 0; i < bemenetek; i++) { ai[i] = getinput(i); ai_rend[i] = getinput(i); } //ai[] tömb csökkenő rendezése ai_rend[] tömbbe for (i = 0 ; i < bemenetek ; i++) { for (j = 0; j < bemenetek; j++) { if (ai_rend[i] < ai_rend[j]) { swap = ai_rend[i]; ai_rend[i] = ai_rend[j]; ai_rend[j] = swap; } } } // Sorrend meghatározás ai[] és ai_rend[] összehasonlításáva // Kimenet beállítása sorszam = 0; for (i = 0 ; i < bemenetek ; i++) { j = 0; while ( j < bemenetek) { if (ai[i] == ai_rend[j]) { aq[i] = j ; ai_rend[j] = 0; // amit már megtaláltam nullázom, hogy folytonos legyen a sorszámozás j = bemenetek; } else { j++; } } } for(i = 0; i < bemenetek; i++) { setoutput( i, aq[i]+1 ); } sleeps(10); }
    Mutasd a teljes hozzászólást!
  • 2. Túl sok a ciklus. Ez a nagyobbik gondom

    Ez miért gond?
    Mutasd a teljes hozzászólást!
  • Nemtom, maga az ötlet mindenesetre valamit azért csinál:

    int main(void) { int bemenet[]={10,10,5,10,5,4,2,6,3,1,2}; int indexek[]={ 0, 1,2, 3,4,5,6,7,8,9,10}; for(int i=0;i<10;i++) for(int j=i+1;j<11;j++) if(bemenet[indexek[j]]<bemenet[indexek[i]]){ int csere=indexek[i]; indexek[i]=indexek[j]; indexek[j]=csere; } for(int i=0;i<11;i++) printf("%d. %d\n",indexek[i],bemenet[indexek[i]]); return 0; }
    Kipróbálható itt: Ideone.com
    Mutasd a teljes hozzászólást!
  • Szia!

    Ez a feladat az "Indextáblás rendezés".
    Van egy "t" tömb ami rendezetlen elemeket tartalmaz, "N" darabot. Kell egy másik tömb "IT" (indextábla) amit feltöltünk 0-tól N-1-ig. Ezek lesznek az indexek, amiket rendezni fogunk.

    A függvény deklarációja: void Rendez(int t[] , int *IT, int n);

    t[]: a rendezendő elemeket tartalmazó tömb.
    *IT: az indextábla első elemére mutató pointer.
    n: a rendezendő elemek száma.

    Azért void típusú a függvény mivel egy egész tömböt nem lehet returolni. Egy lehetőség, hogy egy pointert returnolunk ami az indextábla első elemére fog mutatni. A másik lehetőség, amit választottam, hogy helyben rendezzük az Indextáblát a pointer segítségével így nem kell returnolni semmit. Ezért használjuk az IT pointert a függvényben.

    #include <stdio.h> #define MAX 7 void Rendez(int t[],int *IT,int n) { //t[] = a rendezendő elemek tömbje, //IT[] = a rendezett indexeket tartalmazó tömb, //n a rendezendő elemek száma (t[] tömb elemszáma) int k = 0; int cs = 0; for (int i = 0; i < n; ++i) //Feltöltjük egyenlőre rendezetlenül indexek számokkal. 0-tól n-ig //Ezt a tömböt fogjuk igazából rendezni. { IT = i; } for (int i = 0; i < n - 1 ; ++i) { //Kiválasztjuk az i. indexű elemet k-nak. //és megnézzük hogy utána van e kisebb elem. //Lényegében megkeressük a legkisebb elemet mindig amit még nem rendeztünk. k = i; for (int j = i+1; j < n; ++j) { if (t[IT[j]] < t[IT[k]]) //Ha van kisebb elem akkor //elmentjük az indexét és tovább keresünk van e még kisebb. k = j; } //Ha ez a k nagyobb (mivel az elején egyenlő volt i-vel csak nagyobb lehet mert "jobbra" keresünk" //akkor az az elem nem jó helyen van, kicseréljük a megfelelő helyre. //Tehát az aktuális ciklusban kijelöl "i." indexű elemnél találtunk kisebbet, ezért megcseréljük a kettőt. if (k > i) { cs = IT; IT = IT[k]; IT[k] = cs; } } } int main() { int t[] = {5,2,7,4,6,4,1}; int IT[MAX]; Rendez(t,IT, MAX); printf("Rendezendő elemek száma: %d\n",MAX); printf("\Rendezendő tömb t[]:\t\t"); for (int i = 0; i < MAX; ++i) { printf(" %d", t); } printf("\nIndexek rendezés előtt IT[]:\t"); for (int i = 0; i < MAX; ++i) { printf(" %d", i); } printf("\n\nRendezendő tömb t[]:\t\t"); for (int i = 0; i < MAX; ++i) { printf(" %d", t[IT]); } printf("\nIndexek rendezés után IT[]:\t"); for (int i = 0; i < MAX; ++i) { printf(" %d", IT); } }
    Output:
    Rendezendő elemek száma: 7                                                                                                                           


    Rendezendő tömb t[]:             5 2 7 4 6 4 1                                                                                                       
    Indexek rendezés előtt IT[]:     0 1 2 3 4 5 6                                                                                                       
                                                                                                                                                         
    Rendezendő tömb t[]:             1 2 4 4 5 6 7                                                                                                       
    Indexek rendezés után IT[]:      6 1 3 5 0 4 2




    Remélem sikerült segítenem.

    Mutasd a teljes hozzászólást!
  • PS.: Utólag vettem észre, hogy valamilyen oknál fogva nem jól másoltam át a kódot.

    Az első for ciklusban:

    IT = i; helyett IT[i] = i;


    A második for ciklusban pedig a második if-en belül:
    cs = IT;
    helyett
    cs = IT[i]
    alatta pedig
    IT[i] = IT[k];
    Mutasd a teljes hozzászólást!
  • Köszönöm. Érdekes megoldás legalábbis számomra. Viszont a végeredményt nem értem és nem az mint amire szükségem van.

    Ha a rendezetlen tömb: 5 2 7 4 6 4 1
    Az rendezve:  1 2 4 4 5 6 7

    Eddig oké. Viszont erre nekem a következő "rendezett index lenne a jó":  4 1 6 2 5 3 0

    Az eredeti tömb [0] index értéke az 5
    A rendezett sorban ez a 4. index így 4 kell a kimenetre

    Az eredeti tömb [1] index értéke a 2
    A rendezett sorban ez a 1. index így 1 kell a kimenetre

    Az eredeti tömb [2] index értéke a 7
    A rendezett sorban ez a 6. index így 6 kell a kimenetre

    És így tovább.
    Mutasd a teljes hozzászólást!
  • Mutasd a teljes hozzászólást!
  • Ezt most nem értem....
    Mutasd a teljes hozzászólást!
  • Egy bedrótozott bemenetre azt írja ki, amit kértél: rendezett elemek pozícióit az eredeti tömbben, meg a kényelem kedvéért az értéküket is.
    Az általad már implementált "egyszerű csere" (azt hiszem ez a neve) alapú rendezést használva.
    A példa bemenet 10,10,5,10,5,4,2,6,3,1,2
    A kimenet meg
    9. 1 (a legkisebb elem az eredeti tömbben a 9. helyen lévő 1-es)
    6. 2 (a második legkisebb elem az eredeti tömbben a 6. helyen lévő 2-es)
    10. 2 (a harmadik legkisebb elem az eredeti tömbben a 10. helyen lévő 2-es)
    8. 3
    5. 4
    4. 5
    2. 5
    7. 6
    0. 10
    3. 10
    1. 10
    A kódban még meg is van formázva, hogy viszonylag egyszerűen lehessen követni az elemek eredeti pozícióját:

    elemek 10,10,5,10,5,4,2,6,3,1,2 pozíció 0, 1,2, 3,4,5,6,7,8,9,10
    Hiányzik még valami?
    Mutasd a teljes hozzászólást!
  • Á, igen már látom, félreértettem a feladatot az elején.
    A kódomat kiegészítve viszont könnyen eljuthatunk a megoldáshoz:

    Ugye itt az indexeket hozzárendeltük lényegében az egyes elemekhez és rendezve lettek az indexek. Elég csak megkeresni, hogy hányadik helyre kerültek el az egyes indexek. Tehát például maradjunk a felhozott példánál:

    Rendezendő tömb t[]:             5 2 7 4 6 4 1                                                                                                      
    Indexek rendezés előtt IT[]:     0 1 2 3 4 5 6

    Rendezendő tömb t[]:             1 2 4 4 5 6 7                                                                                                      
    Indexek rendezés után IT[]:      6 1 3 5 0 4 2

    Az 5-ös (t[0]) indexe a 0 ugye, a 0 pedig a rendezés után IT-ben az IT[4] helyen van ezt ugyanígy végig kell nézni a többire. Ezt én 2 for ciklussal valósítottam meg. Minden elemet megnézünk és mindegyiknek megkeressük hányadik helyen van az indexe a rendezés után:
    Az új tömb, amibe a "válasz" kerül a Result nevű tömb lesz. Ezt szintén ugyanúgy átadom a függvénynek mint, ahogy az IT-vel tettem.

    Tehát a kód kiegészítve (csak a függvényt írtam ide, mert már túl hosszú lenne az egész):

    void Rendez(int t[], int* IT, int n, int * Result) { //t[] = a rendezendő elemek tömbje, //IT[] = a rendezett indexeket tartalmazó tömb, //n a rendezendő elemek száma (t[] tömb elemszáma) int k = 0; int cs = 0; int q; for (int i = 0; i < n; ++i) //Feltöltjük egyenlőre rendezetlenül indexek számokkal. 0-tól n-ig //Ezt a tömböt fogjuk igazából rendezni. { IT[i] = i; } for (int i = 0; i < n - 1; ++i) { //Kiválasztjuk az i. indexű elemet k-nak. //és megnézzük hogy utána van e kisebb elem. //Lényegében megkeressük a legkisebb elemet mindig amit még nem rendeztünk. k = i; for (int j = i + 1; j < n; ++j) { if (t[IT[j]] < t[IT[k]]) //Ha van kisebb elem akkor //elmentjük az indexét és tovább keresünk van e még kisebb. k = j; } //Ha ez a k nagyobb (mivel az elején egyenlő volt i-vel csak nagyobb lehet mert "jobbra" keresünk" //akkor az az elem nem jó helyen van, kicseréljük a megfelelő helyre. //Tehát az aktuális ciklusban kijelöl "i." indexű elemnél találtunk kisebbet, ezért megcseréljük a kettőt. if (k > i) { cs = IT[i]; IT = IT[k]; IT[k] = cs; } } //Az "i" jelenti hogy melyik indexet keresem éppen //a "q" lesz a válasz hogy hányadik helyre került az "i" index //Ezt az egészet szintén egy tömbbe mentem, amire itt egy pointer mutat. for (int i = 0; i < MAX; ++i) { for (q = 0; IT[q] != i; q++) { } Result[i] = q; } }
    Output:

    Rendezendo elemek szama: 7

    Rendezendo tomb a rendezés előtt t[]: 5 2 7 4 6 4 1

    Result tömb a rendezés után: 4 1 6 2 5 3 0

    A rendezett tomb t[]: 1 2 4 4 5 6 7

    A kódon szerintem még lehet szépíteni rövidíteni én csak egy lehetséges egyszerű megoldással szerettem volna szolgálni, remélem ez már a megfelelő megoldás.

    Mutasd a teljes hozzászólást!
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd