Sortari

Insertion Sort

Posted by Feroviarul on

Aspecte teoretice:

Inserția directă aparține familiei de tehnici de sortare care se bazează pe metoda “jucătorului de bridge”. Este un algoritm aproape la fel de simplu ca Selection sort, dar poate mai flexibil. Considerăm elementele A[1]…A[i-1] fiind sortate, inserăm elementul A[i] în locul ce îi revine.
Fiind dat o tabelă A cu N elemente nesortate, parcurgem tabela și le inserăm fiecare element în locul propriu între celelalte elemente considerate sortate. Pentru fiecare i = 2..N , elementele A[1]…A[i] sunt sortate prin inserarea lui A[i] între lista elementelor sortate: A[1]…A[i-1]. Elementele aflate în stânga indexului sunt în ordine sortată dar nu sunt în poziția lor finală. Tabela este sortată complet când indexul ajunge la capătul drept al tabelei.

Analiza complexității:

Insertion sort este un algoritm de sortare simplu, liniar: O(N) pentru tabele care conțin N elemente aproape sortate. Timpul de execuție al algoritmului depinde de numărul inversărilor, deci de ordinea inițială al elementelor. În caz general sunt necesare N^2 /4 comparații si interschimbări, N^2 /8 deci ordinea magnitudinii este O(N^2). În caz cel mai nefavorabil, când tabela este initial sortată în ordine inversă.

Exemplu Pas cu Pas:

5 7 0 3 4 2 6 1
5 7 0 3 4 2 6 1
0 5 7 3 4 2 6 1
0 3 5 7 4 2 6 1
0 3 4 5 7 2 6 1
0 2 3 4 5 7 6 1
0 2 3 4 5 6 7 1
0 1 2 3 4 5 6 7

Implementare:

Logo_C_Sharp
Cod Sursa C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace InsertionSortCS
{
    class Program
    {
        static void InsertionSort(int length, double[] array)
        {
            int i, j;
            double key;
            for (i = 2; i <= length; i++)
            {
                key = array[i];
                j = i - 1;
                while (j >= 1 && array[j] > key)
                {
                    array[j + 1] = array[j];
                    j = j - 1;
                }
                array[j + 1] = key;
            }
        }
 
        static void Main(string[] args)
        {
            int i, length;
            double[] array = new double[10];
            Console.Write("Introduceti numarul elementelor n: ");
            length = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Introduceti elementele vectorului de sortat");
            for (i = 1; i <= length; i++)
            {
                Console.Write("array[" + i + "]=");
                array[i]=Convert.ToInt32(Console.ReadLine());
            }
            Console.WriteLine("Elementele vectorului nesortat sunt: ");
            for (i=1; i<=length; i++)
                Console.Write(array[i] + " ");
            Console.WriteLine("Vectorul sortat prin metoda insertiei directe");
            InsertionSort(length,array);
            for (i=1;i<=length;i++)
                Console.Write(array[i] + " ");
            Console.ReadLine();
        }
    }
}
Logo_VB
Cod Sursa VB
Module Module1
    Sub InsertionSort(ByVal length As Integer, ByVal array() As String)
        Dim i, j As Integer
        Dim key As Double
        For i = 2 To length
            key = array(i)
            j = i - 1
            While (j >= 1 And array(j) > key)
                array(j + 1) = array(j)
                j = j - 1
            End While
            array(j + 1) = key
        Next i
    End Sub
 
    Sub Main()
        Dim i, length As Integer
        Dim array(100) As String
        Console.Write("Introduceti nr. elementelor n=")
        length = Convert.ToInt32(Console.ReadLine())
        Console.WriteLine("Introduceti elementele vectorului de sortat")
        For i = 1 To length
            Console.Write("array[" & i & "]=")
            array(i) = Convert.ToString(Console.ReadLine())
        Next i
        Console.WriteLine("Elementele vectorului nesortat sunt ")
        For i = 1 To length
            Console.Write(array(i) & " ")
            Console.WriteLine()
        Next i
        Console.WriteLine("Vectorul sortat prin metoda inserarii directe ")
        InsertionSort(length, array)
        For i = 1 To length
            Console.Write(array(i) & " ")
        Next i
        Console.ReadLine()
    End Sub
 
End Module
Visual_C++_Icon
Cod Sursa C++

// InsertionSortCPP.cpp : Defines the entry point for the console application. // #include “stdafx.h” #include <iostream> #include <conio.h> using namespace std; void sort_inserare_directa(int length,float array[100])  /* SORTARE PRIN INSERARE DIRECTA */  {  int i,j;  float key;  for(i=2;i<=length;i++)  {  key=array[i];  j=i-1; while(j>=1 && array[j]>key)  { array[j+1]=array[j];  j=j-1;  }  array[j+1]=key;  }  } int main()  {  int i,length;  float array[10]; cout<<“Introduceti nr.elementelor n=”;  cin>>length; cout<<“Introduceti elementele vectorului de sortat”<<endl; for(i=1;i<=length;i++) { cout<<“array[“<<i<<“]=”;  cin>>array[i]; } cout<<“Elementele vectorului nesortat sunt: “<<endl; for(i=1;i<=length;i++) cout<<array[i]<<” “; cout<<“VECTORUL SORTAT PRIN METODA INSERARII DIRECTE”<<endl;  sort_inserare_directa(length,array);  for (i=1;i<=length;i++) cout<<array[i]<<” “; system(“pause”);  }

phplogo
Cod Sursa PHP
<?php

 
function insertion_Sort($my_array)
{
	for($i=0;$i<count($my_array);$i++){
		$val = $my_array[$i];
		$j = $i-1;
		while($j>=0 && $my_array[$j] > $val){
			$my_array[$j+1] = $my_array[$j];
			$j--;
		}
		$my_array[$j+1] = $val;
	}
	return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Vectorul original :\n";
echo implode(', ',$test_array );
echo "\nVectorul sortat :\n";
print_r(insertion_Sort($test_array));
sleep(10);
?>
Java-Logo
Cod Sursa JAVA


//Complexitate: Nefavorabil: O(n^2); Mediu: O(n^2); Favorabil: O(n)class InsertionSortJAVA
{
 public static void InsertionSort(int length, int array[])
        {
            int i, j;
            int key;
            for (i = 2; i <= length; i++)
            {
                key = array[i];
                j = i – 1;
                while (j >= 1 && array[j] > key)
                {
                    array[j + 1] = array[j];
                    j = j – 1;
                }
                array[j + 1] = key;
            }
        }        public static void main(String[] args)
        {
          int a[]={0,7,4,5,3,1,8,9,2,6};
          int i;
          InsertionSort(9,a);
          for (i=0;i<10;i++)
                System.out.println(a[i]+” “);
        }
}

Rezultat:

quicksortrezultat

Leave a comment