Elektroda.pl
Elektroda.pl
X

Wyszukiwarki naszych partnerów

Wyszukaj w ofercie 200 tys. produktów TME
Europejski lider sprzedaży techniki i elektroniki.
Proszę, dodaj wyjątek elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[C++] Sortowanie przez wybieranie i przez wstawianie

Toshib 30 Kwi 2009 20:00 2896 2
  • #1 30 Kwi 2009 20:00
    Toshib
    Poziom 15  

    Witam, napisałem dwa programy na:

    1. Sortowanie przez wybieranie:

    Code:
    // Sortowanie przez wybieranie
    

    #include <iostream>

    using namespace std;

    bool wprowadzenie_danych(int &ilosc_elementow, int tablica[]);
    int sortowanie_wybieranie(int tablica[], int n);
    int najmniejszy(int tablica[], int n, int start);
    void wypisz_rezultat(int tablica[], int n, int zamiany);
    void wynik_czastkowy(int tablica[], int n, int od, int dokad);


    int main()
    {
       int tablica[100]={0},n,ile_zamian;
       if(wprowadzenie_danych(n, tablica))   // jezeli wprowadzono poprawne dane
       {
          ile_zamian=sortowanie_wybieranie(tablica,n); // to sortujemy
          wypisz_rezultat(tablica,n,ile_zamian);       // i wypisujemy posortowana tablice
       }
       return 0;
    }

    //***********************************************************************************
    // funkcja do wprowadzania danych:
    //***********************************************************************************

    bool wprowadzenie_danych(int &ilosc_elementow, int tablica[])
    {
       cout << "Sortowanie przez wybieranie\n\nPodaj ilosc elementow: ";
       cin >> ilosc_elementow;
       if((ilosc_elementow<1) || (ilosc_elementow>100))   // sprawdzenie poprawnosci danych
       {
          cout << "Zla ilosc elementow!" << endl;
          return false;
       }
       cout << endl;
       for (int i=0; i<ilosc_elementow; i++)              // uzupelnienie tablicy
       {
          cout << "Podaj " << i+1 << " element tablicy: ";
          cin >> tablica[i];
       }
       return true;
    }

    //*************************************************************************************
    // funkcja do wyszukiwania najmniejszego elementu tablicy zaczynajac od elementu start:
    //*************************************************************************************
    int najmniejszy(int tablica[], int n, int start) 
    {
       int minimum=tablica[start], indeks_minimum=start;   // na poczatku zakladamy ze minimalny to pierwszy element




       for(int j=start+1; j<n; j++)      // szukanie kandydata na inne minimum
       {
          if(tablica[j]<minimum)
          {
             minimum=tablica[j];       // jest minimum
             indeks_minimum=j;         // i jego indeks ktory zwracamy do funkcji sortujacej
          }
       }
       return indeks_minimum;
    }

    //****************************************
    // wlasciwa funkcja sortujaca:
    //****************************************
    int sortowanie_wybieranie(int tablica[], int n)
    {
       int temp,licznik_zamian=0;
       for(int k=0; k<n; k++)      // wlasciwa petla sortujaca
       {
          int indeks_najmniejszego=najmniejszy(tablica,n,k);  // szukamy najmniejszego elementu w dalszej czesci tablicy
          if(tablica[k]>tablica[indeks_najmniejszego])        // jezeli biezacy element tablicy jest wiekszy od minimalnego
          {
             temp=tablica[k];                                //
             tablica[k]=tablica[indeks_najmniejszego];       // zamiana
             tablica[indeks_najmniejszego]=temp;             //
             wynik_czastkowy(tablica, n, temp, k);    // wypisujemy czastkowe wyniki
             licznik_zamian++;
          }
       }
       return licznik_zamian;
    }

    //*********************************************************
    // wypisanie stanu tablicy po kazdym kroku sortowania:
    //*********************************************************
    void wynik_czastkowy(int tablica[], int n, int od, int dokad)
    {
       static int licznik_krokow=0;
       if(!licznik_krokow)
       {
          cout << "\n";
       }
       cout << "Krok " << licznik_krokow+1 << ": [";
       licznik_krokow++;
       for(int m=0; m<n; m++)
       {
          cout << tablica[m];
          if(m<n-1) cout << ", ";
          else cout << "]   Zamiana " << od << " ---> " << tablica[dokad] <<  endl;
       }
    }

    //**********************************************
    // wypisanie na ekran posortowanej tablicy:
    //**********************************************
    void wypisz_rezultat(int tablica[], int n, int zamiany)
    {
       cout << endl << "  Posortowana tablica: [";
       for(int m=0; m<n; m++)
       {
          cout << tablica[m];
          if(m<n-1) cout << ", ";
          else cout << "]" << endl;
       }
       cout << "  Ilosc zamian: " << zamiany << endl;
    }


    oraz:
    2. Sortowanie przez wstawianie:
    Code:
    // Sortowanie przez wstawianie
    

    #include <iostream>

    using namespace std;

    int sortowanie_wstawianie(int tablica[], int ilosc_elementow);
    bool wprowadzenie_danych(int tablica[], int &n);
    void pokaz_wyniki(int tablica[], int n, int ile_zamian);
    void czastkowe_wyniki(int tablica[], int n, int od, int dokad);
    double mediana(int tablica[], int n);

    int main()
    {
       int n,tablica[100]={0},ile_zamian;
       if(wprowadzenie_danych(tablica,n))
       {
          ile_zamian=sortowanie_wstawianie(tablica,n);
          pokaz_wyniki(tablica,n,ile_zamian);
       }
       return 0;
    }

    //***********************************************************
    // funkcja sortujaca:
    //***********************************************************
    int sortowanie_wstawianie(int tablica[], int ilosc_elementow)
    {
       int temp, licznik_zamian=0;     // zmienna pomocnicza do zamiany i licznik zamian
       for(int j=1; j<ilosc_elementow; j++)  // petla zewnetrzna, elementy wyjmowane ze zbioru elementow nieposortowanych
       {
          for(int k=0; k<j; k++)    // petla wewnetrzna, porownywane elementy zbioru elementow posortowanych
          {
             if(tablica[j]<tablica[k])  // warunek zamiany, sprawdzamy gdzie upchnac wyjety element
             {
                temp=tablica[j];             //
                tablica[j]=tablica[k];       // zamiana
                tablica[k]=temp;             //
                licznik_zamian++;
                czastkowe_wyniki(tablica,ilosc_elementow,j,k);
             }
          }
       }
       return licznik_zamian;
    }

    //*************************************************
    // wprowadzenie danych:
    //*************************************************
    bool wprowadzenie_danych(int tablica[], int &n)
    {
       cout << "Sortowanie przez wstawianie\n\nPodaj ilosc elementow: ";
       cin >> n;
       if((n<1) || (n>100))   // dbamy o nieprzekroczenie zakresu tablicy
       {
          cout << "Zla liczba elementow!\n";
          return false;
       }
       for(int i=0; i<n; i++)
       {
          cout << "Podaj element nr " << i+1 << ": ";
          cin >> tablica[i];
       }
       return true;
    }

    //*******************************************
    // pokazanie posortowanej tablicy:
    //*******************************************
    void pokaz_wyniki(int tablica[], int n, int ile_zamian)
    {
       cout << "\n  Posortowana tablica:\n    [";
       for(int i=0; i<n; i++)
       {
          cout << tablica[i];
          if(i<n-1) cout << ", ";
          else cout << "]\n";
       }
       cout << "    Ilosc zamian: " << ile_zamian << "\n";
       cout << "    Mediana wynosi: " << mediana(tablica,n) << "\n";
    }

    //*****************************************************
    // pokazywanie czastkowych wynikow po kazdej zamianie:
    //*****************************************************
    void czastkowe_wyniki(int tablica[], int n, int od, int dokad)
    {
       static int krok;
       if(!krok) cout << endl;
       cout << "  Krok nr " << krok+1 << ":  [";
       krok++;
       for(int i=0; i<n; i++)
       {
          cout << tablica[i];
          if(i<n-1) cout << ", ";
          else cout << "]  zamiana: " << tablica[od] << " z " << tablica[dokad] << "\n";
       }
    }

    //**************************************************
    // wyliczenie mediany:
    //**************************************************
    double mediana(int tablica[], int n)
    {
       if(!(n%2))   // dla parzystej liczby elementow
          return (tablica[(n/2)-1]+tablica[n/2])/2.;
       return tablica[n/2]; // dla nieparzystej liczby elementow
    }


    Będę wdzięczny za wszelkie uwagi, spostrzeżenia i porady, które pomogą mi być lepszym programistą.

    Pozdrawiam.

  • #2 02 Maj 2009 21:55
    smagciu
    Poziom 12  

    Ok, fajnie. Jak napisałeś sam te programy to zrozumiałeś na czym polegają dokładnie te algorytmy do sortowania. To jak to już umiesz to teraz polecam bibliotekę STL, tu masz do niej opis Link. Możesz sobie sortowanie robić w jednej linijce. Ogólnie poczytaj jakie możliwości daje Ci ta biblioteka, bo jest ich wiele i warto wiedzieć, że takie coś istnieje.

    Pozdrawiam

  • #3 03 Maj 2009 20:31
    lord_dagoth
    Poziom 25  

    smagciu napisał:
    Ok, fajnie. Jak napisałeś sam te programy to zrozumiałeś na czym polegają dokładnie te algorytmy do sortowania. To jak to już umiesz to teraz polecam bibliotekę STL, tu masz do niej opis Link. Możesz sobie sortowanie robić w jednej linijce. Ogólnie poczytaj jakie możliwości daje Ci ta biblioteka, bo jest ich wiele i warto wiedzieć, że takie coś istnieje.

    Pozdrawiam

    Wypowiedź totalnie bez sensu. Jak dostaje zadanie na przedmiocie Algorytmy i struktury danych napisanie kilku algorytmów sortowania (przez scalanie, kubełkowe, bąbelkowe, kopcowanie) a następnie porównania ich wydajności, to nie ide do wykładowcy i nie mówie mu, że mam STL'a więc po co mam je pisać...

 Szukaj w ofercie
Zamknij 
Wyszukaj w ofercie 200 tys. produktów TME