Aspecte teoretice:
Sortarea prin amestecare (Shaker Sort/ Cocktail Sort) reprezintă o variantă a metodei bubble sort, având următoarele îmbunătățiri:
- La fiecare parcurgere a subtabloului a[i],…,a[N] se memorează indicele k al ultimei interschimbări efectuate, astfel încât la următoarea trecere, un capăt al subtabloului va fi marcat de k (între 1 și k tabloul este ordonat);
- Se schimbă alternativ sensul de parcurgere al subtablourilor pentru două treceri consecutive.
Analiza complexității:
33 98 74 13 55 20 77 45 64 83
33 98 74 13 55 20 77 45 64 83
33 98 74 13 55 20 77 45 64 83
33 74 98 13 55 20 77 45 64 83
33 74 98 13 55 20 77 45 64 83
33 74 13 98 55 20 77 45 64 83
33 74 13 55 20 77 45 64 83 98
33 74 13 55 20 77 45 64 83 98
33 74 13 55 20 77 45 64 83 98
33 74 13 55 20 77 45 64 83 98
33 74 13 55 20 45 77 64 83 98
33 74 13 55 20 45 77 64 83 98
33 74 13 55 20 45 77 64 83 98
33 74 13 20 55 45 77 64 83 98
33 74 13 20 55 45 77 64 83 98
33 74 13 20 55 45 77 64 83 98
33 13 74 20 55 45 77 64 83 98
33 13 74 20 55 45 77 64 83 98
13 33 74 20 55 45 77 64 83 98
13 33 74 20 55 45 77 64 83 98
13 33 74 20 55 45 77 64 83 98
13 33 74 20 55 45 77 64 83 98
13 33 20 74 55 45 77 64 83 98
13 33 20 74 55 45 77 64 83 98
13 33 20 55 74 45 77 64 83 98
13 33 20 55 74 45 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 77 64 83 98
13 33 20 55 45 74 64 77 83 98
13 33 20 55 45 74 64 77 83 98
13 33 20 55 45 64 74 77 83 98
13 33 20 55 45 64 74 77 83 98
13 33 20 55 45 64 74 77 83 98
13 33 20 45 55 64 74 77 83 98
13 33 20 45 55 64 74 77 83 98
13 33 20 45 55 64 74 77 83 98
13 20 33 45 55 64 74 77 83 98
13 20 33 45 55 64 74 77 83 98
13 20 33 45 55 64 74 77 83 98
Implementare:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ShakerSortCS { class Program { static void ShakerSort(int[] v, int len) { int j, k, stanga, dreapta, aux; stanga = 1; dreapta = len - 1; k = len - 1; do { for (j = dreapta; j >= stanga; j--) if (v[j - 1] > v[j]) { aux = v[j - 1]; v[j - 1] = v[j]; v[j] = aux; k = j; } stanga = k + 1; for (j = stanga; j <= dreapta; j++) if (v[j - 1] > v[j]) { aux = v[j - 1]; v[j - 1] = v[j]; v[j] = aux; k = j; } dreapta = k - 1; } while (stanga < dreapta); } 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()); } ShakerSort(v, len); for (i = 0; i < len; i++) Console.Write(v[i] + " "); Console.ReadLine(); } } }
Module Module1 Dim v(20) As Integer Sub ShakerSort(ByVal v() As Integer, ByVal len As Integer) Dim j, k, stanga, dreapta, aux As Integer stanga = 1 dreapta = len - 1 k = len - 1 Do While (stanga < dreapta) For j = dreapta To stanga Step -1 If (v(j - 1) > v(j)) Then aux = v(j - 1) v(j - 1) = v(j) v(j) = aux k = j End If Next j stanga = k + 1 For j = stanga To dreapta If (v(j - 1) > v(j)) Then aux = v(j - 1) v(j - 1) = v(j) v(j) = aux k = j End If Next j dreapta = k - 1 Loop End Sub Sub Main() Dim i, 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 i ShakerSort(v, len) For i = 0 To len - 1 Console.Write(v(i) & " ") Next i Console.ReadLine() End Sub End Module
// ShakerSortCPP.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; int v[20]; void ShakerSort(int v[], int len) { int i,j,k,stanga,dreapta,aux; stanga=1; dreapta=len-1; k=len-1; do { for (j=dreapta; j>=stanga; j--) if(v[j-1] > v[j]) { aux=v[j-1]; v[j-1]=v[j]; v[j]=aux; k=j; } stanga=k+1; for(j=stanga; j<=dreapta; j++) if(v[j-1]>v[j]) { aux=v[j-1]; v[j-1]=v[j]; v[j]=aux; k=j; } dreapta=k-1; } while (stanga<dreapta); } 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]; } ShakerSort(v, len); for (i=0; i<len; i++) cout<<v[i]<<" "; system("pause"); }
<?php function cocktailSort($my_array) { if (is_string($my_array)) $my_array = str_split(preg_replace('/\s+/','',$my_array)); do{ $swapped = false; for($i=0;$i<count($my_array);$i++){ if(isset($my_array[$i+1])){ if($my_array[$i] > $my_array[$i+1]){ list($my_array[$i], $my_array[$i+1]) = array($my_array[$i+1], $my_array[$i]); $swapped = true; } } } if ($swapped == false) break; $swapped = false; for($i=count($my_array)-1;$i>=0;$i--){ if(isset($my_array[$i-1])){ if($my_array[$i] < $my_array[$i-1]) { list($my_array[$i],$my_array[$i-1]) = array($my_array[$i-1],$my_array[$i]); $swapped = true; } } } }while($swapped); return $my_array; } $test_array = array(3, 0, 2, 5, -1, 4, 1); echo "Vector Original :\n"; echo implode(', ',$test_array ); echo "\nVector Sortat: \n"; echo implode(', ',cocktailSort($test_array)). PHP_EOL; sleep(10); ?>
{ int a[]={7,4,5,3,1,8,9,2,6,0}; int i; ShakerSort(a,10); for (i=0;i<10;i++) System.out.println(a[i]+” “); } } |
Rezultat:
InfoCad Blog 