aFizyka logo

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

Schemat algorytmu sortowania przez wstawianie liniowe Visual studio C#

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

Przykładowa aplikacja wykorzystująca algorytm sortowania liniowego przez wstawianie Visual studio C#

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);
        }
    }
}