Algorytm szybkiego sortowania (Quick sort)
Quick sort, to jeden z najszybszych algorytmów sortowania. Pracuje bezpośrednio na tablicy, liście wprowadzonych danych. Jego działanie nie wymaga dodatkowej tablicy na buforowanie sortowanych danych. Wykorzystuje zasadę ?dziel i zwyciężaj?. Złożoność algorytmu jest typu O(n log n).
Opis działania algorytmu szybkiego sortowania
W pierwszym kroku wybierany jest element ze środka zbioru. Wybór tego elementu określa podział zbioru na dwie części- lewa i prawą. Lewa część jest od indeksu zerowego do środkowego, prawy od środkowego do prawego.
Kolejnym krokiem jest przenoszenie mniejszych elementów do lewej części zbioru, a większych do prawej. Wynikiem przeniesienia nie muszą być równoliczne zbiory. Lewa lub prawa część po przenosinach może być mniejsza/ większa jedna od drugiej.
Lewa część zbioru w każdym kroku zawiera elementy mniejsze niż elementy zapisane w prawej części. Kolejnym krokiem jest osobne sortowanie lewej i prawej części.
Schemat algorytmu szybkiego sortowania
Algorytm szybkiego sortowania zapisany rekurencyjnie
Kod funkcji algorytmu sortowania szybkiego zapisany w języku C#
Wskazówka:
void qSort_A_Z(Int32[] t,int L,int P)
{
Int32 bufor, sr, i, j;
i = L;
j = P;
sr = t[(L + P) / 2];//wybierz element ze srodka
do{
while (t[i] < sr) i++;
while (sr < t[j]) j--;
if (i <= j)
{
bufor = t[i];
t[i] = t[j];
t[j] = bufor;
i++;
j--;
}//koniec if
}while (i < j);//koniec do- while i<j
if (L < j) qSort_A_Z(t, L, j);
if (i < P) qSort_A_Z(t, i, P);
}
Przykładowa aplikacja wykorzystująca algorytm szybkiego sortowania.
Pełny kod klasy Form utworzonej formatki aplikacji sortującej algorytmem szybkiego sortowania.
Wskazówka:
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 _14AlgQsort
{
public partial class Form1 : Form
{
Int32[] tab; //tablica glowna
int rozmiar;//rozmiar zbioru
void losujTablice(Int32[] t, int zakres)
{
Random r = new Random();
int i = 0;
//mogą występować powtórzenia wylosowanych elementów
while (i < t.Length)
{
t[i] = r.Next(zakres) + 1;
i++;
}
}
void qSort_A_Z(Int32[] t,int L,int P)
{
Int32 bufor, sr, i, j;
i = L;
j = P;
sr = t[(L + P) / 2];//wybierz element ze srodka
do{
while (t[i] < sr) i++;
while (sr < t[j]) j--;
if (i <= j)
{
bufor = t[i];
t[i] = t[j];
t[j] = bufor;
i++;
j--;
}//koniec if
}while (i < j);//koniec do- while i<j
if (L < j) qSort_A_Z(t, L, j);
if (i < P) qSort_A_Z(t, i, P);
}
void qSort_Z_A(Int32[] t, int L, int P)
{
Int32 bufor, sr, i, j;
i = L;
j = P;
sr = t[(L + P) / 2];//wybierz element ze s?rodka
do{
while (t[i] > sr) i++;
while (sr > t[j]) j--;
if (i <= j)
{
bufor = t[i];
t[i] = t[j];
t[j] = bufor;
i++;
j--;
}//koniec if
}while (i < j);//koniec do- while i<j
if (L < j) qSort_Z_A(t, L, j);
if (i < P) qSort_Z_A(t, i, P);
}
public Form1()
{
InitializeComponent();
}
private void textBox3_KeyPress(object sender, KeyPressEventArgs e)
{
if (e.KeyChar == 8) return;//wyskocz na Backspace
if (e.KeyChar < '0' || e.KeyChar > '9') e.Handled = true;//ignoruj nienumeryczne
}
private void button1_Click(object sender, EventArgs e)
{
//losowanie nowej tablicy
if (textBox3.Text.Length < 1) return;
//wyczysc stara tablice
if (tab != null) Array.Clear(tab, 0, tab.Length);
//ustaw nowy rozmiar
rozmiar = int.Parse(textBox3.Text);
tab = new int[rozmiar];
//przy losowaniu ustaw zakres na 2 razy większy od rozmiaru
losujTablice(tab, 2 * rozmiar);
//pokaz wylosowany zbior
textBox1.Clear();
for (int i = 0; i < tab.Length; i++)
textBox1.AppendText(tab[i].ToString() + Environment.NewLine);
}
private void button2_Click(object sender, EventArgs e)
{
//ajk pusta tablica to wyskocz
if (tab == null) return;
qSort_A_Z(tab, 0, rozmiar - 1);
//wypisz posortowaną
//pokaz wylosowany zbior
textBox2.Clear();
for (int i = 0; i < tab.Length; i++)
textBox2.AppendText(tab[i].ToString() + Environment.NewLine);
}
private void button3_Click(object sender, EventArgs e)
{
//ajk pusta tablica to wyskocz
if (tab == null) return;
qSort_Z_A(tab, 0, rozmiar - 1);
//wypisz posortowaną
//pokaz wylosowany zbior
textBox2.Clear();
for (int i = 0; i < tab.Length; i++)
textBox2.AppendText(tab[i].ToString() + Environment.NewLine);
}
}
}
