09

Gru

Sortowanie bąbelkowe, przez wybór i wstawianie

W tym wpisie przedstawię implementacje podstawowych algorytmów sortowania przy użyciu C# i Windows Form. Sortowanie przydatne jest wtedy gdy chcemy przedstawić nieuporządkowane dane w sposób bardziej zrozumiały, więcej na temat sortowania można przeczytać w Wikipedii. Podczas dzisiejszego wpisu do sortowania użyjemy wygenerowanych liczb które będziemy porządkować od najmniejszej do największej.
Liczby wygenerowane jak i posortowane pokazywać będziemy w textBoxie a więc do naszego projektu dodajemy textBox oraz ustawiamy jego wartości Multiline i ReadOnly na true a ScrollBars na Vertical.

  1. Generator liczb
    1. MaskedTextBox
    2. Do programu dodajemy maskedTextBox w którym podawać będziemy ilość liczb do wylosowania, ustawiamy jego wartość Mask na 999, maska ta oznacza że możliwe jest wpisanie tylko 3 cyfr i .

    3. Kod działania
    4. Generator będzie się uruchamiał po naciśnięciu buttona dlatego dodajemy button do projektu i w wartości Text wpisujemy „Wygeneruj liczby”. Teraz należy zaprogramować działanie buttona dlatego w metodzie button1_Click dodajemy poniższy kod.

//Czyszczeie texboxa z wygenerowanymi liczbami
textBox1.Clear();
//Określenie ziarna losowania na milisekundy z zegaru systemowego
Random rand = new Random(DateTime.Now.Millisecond);
//Zabezpieczenie przed pozostawieniem maskedTextBoxa pustego
try
	{
	//Przypisanie ilości liczb do wygenerowania (count zmienna globalna)
	count = Convert.ToInt32(maskedTextBox2.Text);
        //Dodanie do textboxa pierwszej lczby z zakresu od 0 do 1000 (bez nowej lini)
	textBox1.Text = rand.Next(0, 1000).ToString();
	}
//Jeżeli maskedbox jest pusty
catch
	{
		count = 0;
	}
for (int i = 1; i < count; i++)
	//Dodanie do textboxa kolejnej liczby wraz z poczatkeim nowej lini
	textBox1.Text += "\r\n" + rand.Next(0, 1000).ToString();

  1. Sortowanie Bąbelkowe
    1. Opis działania
    2. Algorytm polega na porównywaniu dwóch elementów tablicy, bieżącego i następnego. Jeżeli element bieżący jest większy od następnego to należy zamienić je miejscami i zacząć sprawdzanie od nowa aż do uzyskania sytuacji gdzie element bieżący nie jest większy od następnego.

    3. Kod działania
    4. Po naciśnięciu buttona nr 2 uruchamiany jest poniższy kod, dzięki któremu w textBoxie nr 2 możemy zobaczyć prostowaną listę wygenerowanych liczb.

//Czyszczenie textboxa z wcześniejszych sortowań
textBox2.Clear();
//Deklarowanie tablicy z liczbami do posortowania
int[] tab;
//Zmienna pomocnicza, bufor
int buf;
//Egzemplarz tablicy
tab = new int[count];
//Przypisywanie wygenerowanych liczb do tablicy
for (int i = 0; i < count; i++)
	tab[i] = Convert.ToInt32(textBox1.Lines[i]);
//Algorytm sortowania bąbelkowego
//Ilość elementów musi być mniejsza o 1 od wielkości tablicy
for (int j = 0; j < count - 1; j++)
{
	//Jeżeli element tablic jest większy od następnego
	if (tab[j] > tab[j + 1])
	{
		//Przypisz do zmiennej pomocniczej wartośc elementu tablicy
		buf = tab[j];
		//Przypisz do tablicy  element o 1 większy
		tab[j] = tab[j + 1];
		//Przypisz do elementu tablicy o 1 większego wartość zmiennej pomocniczej
		tab[j + 1] = buf;
		//Ustaw pętle for na 0
		j = -1;
	}
}
//Zabezpieczenie przed pustym masked boxem
try
	{
		//Przypisz 1 element tablicy, bez nowej lini, do textboxa
		textBox2.Text += tab[0].ToString();
		//Wypisz pozostałe posortowane elementy tablicy
		for (int k = 1; k < count; k++)
			textBox2.Text += "\r\n" + tab[k].ToString();
	}
//Wypisanie komunikatu jeżeli wystąpił błąd
catch
	{
		textBox2.Text = "Błąd sortowania!";
	}

  1. Sortowanie przez wybór
    1. Opis działania
    2. Algorytm co przebieg pętli wyszukuje element najmniejszy, nie biorąc pod uwagę już wcześniej umiejscowionych na odpowiednim miejscu wartościach, i ustawia go na pierwszej dostępnej pozycji przez co lista elementów do posortowania zmniejsza się o 1. Algorytm kończy działanie gdy wszystkie elementy znajdą się na swoim docelowym miejscu.

    3. Kod działania
    4. Sortowanie przez wybór będzie uruchamiane analogicznie do sortowania bąbelkowego czyli po naciśnięciu buttona. Natomiast różnicą jest sposób sortowania oraz to, iż posortowany „przez wybór” zbiór wyświetlony będzie w textBoxie nr 3, za co odpowiedzialny jest poniższy kod.

//Czyszczenie textboxa z wcześniejszych sortowań
textBox3.Clear();
//Deklarowanie tablicy z liczbami do posortowania
int[] tab;
//Zmienna pomocnicza, bufor
int buf;
//Egzemplarz tablicy
tab = new int[count];
//Przypisywanie wygenerowanych liczb do tablicy
for (int i = 0; i < count; i++)
	tab[i] = Convert.ToInt32(textBox1.Lines[i]);
