[C++] Sortowanie bąbelkowe

Forum dotyczące ogólnie pojętego programowania - algorytmów, struktur danych, narzędzi programistycznych, itp - głównie w kontekście komputerów PC.
ODPOWIEDZ
Awatar użytkownika
Luminofor
Użytkownik
Posty: 1375
Rejestracja: 27 lis 2007, 17:17
Lokalizacja: Polska

[C++] Sortowanie bąbelkowe

Post autor: Luminofor » 24 kwie 2009, 23:32

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

Kod: Zaznacz cały

// Sortowanie babelkowe

#include <iostream>

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<n-1; j++)  // wlasciwa petla, do n-1 bo statniego elementu nie musimy sprawdzac
		{
			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<n; k++)
		{
			cout << tablica[k];      // drukujemy czastkowe wyniki sortowania po kazdym kolejnym przejsciu
			if(k<n-1) cout << ", ";  // kosmetyczne, usuwamy przecinek po ostatnim elemencie
		}
		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<n; k++)
	{
		cout << tablica[k];         // drukowanie posortowanej tablicy
		if(k<n-1) cout << ", ";
	}
	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<n; i++)  // petla do podawania elementow
	{
		cout << "Podaj element nr " << i+1 << ": ";
		cin >> tablica[i];
	}
	return 1;  // zwracamy 1 i mozemy sortowac
}

Awatar użytkownika
c4r0
Moderator
Posty: 2152
Rejestracja: 13 kwie 2004, 19:56
Lokalizacja: z lasu
Kontakt:

Post autor: c4r0 » 25 kwie 2009, 13:28

1. Polecał bym używanie printf zamiast cout.
2. Tą tablicę wypadałoby przekazywać do funkcji przez wskaźnik :)

Awatar użytkownika
olo16
Użytkownik
Posty: 396
Rejestracja: 12 paź 2007, 16:37
Lokalizacja: w-wa

Post autor: olo16 » 25 kwie 2009, 13:40

c4r0 pisze:1. Polecał bym używanie printf zamiast cout.
Biblioteka stdio jest już przestarzała. Funkcje z biblioteki iostream są nowsze i łatwiejsze w obsłudze. stdio jest już tylko pozostałością z C.
c4r0 pisze:2. Tą tablicę wypadałoby przekazywać do funkcji przez wskaźnik :smile:
Racja. Tablica już jest wskaźnikiem, więc nie było by to specjalnie trudne. Trzeba by tylko zmienić w deklaracji (i definicji) funkcji zmienić

Kod: Zaznacz cały

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

Kod: Zaznacz cały

void babelki(int * tablica, int n)

MiW
Użytkownik
Posty: 226
Rejestracja: 28 sty 2007, 11:32
Lokalizacja: Kraków
Kontakt:

Post autor: MiW » 25 kwie 2009, 14:35

Zastanówcie się, co piszecie o tablicy. Zastanówcie się.
Wskaźnik do tablicy :lol: "tablica[blah]" to "tablica".
A tablica[1] to *(tablica+1)
I puenta: do funkcji odsyłany jest wskaźnik.

Oto przykładowy kod, który kiedyś musiałem napisać.

Kod: Zaznacz cały

#include <iostream>
using namespace std;
int N=0, n=0,tmpe=0;
bool sorto=true;

main()
{
cin>>N;
int a[100000];
for (int aq;aq<N;aq++) cin>>a[aq]; 
cout<<'-'<<endl;

while (sorto)
{sorto=false;
for (int aw=1;aw<N;aw++)
{
if(a[aw-1]>a[aw])
}
}

for (int i=0;i<N;i++) cout<<a[i]<<' ';
}

Awatar użytkownika
olo16
Użytkownik
Posty: 396
Rejestracja: 12 paź 2007, 16:37
Lokalizacja: w-wa

Post autor: olo16 » 25 kwie 2009, 14:41

MiW, chodziło mi o to, że nazwa tablicy to wskażnik do jej zerowego elemontu, czyli to samo co ty napisałeś:
MiW pisze:A tablica[1] to *(tablica+1)
MiW pisze:I puenta: do funkcji odsyłany jest wskaźnik.
Być może. Ja bym tego nie był taki pewien bez analizy kodu konkretnego kompilatora.

Awatar użytkownika
c4r0
Moderator
Posty: 2152
Rejestracja: 13 kwie 2004, 19:56
Lokalizacja: z lasu
Kontakt:

Post autor: c4r0 » 25 kwie 2009, 15:17

MiW pisze:Zastanówcie się, co piszecie o tablicy. Zastanówcie się.
Wskaźnik do tablicy :lol: "tablica[blah]" to "tablica".
A tablica[1] to *(tablica+1)
I puenta: do funkcji odsyłany jest wskaźnik.
Masz rację, do funkcji odsyłany jest wskaźnik, ale jeśli dobrze rozumiem ten kod to jako argument funkcji jest zadeklarowana nowa tablica zajmująca obszar pamięci, a potem od razu jej wskaźnik jest zmieniany na inne miejsce w pamięci (tablicę przekazywaną). Więc jest jeszcze gorzej, bo pamięć jest zupełnie niepotrzebnie zajmowana i od razu ginie wskaźnik na ten obszar.

BTW czy zapis "int * tablica" jest zupełnie równoważny z "int tablica[]"?

Awatar użytkownika
Luminofor
Użytkownik
Posty: 1375
Rejestracja: 27 lis 2007, 17:17
Lokalizacja: Polska

Post autor: Luminofor » 25 kwie 2009, 15:25

Wydaje mi się, że tak, nazwa tablicy jest jednocześnie wskaźnikiem do jej zerowego elementu, tak było w Symfonii. :)

MiW
Użytkownik
Posty: 226
Rejestracja: 28 sty 2007, 11:32
Lokalizacja: Kraków
Kontakt:

Post autor: MiW » 25 kwie 2009, 15:48

olo16, możesz być pewny bez analizy kompilatora ;P

[ Dodano: 2009-04-25, 20:13 ]
Widzę, że nikt nie zauważył, że dałem śmieć nie kod :razz:
Ale nie chciałem, pomyliły mi się pliki.

Awatar użytkownika
Luminofor
Użytkownik
Posty: 1375
Rejestracja: 27 lis 2007, 17:17
Lokalizacja: Polska

Post autor: Luminofor » 25 kwie 2009, 21:26

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;

Kod: Zaznacz cały

// Sortowanie babelkowe

#include <iostream>

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<n-ilosc_juz_posortowanych; j++)  // wlasciwa petla, do n-1 bo statniego elementu nie musimy sprawdzac
		{
			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<n; k++)
		{
			cout << tablica[k];      // drukujemy czastkowe wyniki sortowania po kazdym kolejnym przejsciu
			if(k<n-1) cout << ", ";  // kosmetyczne, usuwamy przecinek po ostatnim elemencie
		}
		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<n; k++)
	{
		cout << tablica[k];         // drukowanie posortowanej tablicy
		if(k<n-1) cout << ", ";
	}
	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<n; i++)  // petla do podawania elementow
	{
		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.

MiW
Użytkownik
Posty: 226
Rejestracja: 28 sty 2007, 11:32
Lokalizacja: Kraków
Kontakt:

Post autor: MiW » 30 kwie 2009, 19:29

Dla mnie OK, jeżeli chodzi o zasadę działania.

ODPOWIEDZ