Sortowanie przez wybór (selekcję)
Sortowanie przez wybór podobnie jak sortowanie bąbelkowe nie jest wydajnym algorytmem przy sortowaniu dużych zbiorów.
Działanie tego algorytmu opiera się na szukaniu najmniejszego elementu w zbiorze i zamienienie z elementem przechowywanym na pierwszej pozycji. W kolejnym obrocie pętli instrukcji szukania najmniejszego elementu zamiana miejsc pominie pierwszą pozycję. Podmiana elementów odbędzie się na pozycji drugiej. Instrukcje powtarza się do momentu otrzymania jednoelementowego zbioru.
Schemat algorytmu porządkowania przez wybór
Kod algorytmu sortowania przez wybór zapisany w języku C# wygląda jak poniżej
Wskazówka:
void sortWybor(Int32[] t, int rozmiar)
{
int id;
for(int i = 0; i < rozmiar; i++)
{
id = i;//zapamietaj biezacy indeks
for (int j = i + 1; j < rozmiar; j++)//szukaj min'a
if (t[j] < t[id])
id = j;
int bufor = t[i];
t[i] = t[id];
t[id] = bufor;
}
}
Przykładowa aplikacja wykorzystująca sortowanie przez wybór.
Pełny kod klasy Form utworzonej aplikacji wykorzystującej algorytm sortowani przez wybór
Form1.cs
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using static System.Windows.Forms.VisualStyles.VisualStyleElement;
namespace _11AlgSortPrzezWybor
{
public partial class Form1 : Form
{
Int32[] tab;
int rozmiar;
void losujTablice(Int32[] t, int zakres)
{
Random r = new Random();
int i = 0;
while (i < t.Length)
{
t[i] = r.Next(zakres) + 1;
i++;
}
}
void sortWybor(Int32[] t, int rozmiar)
{
int id;
for(int i = 0; i < rozmiar; i++)
{
id = i;//zapamietaj biezacy indeks
for (int j = i + 1; j < rozmiar; j++)//szukaj min'a
if (t[j] < t[id])
id = j;
int bufor = t[i];
t[i] = t[id];
t[id] = bufor;
}
}
public Form1()
{
InitializeComponent();
}
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{
if (e.KeyChar == 8) return;//wyskocz jak BackSpace
if(e.KeyChar<'0'||e.KeyChar>'9') e.Handled = true;//ignoru nienumeryczne
}
private void button1_Click(object sender, EventArgs e)
{
//losowanie nowej tablicy
if (textBox1.Text.Length < 1) return;
//wyczysc stara tablice
if (tab != null) Array.Clear(tab, 0, tab.Length);
//ustaw nowy rozmiar
rozmiar = int.Parse(textBox1.Text);
tab = new int[rozmiar];
//przy losowaniu ustaw zakres na 2 razy większy od rozmiaru
losujTablice(tab, 2 * rozmiar);
//pokaz wylosowany zbior
textBox2.Clear();
for (int i = 0; i < tab.Length; i++)
textBox2.AppendText(tab[i].ToString() + Environment.NewLine);
}
private void button2_Click(object sender, EventArgs e)
{
if (tab==null) return;
sortWybor(tab, rozmiar);
//wypisz posortowaną
//pokaz wylosowany zbior
textBox3.Clear();
for (int i = 0; i < tab.Length; i++)
textBox3.AppendText(tab[i].ToString() + Environment.NewLine);
}
}
}