//Algorytm sortowania przez wybór
//Ilość elementów musi być mniejsza o 1 od wielkości tablicy
for (int j = 0; j < count - 1; j++)
{
	//ustaw licznik drugiej liczby na 1. nieposortowaną liczbę
	for (int k = j; k < count -1; k++)
	{
		//Jeżeli element nieposortowany jest mniejszy to zamień wartości
		if (tab[k + 1] < tab[j])
		{
			//Przypisz do zmiennej pomocniczej wartośc elementu tablicy psortowanej                           
			buf = tab[j];
			//Przypisz do tablicy posorotwanej element nieposortowany      
			tab[j] = tab[k + 1];
			//Przypisz do elementu tablicy nieposortowanej wartość zmiennej pomocniczej
			tab[k + 1] = buf;
		}
	}
}
//Zabezpieczenie przed pustym masked boxem
try
{
	//Przypisz 1 element tablicy, bez nowej lini, do textboxa
	textBox3.Text += tab[0].ToString();
	//Wypisz pozostałe posortowane elementy tablicy
	for (int k = 1; k < count; k++)
		textBox3.Text += "\r\n" + tab[k].ToString();
}
//Wypisanie komunikatu jeżeli wystąpił błąd
catch
{
	textBox3.Text = "Błąd sortowania!";
}

  1. Sortowanie przez wstawianie
    1. Opis działania
    2. Algorytm sortowania przez wstawiania potrzebował będzie dwóch tablic które przechowywać będą dane posortowane i nieposortowane. Działanie polega na pobraniu pierwszej wartości ze zbioru nieposortowanego i wstawienie go w miejscu docelowym w zbiorze (tablicy) posortowanym, przez co lista nieuporządkowana zmniejsza ilość swoich elementów o 1 a lista uporządkowana powiększa się o 1 element. W niniejszym przypadku ustalanie miejsca docelowego elementu, w zbiorze posortowanym, odbywać się będzie na zasadzie porównywania pobranego elementu z listy nieposortowanej z elementami w liście posortowanej. Algorytm wykonywać się będzie dopóki lista nie zostanie uporządkowana.

    3. Kod działania
    4. Algorytm tak jak wcześniejsze uruchamiany jest za pomocą buttona, dlatego do metody button4_Cick dodajemy poniższy kod.

//Czyszczenie textboxa z wcześniejszych sortowań
textBox4.Clear();
//Deklarowanie tablicy z liczbami do posortowania, oraz tablicy pomocniczej
int[] tab, tabPom;
//Zmienna pomocnicza, bufor
int buf;
//Egzemplarze tablicy 1. tablica psosrtowana, 2. tablica nieposortowana
tab = new int[count];
tabPom = new int[count];
//Przypisywanie wygenerowanych liczb do tablicy pomocniczej
for (int i = 0; i < count; i++)
	tabPom[i] = Convert.ToInt32(textBox1.Lines[i]);
//Sortowanie przez wstawianie  
//Pobranie pierwszego elementu tablicy, który jest również ostatnim elementem nieuporządkowanym
tab[0] = tabPom[0];                          
for (int i = 1; i < count; i++)                                      
{
	//Petla przyjmuje wartosc ostatniego elementu tablicy posortowanej
	for (int j = i; j > 0; j--)
	{
		//Jeżeli element tablicy nieposortowanej jest mniejszy
		if (tabPom[i] < tab[j - 1])                        
		{
			//Przypisz do zmiennej pomocniczej wartośc elementu tablicy psortowanej    
			buf = tab[j - 1];
			//Przypisz do tablicy posorotwanej element nieposortowany
			tab[j - 1] = tabPom[i];
			//Przypisz do tablicy posorotwanej wartość zmiennej pomocniczej
			tab[j] = buf;
		}
		//Jeżeli element tablicy nieposortowanej jest większy
		else
		{
			//Przypiz do tablicy posortowanej element nieposortowany
			tab[j] = tabPom[i];  
			//Przeriwj działanie pętli
			break;
		}
	}
}
//Zabezpieczenie przed pustym masked boxem
try
{
	//Przypisz 1 element tablicy, bez nowej lini, do textboxa
	textBox4.Text += tab[0].ToString();
	//Wypisz pozostałe posortowane elementy tablicy
	for (int k = 1; k < count; k++)
		textBox4.Text += "\r\n" + tab[k].ToString();
}
//Wypisanie komunikatu jeżeli wystąpił błąd
catch
{
	textBox4.Text = "Błąd sortowania!";
}

To już wszystkie algorytmy sortowania w tym wpisie. Ostatecznie program wykorzystujący powyższe algorytmy prezentuje się tak jak na rysunku poniżej. Działającą aplikacje wraz z kodem źródłowym pobrać możesz w punkcie 5.

Algorytmy sortujące

  1. Aplikacja i kod źródłowy
    Pobierz aplikacje – Sortowanie C#

    Pobierz kod źródłowy – Sortowanie C#

Jeżeli masz jakieś pytania do artykułu skontaktuj się ze mną. Zapraszam również do komentowania.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Autor

Dawid Świerczek

Dawid Świerczek

Zajmuje się projektowaniem oraz programowaniem aplikacji wykorzystując platformę .NET, głównie C#. Potrafię również wykonać strony internetowe i z powodzeniem je wypozycjonować. Nieustannie uczę się nowych technologi, aby moje aplikacje były jeszcze lepsze i bardziej wydajne. więcej...

Szukaj