Kody źródłowe/Sortowanie bąbelkowe

Sortowanie bąbelkowe • Kod źródłowy
Sortowanie bąbelkowe
Kod źródłowy
Wikipedia
Zobacz w Wikipedii hasło Sortowanie bąbelkowe
Spis treści
  • $lz - ilość liczb do posortowania
  • $tab[] - tablica elementów ciągu
  • $tmp - zmienna pomocnicza
for(( i=1 ; $i < $lz ; i++ )) ; do
        for(( j=$(($lz-1)) ; $j >= $i ; j-- )); do
                if [ ${tab[j-1]} -gt ${tab[j]} ]; then
                        tmp=${tab[j-1]}
                        tab[j-1]=${tab[j]}
                        tab[j]=$tmp
                fi
        done
done

Wersja klasyczna:

void bubblesort(int table[], int size)
{
	int i, j, temp;
	for (i = 0; i<size-1; i++)
        {
		for (j=0; j<size-1-i; j++)
		{
			if (table[j] > table[j+1])
			{
				temp = table[j+1];
				table[j+1] = table[j];
				table[j] = temp;
			}
		}
        }
}

Wersja z zapamiętaniem czy dokonano zamiany:

  • tab[] - tablica elementów ciągu np. o indeksach od 0 do 99
  • tmp - zmienna pomocnicza o formacie elementu tablicy tab[]
  • change - zmienna logiczna
typedef int TYP

void bubblesort( TYP a[], int n ) 
{
  int i,j;
  TYP tmp;
  int change;

  for (i=0; i<n-1; ++i) 
  {
       change=0;
       for (j=0; j<n-1-i; j++)
       { 
          if (a[j+1] < a[j])   //porównanie sąsiądów
          {  
              tmp = a[j];      
              a[j] = a[j+1];
              a[j+1] = tmp;    //wypchanie bąbelka     
              change=1;
          }
       }
       if(!change) break;      // nie dokonano zmian - koniec!
  }
}

Wersja z zapamiętaniem miejsca ostatniej zamiany:

