Aspecte teoretice:
În practică algoritmul de sortare cel mai rapid este Quicksort (numit sortare rapidă), care folosește partiționarea ca idee de bază. Este mai rapid decât orice metodă de sortare simplă, se execută bine pentru fișiere sau tabele mari, dar ineficient pentru cele mici. Strategia de bază folosită este “divide et impera”, pentru că este mai ușor de sortat două tabele mici, decât una mare. Algoritmul este ușor de implementat, lucrează destul de bine în diferite situații și consumă mai puține resurse decât orice altă metodă de sortare în multe situații.
Metoda QuickSort presupune găsirea poziției finale pe care o ocupă elementul de pe prima poziție comparându-l cu elementele din cealaltă partiție a tabelului, acest algoritm realizându-se până când partiția are 1 element.
Analiza complexității:
Potrivit algoritmului, fiecare element este comparat cu pivotul, adică operațiunea este de O(N), tabela este divizată în două părți, fiecare parte este divizată iarăși în două…. Dacă fiecare parte este împărțită aproximativ în jumătate, va rezulta log2N împărțiri. Deci timpul de execuție al Quicksortului în caz mediu este de O(N log2 N), iar în caz nefavorabil O(N^2) .
Exemplu Pas cu Pas:
Pentru următoarea configurație a tabelului initial: 6 5 4 3 7 2 9 10 algoritmul va sorta vectorul astfel:
6 5 4 3 7 2 9 10 i=6; j=10; 6<10
6 5 4 3 7 2 9 10 i=6; j=9; 6<9
6 5 4 3 7 2 9 10 i=6; j=2; schimba(6,2)
2 5 4 3 7 6 9 10 i=5; j=6; 5<6
2 5 4 3 7 6 9 10 i=4; j=6; 4<6
2 5 4 3 7 6 9 10 i=3; j=6; 3<6
2 5 4 3 7 6 9 10 i=7; j=6; schimba (7,6)
2 5 4 3 6 7 9 10 j=6; i=7; stop(j<i)
Procedeul se va repeta cu cele 2 partiții ((1,j-1) si (i,n) până când fiecare partiție va avea un element:
2 3 4 5 6 7 9 10
Implementare:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace QuickSortCS { class Program { static void QuickSort(int stanga, int dreapta, int[]a) { int i, j, x, y; i = stanga; j = dreapta; x = a[(stanga + dreapta) / 2]; while (i <= j) { while (a[i] < x) { i = i + 1; } while (x < a[j]) { j = j - 1; } if (i <= j) { y = a[i]; a[i] = a[j]; a[j] = y; i = i + 1; j = j - 1; } } if (stanga < j) QuickSort(stanga, j, a); if (i < dreapta) QuickSort(i, dreapta, a); } static void Main(string[] args) { int i, n; int [] a = new int[100]; Console.Write("Dati n: "); n = Convert.ToInt32(Console.ReadLine()); for (i = 1; i <= n; i++) { Console.Write("a[" + i + "]="); a[i] = Convert.ToInt32(Console.ReadLine()); } QuickSort(1, n, a); for (i = 1; i <= n; i++) { Console.Write(a[i] + " "); } Console.ReadLine(); } } }
Module Module1 Dim n As Integer Dim a(1000) As Integer Sub QuickSort(ByVal stanga As Integer, ByVal dreapta As Integer) Dim i, j, x, y As Integer i = stanga j = dreapta x = a((stanga + dreapta) / 2) While i <= j While a(i) < x i = i + 1 End While While x < a(j) j = j - 1 End While If i <= j Then y = a(i) a(i) = a(j) a(j) = y i = i + 1 j = j - 1 End If End While If stanga < j Then QuickSort(stanga, j) End If If i < dreapta Then QuickSort(i, dreapta) End If End Sub Sub Main() Dim i As Integer Console.WriteLine("Dati numarul de elemente n: ") n = Convert.ToInt32(Console.ReadLine()) For i = 1 To n Console.Write("a[" & i & "]=") a(i) = Convert.ToInt32(Console.ReadLine()) Next i QuickSort(1, n) For i = 1 To n Console.Write(a(i) & " ") Next i Console.ReadLine() End Sub End Module
// QuickSortCPP.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; int n,a[1000]; void QuickSort(int stanga, int dreapta) { int i, j, x, y; i=stanga; j=dreapta; x=a[(stanga+dreapta)/2]; while (i<=j) { while (a[i]<x) { i=i+1; } while (x<a[j]) { j=j-1; } if (i<=j) { y=a[i]; a[i]=a[j]; a[j]=y; i=i+1; j=j-1; } } if (stanga<j) QuickSort(stanga,j); if (i<dreapta) QuickSort(i,dreapta); } void main() { int i; cout<<"Dati n: "; cin>>n; for (i=1;i<=n;i++) { cout<<"a["<<i<<"]="; cin>>a[i]; } QuickSort(1,n); for (i=1;i<=n;i++) cout<<a[i]<<" "; system("pause"); }
<?php function quick_sort($my_array) { $loe = $gt = array(); if(count($my_array) < 2) { return $my_array; } $pivot_key = key($my_array); $pivot = array_shift($my_array); foreach($my_array as $val) { if($val <= $pivot) { $loe[] = $val; }elseif ($val > $pivot) { $gt[] = $val; } } return array_merge(quick_sort($loe),array($pivot_key=>$pivot),quick_sort($gt)); } $my_array = array(3, 0, 2, 5, -1, 4, 1); echo 'Vectorul original : '.implode(',',$my_array).'\n'; $my_array = quick_sort($my_array); echo 'Vectorul sortat : '.implode(',',$my_array); sleep(10); ?>
{ public static void QSort(int stanga, int dreapta, int a[]) { int i, j, x, y; i=stanga; j=dreapta; x=a[(stanga+dreapta)/2]; while (i<=j) { while (a[i]<x) { i=i+1; } while (x<a[j]) { j=j-1; } if (i<=j) { y=a[i]; a[i]=a[j]; a[j]=y; i=i+1; j=j-1; } } if (stanga<j) QSort(stanga,j,a); if (i<dreapta) QSort(i,dreapta,a); } public static void main(String args[]) { int a[]={7,4,5,3,1,8,9,2,6,0}; int i; QSort(0,9,a); for (i=0;i<10;i++) System.out.println(a[i]+” “); } } |
module QSort where
qsort [] = []
qsort (x:xs)
= qsort pre ++ [x] ++ qsort post
where
pre = [ n | n <- xs, n < x ]
post = [ n | n <- xs, n >= x ]
Rezultat:
InfoCad Blog 