[C++] Sortowanie bąbelkowe


(Kanaliaon) #1

Oto mój kod na sortowanie bąbelkowe, będę wdzięczny za wszelkie uwagi, spostrzeżenia i porady.

// Sortowanie babelkowe


#include 


using namespace std;


void babelki(int tablica[100], int n);

int pobranie_danych(int &n, int tablica[100]);  

// n przesylamy do funkcji przez referencje, bo chcemy pracowac na oryginalnej zmiennej w funkcji a nie jej kopii,

// tablica z definicji jest przesylana przez referencje


int main()

{

	int n,tablica[100]={0};

	if(pobranie_danych(n, tablica)) // jezeli wlasciwe dane(n>0)

	babelki(tablica, n); // to wywolujemy wlasciwa funkcje

	return 0;

}


// *****************************************************************************


void babelki(int tablica[100], int n)

{

	int temp, counter=1, liczba_zamian=0, ilosc_przejsc=0;

	while(counter) // dopoki wystepuje co najmnniej jedna zamiana 2 elementow w tablicy

	{

	counter=0; // zerujemy licznik zamian w jednym przejsciu tablicy

		for(int j=0; j
		{

			if(tablica[j]>tablica[j+1]) // warunek zamiany

			{

				temp=tablica[j+1]; //

				tablica[j+1]=tablica[j]; // zamiana

				tablica[j]=temp; //

				counter++; // wewnetrzny licznik ilosci zamian w jednym przejsciu tablicy

			}

		}

		if(!ilosc_przejsc) cout << endl; // kosmetyczne

		cout << "Przejscie nr " << ilosc_przejsc+1 << ": [";

		for(int k=0; k
		{

			cout << tablica[k]; // drukujemy czastkowe wyniki sortowania po kazdym kolejnym przejsciu

			if(k
		}

		cout << "]" << endl;

		liczba_zamian=liczba_zamian+counter; // laczna liczba zamian

		ilosc_przejsc++; // liczba przejsc tablicy

	}

	cout << endl << "Posortowana tablica: " << endl << " [";

	for(int k=0; k
	{

		cout << tablica[k]; // drukowanie posortowanej tablicy

		if(k
	}

	cout << "]" << endl << endl << "Ilosc zamian liczb: " << liczba_zamian << endl;

	cout << "Ilosc przejsc przez tablice: " << ilosc_przejsc << endl;

}


// *****************************************************************************


int pobranie_danych(int &n, int tablica[100])

{

	cout << "Podaj liczbe wyrazow n: ";

	cin >> n;

	if(n<=0)

	{

		cout << "Zla liczba wyrazow!" << endl;

		return 0; // zwracamy 0 czyli sortowanie sie nie odbedzie

	}

	for(int i=0; i
	{

		cout << "Podaj element nr " << i+1 << ": ";

		cin >> tablica[i];

	}

	return 1; // zwracamy 1 i mozemy sortowac

}

([alex]) #2

Po pierwszym przejściu sortowania "najcięższy bąbelek" zostanie "pochwycony" i spadnie na sam dół tablicy.

Więc na drugim nie trzeba iść do końca tablicy tylko o jeden element mniej.

Na trzecim przejściu jeszcze o jeden mniej, itd.

Interfejs użytkownika nie jest odporny na "blondynkę".

Wpisanie liter zamiast liczby* spowoduje załamanie działania programu.

\ ***Podaj liczbe wyrazow n:** dużo

Bez sensu przekazujesz rozmiar tablicy:

int pobranie_danych(int &n, int tablica[100]);

wystarczy:

int pobranie_danych(int &n, int tablica[]);

lub:

int pobranie_danych(int &n, int *tablica);

pobranie_danych nie sprawdza czy wprowadzona ilość nie "wyłazi" poza tablicę.

Sugestie:

int *pobranie_danych(int &n); // zwraca 0 jeżeli źle podano n lub przydzielony dynamicznie obszar na tablicę.

albo (zauważ że niema żadnego if'a ani skoku) ((!i)<<1) == 2*!i == i?0:2:

cout << (", "+((!i)<<1)) << tablica[k];

cout << tablica[k];

         if(k


może lepiej:

[code] if(k) cout << ", "; cout << tablica[k];


(Kanaliaon) #3

Dokonałem paru poprawek:

  1. Tablice przesyłane do funkcji w sposób tablica[], a więc poprzez wskaźnik do ich zerowego elementu;

  2. Lepsza kontrola danych wejściowych (n>100);

  3. Funkcja nie sortuje elementów już posortowanych, co przyspiesza algorytm i zmniejsza liczbę wywołań wewnętrznej funkcji;

  4. Funkcja pobierania danych zwraca typ bool;

    // Sortowanie babelkowe

    include

    using namespace std;

    void babelki(int tablica[], int n);

    bool pobranie_danych(int &n, int tablica[]);

    // n przesylamy do funkcji przez referencje, bo chcemy pracowac na oryginalnej zmiennej w funkcji a nie jej kopii,

    // tablica z definicji jest przesylana przez referencje

    int main()

    {

    int n,tablica[100]={0};
    
    if(pobranie_danych(n, tablica)) // jezeli wlasciwe dane(n>0)
    
    babelki(tablica, n); // to wywolujemy wlasciwa funkcje
    
    return 0;

    }

    // *****************************************************************************

    void babelki(int tablica[], int n)

    {

    int temp, counter=1, liczba_zamian=0, ilosc_juz_posortowanych=1, ilosc_przejsc=0, licz=0;
    
    while(counter) // dopoki wystepuje co najmnniej jedna zamiana 2 elementow w tablicy
    
    {
    
    counter=0; // zerujemy licznik zamian w jednym przejsciu tablicy
    
    	for(int j=0; j
    	{
    
    		if(tablica[j]>tablica[j+1]) // warunek zamiany
    
    		{
    
    			temp=tablica[j+1]; //
    
    			tablica[j+1]=tablica[j]; // zamiana
    
    			tablica[j]=temp; //
    
    			counter++; // wewnetrzny licznik ilosci zamian w jednym przejsciu tablicy
    
    		}
    
    	}
    
    	ilosc_juz_posortowanych++;
    
    	if(!ilosc_przejsc) cout << endl; // kosmetyczne
    
    	cout << "Przejscie nr " << ilosc_przejsc+1 << ": [";
    
    	for(int k=0; k
    	{
    
    		cout << tablica[k]; // drukujemy czastkowe wyniki sortowania po kazdym kolejnym przejsciu
    
    		if(k
    	}
    
    	cout << "]" << endl;
    
    	liczba_zamian=liczba_zamian+counter; // laczna liczba zamian
    
    	ilosc_przejsc++; // liczba przejsc tablicy
    
    }
    
    cout << endl << "Posortowana tablica: " << endl << " [";
    
    for(int k=0; k
    {
    
    	cout << tablica[k]; // drukowanie posortowanej tablicy
    
    	if(k
    }
    
    cout << "]" << endl << endl << "Ilosc zamian liczb: " << liczba_zamian << endl;
    
    cout << "Ilosc przejsc przez tablice: " << ilosc_przejsc << endl;

    }

    // *****************************************************************************

    bool pobranie_danych(int &n, int tablica[])

    {

    cout << "Podaj liczbe wyrazow n: ";
    
    cin >> n;
    
    if((n<=0) || (n>100))
    
    {
    
    	cout << "Zla liczba wyrazow!" << endl;
    
    	return 0; // zwracamy 0 czyli sortowanie sie nie odbedzie
    
    }
    
    for(int i=0; i
    {
    
    	cout << "Podaj element nr " << i+1 << ": ";
    
    	cin >> tablica[i];
    
    }
    
    return 1; // zwracamy 1 i mozemy sortowac

    }

Będę nadal wdzięczny za wszelkie uwagi, spostrzeżenia i porady.


([alex]) #4

Kiedy przekazywałeś do funkcji int tablica[100] tez przekazywało się przez wskaźnik na pierwszy element.

for(int j=0; j

while(count) zamień na for(int k=n-1;(k>0)&&(count);--k) a zamiast n-ilosc_juz_posortowanych wstaw "k"

Owszem niewiele to przyspieszy tym bardziej że na każdy kroku na cout coś piszesz, ale bardzo ważne aby ręka nauczyła się pisać optymalnie, nie licząc na to że kiedyś rozwój techniki pozwoli zoptymalizować to na etapie kompilacji.