void bubblesortlastchange(int tab[], int size)
{
	int loop, last, i, j, temp;
	last = size - 1;

	for(i = size - 1; i > 0; i--)
	{
		loop = last;
		last = 0;
		for(j = 0; j < loop; j++)
		{
			if(tab[j] > tab[j+1])
			{
				last = j;
				temp = tab[j];
				tab[j] = tab[j+1];
				tab[j+1] = temp;
			}
		}
	}
template <class T>
    void bubble_sort(T* tab, int n) {
        bool swapped; // Czy zamieniono w ostatnim obrocie?
        
        do {
            swapped = false;
            for (int i = 0; i < n - 1; ++i) {
                if (tab[i] > tab[i + 1]) {  
                    swap(tab[i], tab[i + 1]);
                    swapped = true;
                }
            }
        } while (swapped);
    }

C# (bez znacznika zmiany change)

edytuj
public static void BubbleSort(IComparable[] a)
{
  int n = a.Length;
  for(int i = 1; i < n; ++i)
    for(int j = n - 1; j >= i; j--)
      if(a[j - 1].CompareTo(a[j]) > 0)
      {
        IComparable x = a[j - 1];
        a[j - 1] = a[j];
        a[j] = x;
      }
}

C# (inny przykład)

edytuj
public static void Swap(int[] ar, int first)
{
    int hold = ar[first];
    ar[first] = ar[first + 1];
    ar[first + 1] = hold;
}

public static void BubbleSort(int[] ar)
{
    for (int pass = 1; pass < ar.Length; pass++)
        for (int i = 0; i < ar.Length - 1; i++)
            if (ar[i] > ar[i + 1])
                Swap(ar, i);
}
$a = array (3, 7, 14, 1, 20, 14, 15);						//Utworzenie tablicy
$n = count($a);									//Zliczenie elementów tablicy do zmiennej $n

for ($i = 1; $i < $n; $i++)
	for ($j = $n - 1; $j >= $i; $j--)
		if ($a[$j - 1] > $a[$j])					//Porównanie sąsiednich elementów tablicy
			list($a[$j - 1], $a[$j]) = array($a[$j], $a[$j - 1]);	//Zamiana miejscami dwóch elementów tablicy

Pascal

edytuj
Const
numbers = 6; // ilość sortowanych komórek w tablicy

Type
table = Array[1..numbers] Of Integer;

Var
counter : Integer;
liczby : table;

Procedure bubble_sort();

  Var
  check, memory, run : Integer; // ilość sprawdzeń w przebiegu, komórka pamięci, ilość przebiegów

  Begin
    For run := 1 To numbers - 1 Do
      Begin
      check := numbers - run;
	For counter := 1 To check Do
	  If liczby[counter] > liczby[counter + 1]
	  Then
	    Begin
	    memory := liczby[counter];
	    liczby[counter] := liczby [counter + 1];
	    liczby[counter + 1] := memory;
	    End;
      End;
  End;

Python

edytuj
data = [10, 3, 7, 8, 1, 6, 2, 9, 4, 5, 0]

def sort(data):
    for i in range(len(data) - 1, 0, -1):
        for j in range(i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]

sort(data)
print(data)

PL/SQL

edytuj
  • TAB() - zmienna tablicowa indeksowana zawierająca elementy ciągu
  • X - zmienna pomocnicza o formacie elementu tablicy TAB()
FOR I IN 1..TAB.COUNT-1 LOOP
   FOR J IN REVERSE I+1..TAB.COUNT LOOP
     IF TAB(J-1)>TAB(J) THEN
     X:=TAB(J);
     TAB(J):=TAB(J-1);
     TAB(J-1):=X;
     END IF;
   END LOOP;
END LOOP;
fn bubble_sort(array: &mut [i32]) {
    for _j in 0..array.len() - 1 {
        for i in 0..array.len() - 1 {
            if array[i] > array[i + 1] {
                array.swap(i, i + 1);
            }
        }
    }
}

Sortowanie bąbelkowe mieszane (shuttle sort, cocktail sort) w C#

edytuj
public static void ShuttleSort(IComparable[] a)
{
  int l = 1;
  int p = a.Length - 1;
  int k = p;
  do
  {
    for(int j = p; j >= l; j--)
      if(a[j - 1].CompareTo(a[j]) > 0)
      {
        IComparable x = a[j - 1];
        a[j - 1] = a[j];
        a[j] = x;
        k = j;
      }
    l = k + 1;
    for(int j = l; j <= p; j++)
      if(a[j - 1].CompareTo(a[j]) > 0)
      {
        IComparable x = a[j - 1];
        a[j - 1] = a[j];
        a[j] = x;
        k = j;
      }
    p = k - 1;
  }
  while (l < p);
}
    public Integer[] bubbleSort(Integer[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = temp;
                }
            }
        }
    return a;
    }

Java (minimalizacja LOC)

edytuj
    public void bubbleSort(Integer[] a) {
        for (int i = 0, size = a.length - 1; i < a.length - 1; i++, size--)
            for (int j = 0; j < size; j++)
                for (int temp = a[j]; a[j] > a[j + 1]; a[j] = a[j + 1], a[j + 1] = temp) ;
    }

Javascript

edytuj
/**
 * Prototyp dla tablicy zamieniający kolejność dwóch indeksów tej tablicy
 * @param x
 * @param y
 * @returns {Array}
 */
Array.prototype.swap = function (x, y) {
    var b = this[x];
    this[x] = this[y];
    this[y] = b;
    return this;
};

/**
 * Funkcja sortowania bąbelkowego
 * @param array
 */
function bubbleSort(array) {
    var arrayLength = array.length;
    do {
        for (let i = 0; i < arrayLength - 1; i++) {
            if (array[i] > array[i + 1]) {
                array.swap(i, i + 1);
            }
        }
        arrayLength = arrayLength - 1;
    }
    while (arrayLength > 1)
}