Bubble Sort

Aspecte teoretice:

Această metodă se rezumă la a compara fiecare element cu celelalte, făcându-se interschimbarea dacă elementul mai mare are indexul mai mic. Este cea mai simplă metodă de sortare și nu necesită cunoașterea detaliată a limbajului de programare. Poate fi folosită cu succes de către începători.

Analiza complexității:

Bubble sort este o metodă de sortare simplă, eficientă pentru un număr mic de elemente (mai puțin de 15), dar nu pentru tabele mari. Nu necesită foarte multă memorie, dar este de două ori mai lentă decât InsertionSort în aproape orice situație. Timpul de execuție depinde de input, adică de ordinea inițială al elementelor. Dacă tabela este deja sortată e nevoie de un singur pas, adică N-1 comparări. În cazul cel mai nefavorabil sunt necesare N ×(N-1)/2 comparări și N × (N-1)/2 interschimbări. Performanța algoritmului în caz general este mai greu de analizat dar este asemănător cazului nefavorabil. Complexitatea timpului al Bubble sortului este O(N^2).

Exemplu pas cu pas:

6 5 4 3 2 1
5 6 4 3 2 1
5 4 6 3 2 1
5 4 3 6 2 1
5 4 3 2 6 1
5 4 3 2 1 6
4 5 3 2 1 6
4 3 5 2 1 6
4 3 2 5 1 6
4 3 2 1 5 6
3 4 2 1 5 6
3 2 1 4 5 6
2 3 1 4 5 6
2 1 3 4 5 6
1 2 3 4 5 6

Implementare:

Cod Sursa C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace BubbleSortCS
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] v = new int[25];
            int i, n, ok, aux;
            Console.Write("Numarul de elemente n= ");
            n = Convert.ToInt32(Console.ReadLine());
            for (i = 1; i <= n; i++)
            {
                Console.Write("v[" + i + "]=");
                v[i] = Convert.ToInt32(Console.ReadLine());
            }
            for (i = 1; i <= n; i++)
                do
                {
                    ok = 1;
                    for (i = 1; i <= n - 1; i++)
                    {
                        if (v[i] > v[i + 1])
                        {
                            aux = v[i];
                            v[i] = v[i + 1];
                            v[i + 1] = aux;
                            ok = 0;
                        }
                    }
                } while (ok != 1);
            for (i = 1; i <= n; i++)
            {
                Console.Write(v[i] + " ");
            }
            Console.ReadLine();
        }
    }
}

Cod Sursa VB

Module Module1
    Dim v(25) As Integer
    Dim i, n, ok, aux As Integer
 
    Sub Main()
        Console.Write("Numarul elementelor n = ")
        n = Convert.ToInt32(Console.ReadLine())
        For i = 1 To n
            Console.Write("v[" & i & "]=")
            v(i) = Convert.ToString(Console.ReadLine())
        Next i
        Do While (ok <> 1)
            ok = 1
            For i = 1 To n - 1
                If (v(i) > v(i + 1)) Then
                    aux = v(i)
                    v(i) = v(i + 1)
                    v(i + 1) = aux
                    ok = 0
                End If
            Next i
        Loop
        For i = 1 To n
            Console.Write(v(i) & " ")
        Next i
        Console.ReadLine()
    End Sub
 
End Module

Cod Sursa C++

// BubbleSortCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include<iostream>
#include<conio.h>
 
using namespace std;
 
int v[25];
int i, n, ok, aux;
 
void main()
{
	cout<<"n=";
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cout<<"v["<<i<<"]=";
		cin>>v[i];
	}
	for(i=1;i<=n;i++)
	//sortarea crescatoare
	do
	{
		ok=1;
		for(i=1;i<=n-1;i++)
		if(v[i]>v[i+1])
		{
			// interschimbare
			aux=v[i];
			v[i]=v[i+1];
			v[i+1]=aux;
			ok=0;
		}
	} while(ok!=1);
	for(i=1;i<=n;i++)
	cout<<v[i]<<" ";
	system("Pause");
}
 

Cod Sursa PHP

<?php

 
function bubble_Sort($my_array )
{
	do
	{
		$swapped = false;
		for( $i = 0, $c = count( $my_array ) - 1; $i < $c; $i++ )
		{
			if( $my_array[$i] > $my_array[$i + 1] )
			{
				list( $my_array[$i + 1], $my_array[$i] ) =
						array( $my_array[$i], $my_array[$i + 1] );
				$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(', ',bubble_Sort($test_array)). PHP_EOL;
sleep(10);
?>

Cod Sursa JAVA

 

//Complexitate: Nefavorabil: O(n^2); Mediu: O(n^2); Favorabil: O(n)class BubbleSortJAVA {   public static void main(String args[])   {     int[] v = {7,4,5,3,1,8,9,2,6,0};     int i, ok, aux;     for(i=0;i<9;i++)     //sortarea crescatoare     do     {       ok=1;       for(i=0;i<9;i++)       if(v[i]>v[i+1])       {         // interschimbare         aux=v[i];         v[i]=v[i+1];         v[i+1]=aux;         ok=0;       }     } while(ok!=1);     for(i=0;i<10;i++)     System.out.println(v[i]);   } }

 

Cod Sursa LISP

 

(defun bubble_sort (v &aux schimbat
(n (length v)))
(loop
(setq schimbat nil)
(dotimes (i (- n 1))
(when (>(aref v i)(aref v (+ i 1)))
(psetf (aref v i)(aref v(+ i 1))
(aref v (+ i 1))(aref v i)
schimbat t)))
(unless schimbat (return v))))

Rezultat: