[C++] Sortowanie bąbelkowe

Leogict · 24 Kwiecień 2009 22:33

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 · 25 Kwiecień 2009 00:47

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];

Leogict · 25 Kwiecień 2009 20:29

Dokonałem paru poprawek:

Tablice przesyłane do funkcji w sposób tablica[], a więc poprzez wskaźnik do ich zerowego elementu;
Lepsza kontrola danych wejściowych (n>100);
Funkcja nie sortuje elementów już posortowanych, co przyspiesza algorytm i zmniejsza liczbę wywołań wewnętrznej funkcji;

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 · 25 Kwiecień 2009 20:53

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.