Sortowanie przez wybór (selection sort)

informatyka logo
Strona główna Strona szkoły Plan lekcji Bieżące zastępstwa Biblioteka 

III LO Tarnów
eDziennik III LO Tarnów
MS Visual Studio C++ 2008

Sortowanie przez wybór (selection sort)


Algorytm ten jest modyfikacją algorytmu sortowania bąbelkowego. Jego działanie polega na tej samej zasadzie co sosrtowanie bąbelkowe, z tą różnicą, że zyskuje się na mniejszej ilości instrukcji przestawień sortowanych elementów. W tej metodzie zapamiętuje się indeks najmniejszego bądź najwięszego elementu w skracanym ciągu zbioru wejściowego. Zamiana miejscami elementów występuje raz, w głównej pętli algorytmu.
 
sortowanie przez wybór idea działania algorytmu (selection sort)
 
Treść algorytmu podaję za autorem podręcznika "Informatyka"" WSiP M. Sysło
 
Dane: Ciąg n-elementowy liczb całkowitych x1, x2, ...xn
 
Wynik: Uporządkowny podany ciag liczb od największego do najmniejszego elementu
 
Krok 1: Dla i=1,2, ..., n-1 wykonaj kolejno kroki 2 i 3, a następnie zakończ algorytm
 
Krok 2: Znajdź k takie, że xk jest najmniejszym elementem w ciągu x1, x2, ...xn-i
 
Krok 3: Zmień miejscami elementy xk oraza xn-i
 
Schemat blokowy algorytmu sortowania przez wybór
 
sortowanie przez wybór schemat algorytmu (selection sort) visual studio c++


Cel: Stosując algorytm sortowania przez wybór, uporządkuj zbiór liczb całkowitych, zapisany w jdnowymiarowej tablicy dynamicznej w porządku od największego do najmniejszego elementu.
 
kliknij na rysunku, aby pobrać plik *.exe

 
Krok 1: Dołącz bibliotekę generatora liczb losowych oraz zadeklaruj jednowymiarową tablicę dynamiczną

using namespace System::Collections::Generic;
.
.
.
#pragma region Windows Form Designer generated code
		/// <summary>
		/// Required method for Designer support - do not modify
		/// the contents of this method with the code editor.
		/// </summary>
        array <System::Int32> ^t;

Krok 2: Napisz funkcję losującą elementy zbioru. Elementy mogą się powtarzać.

		void losu_z_powtorzeniami(array<System::Int32>^ tab,int zakres){
			Random^ los=gcnew Random();
			int i=0;
			while(i<=tab->GetLength(0)-1)
			{
                          tab[i]=los->Next(zakres)+1;
			  i++;
			}
	       }//koniec losuj zbiór z powtórzeniami 

Krok 3: Napisz funkcję realizująca algorytm sortowania przez wybór

void sortuj_przez_wybor(array<System::Int32>^ tab){
	int n=tab->GetLength(0)-1;
	int k;//połozenie minimum
	System::Int32 min;
	System::Int32 bufor;//bufor na wartość z tablicy sorotwanego zbioru
	while(n>0){
		    min=tab[0];//przyjmij tymczasowe minimum
  		    k=0;
		    //szukamy minimum i zapamietaj jego miejsce
		    for(int i=0;i<=n;i++){if(tab[i]<min){min=tab[i];k=i;}}
		    //zamień minimum z ostatnim elementem
		    bufor=tab[n];
		    tab[n]=min;
		    tab[k]=bufor;
	            n=n-1;
	     }//koniec petli dopóki n>0
        }//koniec sortuj_przez_wybor

Krok 4: W zdarzeniu kliknięcia klawisza wywołaj funkcję losowania i sortowania zbioru

private: System::Void button1_Click(System::Object^  sender, System::EventArgs^  e) {
	 int n=Convert::ToInt32(textBox1->Text);//odczytaj podany rozmiar zbioru
	 t= gcnew array<System::Int32>(n);//przydziel pamięć dla tablicy dynamicznej
	 losu_z_powtorzeniami(t,n+100);//losuj zbiór
	 sortuj_przez_wybor(t);//sortuj
	 }

Zadanie 1: Pokaż zawartość zbioru przed i po sortowaniu.
 
Zadanie 2: Zmodyfikuj funkcję losującą elementy tak, aby nie występowały powtórzenia.
 




strona główna
Delphi
symulacje fizyczne Delphi
Saper w Delphi7
VS C++ 2008 Express
Wstęp do środowiska VS C++ 2008
Kólko i krzyżyk gra w visual studio c++
Delphi, VS C++
Wstęp do algorytmów

Tworzenie witryn www aplikacja google
Walki robotów
diversity motorola solutions polska walki robotów

III LO Tarnów
2012-2013©Adam Lasko Zbylitowska Góra