Algoritmlar va berilganlar strukturasi

Boshqa tartiblash algoritmlari bilan aloqasi

Kiritish tartibi tanlash saralashiga juda o'xshaydi . Tanlashda bo'lgani kabi, k massivdan o'tgandan so'ng, birinchi k element tartiblangan tartibda bo'ladi. Biroq, ikkita algoritm o'rtasidagi asosiy farq shundan iboratki, kiritish tartiblash joriy kalitdan orqaga qarab skanerdan o'tkazadi, saralash esa oldinga qarab skanerlanadi. Bu tanlov saralashiga olib keladi, birinchi k element saralanmagan kirishning eng kichik k elementiga aylanadi, kiritish tartibida esa ular kirishning oddiy k elementi bo'ladi.
Kiritishni saralashning tanlangan saralashdan asosiy afzalligi shundaki, saralash ro‘yxatining saralanmagan qismidagi mutlaq eng kichik elementni topish uchun qolgan barcha elementlarni skanerlashi kerak, kiritish tartibi esa ( k + 1)-chi bo‘lganda faqat bitta taqqoslashni talab qiladi . element k -chi elementdan katta ; Bu tez-tez to'g'ri bo'lsa (masalan, kirish massivi allaqachon tartiblangan yoki qisman saralangan bo'lsa), qo'shish saralash tanlangan saralash bilan solishtirganda sezilarli darajada samaraliroq bo'ladi. O'rtacha ( k + 1)-chi element darajasi tasodifiy bo'lsa), kiritish saralash oldingi k elementning yarmini solishtirish va siljitishni talab qiladi , ya'ni kiritish saralash tanlangan saralashning yarmiga teng taqqoslashni amalga oshiradi. o'rtacha.
Kiritish saralash uchun eng yomon holatda (kirish massivi teskari tartiblangan bo'lsa), qo'shish saralash xuddi tanlagan saralash kabi ko'plab taqqoslashlarni amalga oshiradi. Biroq, qo'shishni saralashning tanlab olish tartibiga nisbatan kamchiliklari shundaki, u ko'proq yozishni talab qiladi, chunki har bir iteratsiyada ( k + 1)-chi elementni massivning tartiblangan qismiga kiritish hamma narsani siljitish uchun ko'plab elementlarni almashtirishni talab qiladi. quyidagi elementlardan, shu bilan birga tanlashning har bir iteratsiyasi uchun faqat bitta almashtirish talab qilinadi. Umuman olganda, kiritish tartiblash O( n ² ) massivga yoziladi , tanlashda esa faqat O( n ) marta yoziladi. Shu sababli, xotiraga yozish o'qishdan ko'ra ancha qimmat bo'lgan hollarda, masalan, bilan tanlashni tanlash afzalroq bo'lishi mumkin EEPROM yoki flesh xotira .
Tezkor saralash va birlashtirish kabi baʼzi boʻlish va zabt etish algoritmlari kattaroq massivlar uchun qoʻshishni saralashdan ustun boʻlsa-da, qoʻshish tartiblash yoki tanlash kabi rekursiv boʻlmagan saralash algoritmlari odatda juda kichik massivlar uchun tezroq (aniq oʻlcham muhit va amalga oshirishga qarab farq qiladi, lekin odatda 7 dan 50 tagacha element). Shu sababli, ushbu algoritmlarni amalga oshirishda foydali optimallashtirish massiv kichik o'lchamga bo'linganda oddiyroq algoritmdan foydalangan holda gibrid yondashuv hisoblanadi.


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 insertionsort
{
public partial class Form1 : Form
{
private int[] arr;
private int n;
private int i = 1;
private int j;
private bool isSorting = false;
private Timer timer;
public Form1()
{
InitializeComponent();
arr = new int[] { 5, 2, 4, 6, 1, 3 ,7};
n = arr.Length;
timer = new Timer();
timer.Interval = 1000;
timer.Tick += new EventHandler(timer1_Tick_1);
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
Graphics g = e.Graphics;
int x = 300;
int y = 250;
for (int k = 0; k < n; k++)
{
Brush brush = Brushes.Black;