Sortowanie przez wstawianie liniowe
Idea sortowania przez wstawianie przypomina układanie oddanej książki na półkę w bibliotece. Taka książka musi trafić na miejsce zgodnie z przyjętym sortowaniem.
Algorytm sortowania przez wstawianie liniowe, polega na rozpoczęciu sortowania od drugiego elementu zbioru. Element ten porównywany jest z elementem go poprzedzającym.
Jeżeli jest to element o wartości większej, to zostaje przesunięty o jedną pozycję w prawo. Czynność przesuwania trwa do momentu napotkania liczby mniejszej lub gdy skończą się pozycje do przeglądnięcia.
Kolejny krok, to wstawienie bieżącej liczby w wyznaczona pozycję.
Powyższe czynności ponownie są wykonywane dla kolejnych elementów zbioru nieposortowanego.
Schemat algorytmu sortowania przez wstawianie liniowe
Kod funkcji realizującej sortowani przez wstawianie liniowe zapisany w języku C# znajduje się poniżej
Wskazówka:
void sortPrzezWstawianieLiniowe(Int32[] t, int rozmiar)
{
int bufor, j;
for(int i = 1; i < rozmiar; i++)
{
bufor = t[i];
j = i - 1;
while(j>=0 && t[j] > bufor)
{
t[j + 1] = t[j];//przesun elemety;
j--;//zmniejsz licznik pozycji do przeglądnięcia
}
t[j + 1] = bufor;//wstaw element
}
}
Przykładowa aplikacja wykorzystująca algorytm sortowania liniowego przez wstawianie
Pełny kod klasy Form dla formatki utworzonej aplikacji. Kod zawiera funkcję losującą elementy zbioru z powtórzeniami.
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;
namespace Alg12SortWstawianie
{
public partial class Form1 : Form
{
Int32[] tab;
int rozmiar;
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 sortPrzezWstawianieLiniowe(Int32[] t, int rozmiar)
{
int bufor, j;
for(int i = 1; i < rozmiar; i++)
{
bufor = t[i];
j = i - 1;
while(j>=0 && t[j] > bufor)
{
t[j + 1] = t[j];//przesun elemety;
j--;//zmniejsz licznik pozycji do przeglądnięcia
}
t[j + 1] = bufor;//wstaw element
}
}
public Form1()
{
InitializeComponent();
}
private void textBox2_KeyPress(object sender, KeyPressEventArgs e)
{
if (e.KeyChar == 8) return;//wyskocz jak 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 (textBox2.Text.Length < 1) return;
//wyczysc stara tablice
if (tab != null) Array.Clear(tab, 0, tab.Length);
//ustaw nowy rozmiar
rozmiar = int.Parse(textBox2.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 button3_Click(object sender, EventArgs e)
{
if (tab == null) return;
sortPrzezWstawianieLiniowe(tab, rozmiar);
//wypisz posortowaną
//pokaz wylosowany zbior
textBox3.Clear();
for (int i = 0; i < tab.Length; i++)
textBox3.AppendText(tab[i].ToString() + Environment.NewLine);
}
}
}
