[C++] Sortowanie przez wybieranie i przez wstawianie


(Kanaliaon) #1

Witam, napisałem dwa programy na:

  1. Sortowanie przez wybieranie:

    // Sortowanie przez wybieranie

    include

    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
    {
    
    	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
    {
    
    	if(tablica[j]
    	{
    
    		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
    {
    
    	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
    {
    
    	cout << tablica[m];
    
    	if(m
    	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
    {
    
    	cout << tablica[m];
    
    	if(m
    	else cout << "]" << endl;
    
    }
    
    cout << " Ilosc zamian: " << zamiany << endl;

    }

oraz: 2. Sortowanie przez wstawianie:

// Sortowanie przez wstawianie


#include 


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
	{

		for(int k=0; k
		{

			if(tablica[j]
			{

				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
	{

		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
	{

		cout << tablica[i];

		if(i
		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
	{

		cout << tablica[i];

		if(i
		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.


(Kojot) #2

Jeśli opanowałeś już wskaźniki to polecam dynamiczne alokowanie pamięci na tablicę, zamiast ustalania stałego rozmiaru.

Poza tym ta linijka z kropką na końcu Ci się kompiluje?

return (tablica[(n/2)-1]+tablica[n/2])/2.;

(Kanaliaon) #3

Tak, ta kropka to niejawny casting z int na double.


(Kojot) #4

No tak, przecież mediana musi być typu double, moim zdaniem ok;)


([alex]) #5

Może głupie pytanie, ale czym to wybieranie różni się od bąbielkowego? :lol:


(Kanaliaon) #6

O które pytasz? Bąbelkowe porównuje element bieżący z następnym i jeżeli następny jest mniejszy od poprzedniego to je zamienia i tak aż wszystkie posortuje, wybieranie wyszukuje element minimalny począwszy od nastepnego od bieżącego i zamienia miejscami minimalny i bieżący, a wstawianie działa na zasadzie jaką stosujesz układając karty w talii - wyciągasz następny element i wkładasz go w odpowiednie miejsce. W necie można znaleźć opisy, animacje i wirtualne demonstracje tych algorytmów. :slight_smile:


([alex]) #7

Opisałeś ten pierwszy, ale ja pytam o ten drugi, w tym drugim widzę sortowanie bąbelkowe.


(Kanaliaon) #8

To nie jest bąbelkowe, bąbelkowe masz tu: viewtopic.php?f=23&t=326613#p2143857

W sortowaniu przez wstawianie zrobiłem 2 pętle, jedna dla wypychania bieżącego elementu (zewnętrzny for) a druga do sprawdzania gdzie go włożyć (wewnętrzny for).

W bąbelkach po prostu sprawdzałeś czy następny element jest mniejszy od poprzedniego i jeżeli tak to je zamieniałaś i leciałeś dalej aż licznik zamian osiągnie 0 w przejściu przez tablicę. Także w bąbelkach mogło być wiele przejść przez tablicę, a o ile się nie mylę, to w sortowaniu przez wstawianie tylko raz przechodzi przez tablicę i od razu ustawia w odpowiedniej kolejności.


([alex]) #9

Może jednak porównasz kody. :smiley: