Recursivitate, Sortari

Merge Sort

Posted by Feroviarul on

Aspecte teoretice:

Algoritmul de sortare prin interclasare se bazează pe următoarea idee: pentru a sorta o tabelă cu N elemente îl împărțim în două tabele pe care le sortez separat și le interclasăm. Este o metodă de sortare care folosește strategia de bază “divide et impera”, conform căreia problema se descompune în alte două subprobleme de același tip și după rezolvarea lor rezultatele se combină. Algoritmul sortează elementele în ordine crescătoare.
Tabelul se împarte în n/2, după aceea tabelele se impart în jumătate, tot așa până când tabelele formate au mai puțin sau cel mult de k elemente(în cazul nostru k=2-este cel mai ușor să compari 2 elemente).
Algoritmul presupune :
1. Află mijlocul tabelului
2. Sortează prima jumătate a tabelului
3. Sortează a doua jumătate a tabelului
4. Îmbină cele 2 jumătăți

Analiza complexității:

Majoritatea muncii este cuprinsă în comparare și copiere. În procedura Merge fiecare element din subtabele este comparat: asta este o operație de O(N), copierea elementelor din tabela temporală în cea originală tot O(N). Deci procedura Merge este de O(N). Procedura Mergesort este recursivă și Merge este apelat recursiv pentru ambele jumătăți. Astfel putem împărți tabela de log 2 N ori și de fiecare dată executăm de O(N) procedura Merge. Algoritmul total este de O(N log2 N) în toate cele trei cazuri. Este o metodă stabilă. Nu este sensibil la ordinea inițială al elementelor. Dezavantajul Mergesortului este că necesită o tabelă auxiliară de mărimea originalului. Problema apare când tabela este mare și spațiu este un factor critic.

Exemplu Pas cu Pas:

merge_sort_recursionImplementare:

Logo_C_Sharp
Cod Sursa C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace MergeSortCS
{
    class Program
    {
        static void Interclaseaza(int start, int mijloc, int sfarsit, int [] A)
        {
            int [] B = new int[100];
            int i, j, k;
            k = start; i = start; j = mijloc + 1;
            while (i <= mijloc && j <= sfarsit)
            {
                if (A[i] < A[j])
                {
                    B[k] = A[i];
                    i = i + 1;
                    k = k + 1;
                }
                else
                {
                    B[k] = A[j];
                    j = j + 1;
                    k = k + 1;
                }
            }
            if (i<=mijloc)
                for (j = i; j <= mijloc; j++)
                {
                    B[k] = A[j];
                    k = k + 1;
                }
            else
                for (i = j; i <= sfarsit; i++)
                {
                    B[k] = A[i];
                    k = k + 1;
                }
            for (i = start; i <= sfarsit; i++)
                A[i] = B[i];
        }
 
        static void MergeSort(int inceput, int final, int [] A)
        {
            int centru;
            if (inceput < final)
            {
                centru = (inceput + final) / 2;
                MergeSort(inceput, centru, A);
                MergeSort(centru + 1, final, A);
                Interclaseaza(inceput, centru, final, A);
            }
        }
        static void Main(string[] args)
        {
            int n, i;
            int[] A = new int[100];
            Console.Write("Numarul elementelor n este: ");
            n = Convert.ToInt32(Console.ReadLine());
            for (i = 1; i <= n; i++)
            {
                Console.Write("a[" + i + "]=");
                A[i]=Convert.ToInt32(Console.ReadLine());
            }
            MergeSort(1, n, A);
            for (i = 1; i <= n; i++)
                Console.Write(A[i] + " ");
            Console.ReadLine();
        }
    }
}
Logo_VB
Cod Sursa VB
Module Module1
    Dim A(100) As Integer
    Dim i, n As Integer
 
    Sub Interclaseaza(ByVal start As Integer, ByVal mijloc As Integer, ByVal sfarsit As Integer)
        Dim B(100) As Integer
        Dim i, j, k As Integer
        k = start
        i = start
        j = mijloc + 1
        While (i <= mijloc And j <= sfarsit)
            If A(i) < A(j) Then
                B(k) = A(i)
                i = i + 1
                k = k + 1
            Else
                B(k) = A(j)
                j = j + 1
                k = k + 1
            End If
        End While
        If i <= mijloc Then
            For j = i To mijloc
                B(k) = A(j)
                k = k + 1
            Next j
            For i = start To sfarsit
                A(i) = B(i)
            Next i
        End If
    End Sub
 
    Sub MergeSort(ByVal inceput As Integer, ByVal final As Integer)
        Dim centru As Double
        If inceput < final Then
            centru = (inceput + final) \ 2
            MergeSort(inceput, centru)
            MergeSort(centru + 1, final)
            Interclaseaza(inceput, centru, final)
        End If
    End Sub
 
    Sub Main()
        Console.Write("Numarul elementelor n: ")
        n = Convert.ToInt32(Console.ReadLine())
        For i = 1 To n
            Console.Write("a[" & i & "]=")
            A(i) = Convert.ToInt32(Console.ReadLine())
        Next i
        MergeSort(1, n)
        For i = 1 To n
            Console.Write(A(i) & " ")
        Next i
        Console.ReadLine()
    End Sub
 
