Elektroda.pl
Elektroda.pl
X
Elektroda.pl
Proszę, dodaj wyjątek dla www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

mini program QUICKSORT jak działa?

27 Mar 2006 21:46 1411 4
  • Uczeń
    Program bierze pierwszy element tablicy. Po lewej stronie od pierwszego elementu tablicy liczby mają być mniejsze a po prawej większe lub równe od pierwszego elementu - jest to program będacy częścią programu QUICKSORT - mam parę pytań bo tu trzeba działac na wskaźnikach:

    #include<stdio.h>
    #include <conio.h>
    int swap(int*x, int*y);
    int rozsortuj(int tab[]);
    int pisz(int tab[]);
    int main()
    {
    int tab[10]={3,2,1,9,5,6,1,3,4,3};
    pisz(tab);
    rozsortuj(tab);
    pisz(tab);
    getch ();
    return 0;
    }


    int pisz(int tab[])
    {
    int i;
    printf("\n");
    for(i=0; i<10; i++)
    printf("%d, ", tab[i]);
    }



    int swap(int*x, int*y)
    {
    int temp;
    temp=*x;
    *x=*y;
    *y=temp;
    }



    int rozsortuj(int tab[])
    {
    int i=1, j=9;
    while(i<j)
    {
    if(tab[i]>tab[0])
    if(tab[j]<tab[0])
    swap (&tab[i], &tab[j]);
    else
    j--;
    else
    i++;
    }
    if(tab[0]>tab[i])
    swap(&tab[0], &tab[i]);
    else
    swap(&tab[0], &tab[i-1]);
    }


    1. jak działa ten int swap(int*x, int*y) - do czego on służy ?
    2.
    czy mógłby mi ktoś wytłumaczyć to:
    if(tab[i]>tab[0])
    if(tab[j]<tab[0])
    swap (&tab[i], &tab[j]);
    else
    j--;
    else
    i++;

    a może da się to sformułować jaśniej, bo jeśli miałbym to przetłumaczyć to wychodzi: jeśli i=1 (czyli 2. element tablicy) jest większy od 1. elementu tablicy to .... no właśnie to co - bo potem znowu jest if ???
  • Poziom 12  
    Cytat:
    a może da się to sformułować jaśniej, bo jeśli miałbym to przetłumaczyć to wychodzi: jeśli i=1 (czyli 2. element tablicy) jest większy od 1. elementu tablicy to .... no właśnie to co - bo potem znowu jest if ???


    Funkcja jest prosta tyle że nie jest to już pascal więc trzeba pomyśleć :idea:

    Code:
    if(tab[i]>tab[0])  #JEŻELI(1)  
    
          if(tab[j]<tab[0])  #TO JEŻELI(2)
                 swap (&tab[i], &tab[j]); #(1) i (2) true
          else j--; #(1) true (2) false 
    else i++; #(1) false


    proponuję poczytać sobie jakąś książkę o podstawach C++ i logice tworzenia programów, a przy okazji jak piszesz kod używaj wcięć to będziesz widział co do czego jest :)

    a co do wcześniejszego pytania
    Cytat:
    int swap(int*x, int*y)

    to takie posty powinny być usuwane z forum. wpisz w google "c++ swap" i pierwszy wynik http://www.intercon.pl/~sektor/cbx/basics/functions.html

    pozdrawiam i mniej lenistwa
  • Uczeń
    dziwny ten jakiś swap
    do tej pory jak robiłem proste programy to żeby zamienić miejscami dwie liczby wystarczyło użyć:
    temp=a;
    a=b;
    b=pom;

    a teraz przyszły tablice i nagle wyskakuje taki SWAP - dziwne.....
  • Poziom 12  
    Dałem Ci linka, poczytaj i się dowiesz po co to jest :)

    pozdrawiam
  • Poziom 15  
    Code:

    int swap(int*x, int*y)
    {
    int temp;
    temp=*x;
    *x=*y;
    *y=temp;
    }


    proste:
    masz dwa argumenty x i y, oba są wskażnikami na zmienną typu int
    int temp; // chyba oczywiste
    jak masz np linię 'swap (&tab[i], &tab[j]);' to
    temp=*x; // to jest 'temp = tab[i]'
    *x=*y; // to *x to jest tab[i] a *y jest tab[j] czyli 'tab[i] = tab[j]'
    potem
    *y=temp; // czyli 'tab[j] = tmp'

    taka jest idea tego kodu

    zbędny jest tu zapis
    int swap(int *x, int *y);
    może byc
    void swap(int *x, int *y);
    gdyż nic nie zwracamy ;-)

    Dodano po 1 [godziny] 5 [minuty]:

    co do funkcji

    Code:

    int rozsortuj(int tab[])
    {
        int i=1, j=9;
        while(i<j)
        {
            if(tab[i]>tab[0])
                if(tab[j]<tab[0])
                    swap (&tab[i], &tab[j]);
                else
                    j--;
            else
                i++;
        }

        if(tab[0]>tab[i])
            swap(&tab[0], &tab[i]);
        else
            swap(&tab[0], &tab[i-1]);
    }


    to sprawa jest prosta
    tablica ma 10 elementów (int tab[])
    tak to jest w programie ustawione na sztywno
    i = 1 czyli drugi element tablicy
    j = 9 czyli ostatni element tablicy
    while(i<j) chyba oczywiste i bedzie zwiększane a j będzie zmienszane,
    tak w kolejnych krokach pętli będziemy się poruszać
    zależnie od wartości w tablicy i wyników działania instruckji if
    if(tab[i]>tab[0]) czyli jeśli zaczynając od drugiego elementu porównujemy kolejno z pierwszym elementem tablicy tab[0]
    i jesli liczba w tab[i] jest wieksza to sprawdzamy czy aktualny tab[j] jest mniejszy od 1 elementu tablicy, jesli tak to zamieniamy tab[i] z tab[j]
    chodzi tu o to że sprawdzamy porównują kolejne elementy z pierwszym elementem tablicy i jesli jest on wiekszy to nalezy sprawdzic czy tab[j] jest mniejszy od elem. 1 tablicy, jesli nie byl mniejszy to przesuwamy sie e górę tablicy licznikiem j (j--), natomiast jesli tab[i]>tab[0] jest falszem to przesuwamy sie licznikiem i o jeden w dół tallicy, tak dlugo sie kod wykonuje (petli while) az i bedzie mniejsze od j, czyli gdy przejdziemy wszystkie elementy tablicy

    na koncu juz jedynie zostaje do sprawdzenie pierwszego elementu
    i dokonanie odpowiedniej zamiany

    tyle na temat kodu,
    najlepiej przesledzic w debugerze kolejne kroki jakie ta funkcja wykonuje,
    ja tylko wytlumaczylem jak kod dziala a nie algorytm