Sortari

Shell Sort

Posted by Feroviarul on

Aspecte teoretice:

Sortarea cu micșorarea incrementului (shellsort) este o extensie simplă al Insertion sortului care câștigă viteză permițând schimbarea elementelor aflate departe. Ideea de bază o constituie rearanjarea elementelor din tabela A în așa fel încât, luând fiecare al h-lea element (începând de oriunde), să obținem o tabelă sortată. Astfel spunem că tabela este h-sortată. O tabelă , h-sortată este formată din h subtabele sortate independent, intercalate. Folosind astfel o procedură pentru fiecare secvență a valorii lui h care se termină în 1, va produce o tabelă sortată.

Analiza complexității:

Eficiența algoritmului Shell sort este greu de analizat, greu de comparat cu alte metode, nici timpul de rulare nu este cunoscut sigur. Pentru acest program în legătură cu timpul de rulare există două presupuneri : N(log 2 N)^2 si N^3/2. Timpul de execuție nu este sensibil în mod particular la ordinea inițială al elementelor. Insertion sort este mai lent
pentru că schimbă doar elementele adiacente. Shellsort nu efectuează mai mult de N^½ comparații (pentru creșterile: 1, 4, 13, 40, 121,….). Shellsort este metoda aleasă pentru multe aplicații de sortare pentru că are un timp de execuție accesibil chiar si pentru o tabelă moderat de mare (mai puțin de 5000 elemente) și este o metodă stabilă.

Exemplu pas cu pas:

Șir inițial: 1 11 8 10 12 4 7 3 1 13 1 6 9 5 2

Pas 1: 1 11 8 10 12 4 7 3 1 13 1 6 9 5 2
1 2 8 10 12 4 7 3 1 13 1 6 9 5 11

Pas 2: 1 2 8 10 12 4 7 3 2 13 1 6 9 5 11
1 2 8 10 2 4 7 3 9 13 1 6 12 5 11
1 2 8 10 2 4 7 3 9 5 1 10 12 13 11
1 2 1 10 2 4 7 3 9 5 8 10 12 13 11
1 2 1 3 2 4 7 6 9 5 8 10 12 13 11
1 2 1 3 2 4 7 6 9 5 8 10 12 13 11

…………………………………………….

Pas M: 1 1 2 2 3 4 5 6 7 8 9 10 11 12 13

Implementare:

Logo_C_Sharp
Cod Sursa C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ShellSortCS
{
    class Program
    {
        static void ShellSort(int[] v, int len)
        {
            int inc, i, j, aux;
            for(inc=len/2; inc>0; inc/=2)
                for (i = inc; i < len; i++)
                    for (j = i - inc; j >= 0 && v[j] > v[j + inc]; j -= inc)
                    {
                        aux = v[j];
                        v[j] = v[j + inc];
                        v[j + inc] = aux;
                    }  
        }
 
        static void Main(string[] args)
        {
            int [] v = new int[20];
            int i, len;
            Console.Write("Dati numarul de elemente din vector: ");
            len = Convert.ToInt32(Console.ReadLine());
            for (i = 0; i < len; i++)
            {
                Console.Write("v[" + i + "]=");
                v[i]=Convert.ToInt32(Console.ReadLine());
            }
            ShellSort(v, len);
            for (i = 0; i < len; i++)
                Console.Write(v[i] + " ");
            Console.ReadLine();
        }
    }
}
Visual_C++_Icon
Cod Sursa C++
// ShellSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int v[20];
 
void ShellSort(int v[], int len)
{
	int inc,i,j,aux;
	for(inc=len/2; inc>0; inc/=2)
		for(i=inc; i<len; i++)
			for (j=i-inc; j>=0 && v[j]>v[j+inc]; j-=inc)
			{
				aux=v[j];
				v[j]=v[j+inc];
				v[j+inc]=aux;
			}
}
 
int main(void)
{
	int i;
	int len;
	cout<<"Dati numarul de elemente din vector: ";
	cin>>len;
	for (i=0; i<len; i++)
	{
		cout<<"v["<<i<<"]=";
		cin>>v[i];
	}
	ShellSort(v, len);
	for (i=0; i<len; i++)
		cout<<v[i]<<" ";
	system("pause");
}
Logo_VB
Cod Sursa VB
Module Module1
 
    Private Sub ShellSort(v As Integer(), len As Integer)
        Dim inc As Integer, i As Integer, j As Integer, aux As Integer
        inc = len / 2
        While inc > 0
            For i = inc To len - 1
                j = i - inc
                While j >= 0 AndAlso v(j) > v(j + inc)
                    aux = v(j)
                    v(j) = v(j + inc)
                    v(j + inc) = aux
                    j -= inc
                End While
            Next
            inc /= 2
        End While
    End Sub
 
    Sub Main(args As String())
        Dim v As Integer() = New Integer(19) {}
        Dim i As Integer, len As Integer
        Console.Write("Dati numarul de elemente din vector: ")
        len = Convert.ToInt32(Console.ReadLine())
        For i = 0 To len - 1
            Console.Write("v[" & i & "]=")
            v(i) = Convert.ToInt32(Console.ReadLine())
        Next
        ShellSort(v, len)
        For i = 0 To len - 1
            Console.Write(v(i) & " ")
        Next
        Console.ReadLine()
    End Sub
 
End Module
phplogo
Cod Sursa PHP
<?php

 
function shell_Sort($my_array)
{
	$x = round(count($my_array)/2);
	while($x > 0)
	{
		for($i = $x; $i < count($my_array);$i++){
			$temp = $my_array[$i];
			$j = $i;
			while($j >= $x && $my_array[$j-$x] > $temp)
			{
				$my_array[$j] = $my_array[$j - $x];
				$j -= $x;
			}
			$my_array[$j] = $temp;
		}
		$x = round($x/2.2);
	}
	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";
echo implode(', ',shell_Sort($test_array)). PHP_EOL;
sleep(10);
?>
Java-Logo
Cod Sursa JAVA


//insertie cu diminuarea incrementuluiclass ShellSortJAVA
{
  public static void ShellSort(int v[], int len)
        {
            int inc, i, j, aux;
            for(inc=len/2; inc>0; inc/=2)
                for (i = inc; i < len; i++)
                    for (j = i – inc; j >= 0 && v[j] > v[j + inc]; j -= inc)
                    {
                        aux = v[j];
                        v[j] = v[j + inc];
                        v[j + inc] = aux;
                    }
        }    public static void main(String[] args)
        {
          int a[]={7,4,5,3,1,8,9,2,6,0};
          int i;
          ShellSort(a,10);
          for (i=0;i<10;i++)
                System.out.println(a[i]+” “);
        }
}

Rezultat:

quicksortrezultat

 

 

Leave a comment