End Module
Visual_C++_Icon
Cod Sursa C++
// MergeSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
 
using namespace std;
 
int A[10],i,n;
 
void Interclaseaza(int start, int mijloc, int sfarsit)
{
	int B[10],i,j,k;
	k=start; i=start; j=mijloc+1;
	while (i<=mijloc && j<=sfarsit)
	{
		if (A[i]<A[j])
		{
			B[k]=A[i];
			i=i+1;
			k=k+1;
		}
		else
		{
			B[k]=A[j];
			j=j+1;
			k=k+1;
		}
	}
	if (i<=mijloc)
		for (j=i; j<=mijloc; j++)
		{
			B[k]=A[j];
			k=k+1;
		}
	else
		for (i=j; i<=sfarsit; i++)
		{
			B[k]=A[i];
			k=k+1;
		}
		for (i=start; i<=sfarsit; i++)
			A[i]=B[i];
}
 
void MergeSort(int inceput, int final)
{
	int centru;
	if (inceput<final)
	{
		centru=(inceput+final) / 2;
		MergeSort(inceput,centru);
		MergeSort(centru+1,final);
		Interclaseaza(inceput,centru,final);
	}
}
 
void main()
{
	cout<<"Numarul elementelor n: ";
	cin>>n;
	for (i=1; i<=n; i++)
	{
		cout<<"a["<<i<<"]=";
		cin>>A[i];
	}
	MergeSort(1,n);
	for (i=1; i<=n; i++)
		cout<<A[i]<<" ";
	system("Pause");
}
phplogo
Cod Sursa PHP
<?php

function merge_sort($my_array){
	if(count($my_array) == 1 ) return $my_array;
	$mid = count($my_array) / 2;
	$left = array_slice($my_array, 0, $mid);
	$right = array_slice($my_array, $mid);
	$left = merge_sort($left);
	$right = merge_sort($right);
	return merge($left, $right);
}
 
function merge($left, $right){
	$res = array();
	while (count($left) > 0 && count($right) > 0){
		if($left[0] > $right[0]){
			$res[] = $right[0];
			$right = array_slice($right , 1);
		}else{
			$res[] = $left[0];
			$left = array_slice($left, 1);
		}
	}
	while (count($left) > 0){
		$res[] = $left[0];
		$left = array_slice($left, 1);
	}
	while (count($right) > 0){
		$res[] = $right[0];
		$right = array_slice($right, 1);
	}
	return $res;
}
$test_array = array(100, 54, 7, 2, 5, 4, 1);
echo "Vector Orginal: \n";
echo implode(', ',$test_array );
echo "\nVector Sortat: \n";
echo implode(', ',merge_sort($test_array))."\n";
sleep(10);
?>
Java-Logo
Cod Sursa JAVA


//Complexitate: Nefavorabil: O(n*log n); Mediu: O(n*log n); Favorabil:  O(n*log n)class MergeSortJAVA
{
  public static void Interclaseaza(int start, int mijloc, int sfarsit, int A[])
        {
            int [] B = new int[100];
            int i, j, k;
            k = start; i = start; j = mijloc + 1;
            while (i <= mijloc && j <= sfarsit)
            {
                if (A[i] < A[j])
                {
                    B[k] = A[i];
                    i = i + 1;
                    k = k + 1;
                }
                else
                {
                    B[k] = A[j];
                    j = j + 1;
                    k = k + 1;
                }
            }
            if (i<=mijloc)
                for (j = i; j <= mijloc; j++)
                {
                    B[k] = A[j];
                    k = k + 1;
                }
            else
                for (i = j; i <= sfarsit; i++)
                {
                    B[k] = A[i];
                    k = k + 1;
                }
            for (i = start; i <= sfarsit; i++)
                A[i] = B[i];
        }

        public static void MergeSort(int inceput, int finish, int A[])
        {
            int centru;
            if (inceput < finish)
            {
                centru = (inceput + finish) / 2;
                MergeSort(inceput, centru, A);
                MergeSort(centru + 1, finish, A);
                Interclaseaza(inceput, centru, finish, A);
            }
        }

        public static void main(String args[])
        {
          int a[]={7,4,5,3,1,8,9,2,6,0};
          int i;
          MergeSort(0,9,a);
          for (i=0;i<10;i++)
                System.out.println(a[i]+” “);
        }
}

Rezultat:

quicksortrezultat

Leave a comment