Реализации алгоритмов/Сортировка/Пузырьком: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Метка: отменено
Строка 125: Строка 125:
}
}
}
}






</syntaxhighlight>
</syntaxhighlight>



Версия от 14:53, 1 декабря 2020

Ассемблер

Синтаксис Intel

    mov bx, offset array
    mov cx, n
for_i:
    dec cx
    xor dx, dx
for_j:
    cmp dx, cx
    jae exit_for_j
    jbe no_swap
    mov ah, byte ptr bx[di]
    mov byte ptr bx[di], al
    mov byte ptr bx[si], ah
no_swap:
    inc dx
    jmp for_j
exit_for_j:
    loop    for_i

Синтаксис AT&T (GNU)

.text
# void bubble_sort (unsigned *array, unsigned length);
.globl bubble_sort
    .type   bubble_sort, @function
bubble_sort:
    mov 8(%esp), %ecx # unsigned length
    cmp $1, %ecx
    jbe exit
    mov 4(%esp), %eax # unsigned *array
    dec %ecx
for_ecx:
    xor %edi, %edi
for_edi:
    mov (%eax,%edi,4), %ebx
    cmp %ebx, 4(%eax,%edi,4)
    jae  no_xchng
    mov 4(%eax,%edi,4), %edx
    mov %edx, (%eax,%edi,4)
    mov %ebx, 4(%eax,%edi,4)
no_xchng:
    inc %edi
    cmp %edi, %ecx
    jne for_edi
    loop for_ecx
exit:
    ret

C

#define SWAP(A, B) { int t = A; A = B; B = t; }

void bubblesort(int *a, int n)
{
  int j, nn;

  do {
    nn = 0;
    for (j = 1; j < n; ++j)
      if (a[j-1] > a[j]) {
        SWAP( a[j-1], a[j] );
        nn = j;
      }
    n = nn;
  } while (n);
}

C++

С использованием Template

#include <algorithm>
template< typename Iterator >
void bubble_sort( Iterator First, Iterator Last )
{
    while( First < --Last )
        for( Iterator i = First; i < Last; ++i )
            if ( *(i + 1) < *i )
                std::iter_swap( i, i + 1 );
}

Без использования Template

void bubble(int* a, int n)
{
  for (int i = n - 1; i > 0; i--)
    {
    for (int j = 0; j < i; j++)
      if (a[j] > a[j + 1])
      {
        int tmp = a[j];
        a[j] = a[j + 1];
        a[j + 1] = tmp;
      }
    }
}

C++

#include <cstddef>
#include <utility>

template<typename T>
void bubble_sort(T array[], std::size_t size)
{
    for (std::size_t idx_i = 0; idx_i < size - 1; idx_i++)
    {
        for (std::size_t idx_j = 0; idx_j < size - idx_i - 1; idx_j++)
        {
            if (array[idx_j + 1] < array[idx_j])
            {
                std::swap(array[idx_j], array[idx_j + 1]);
            }
        }
    }
}

C#

static int[] BubbleSort(int[] mas)
{
    int temp;
    for (int i = 0; i < mas.Length - 1; i++)
    {
        for (int j = 0; j < mas.Length - i - 1; j++)
        {
            if (mas[j + 1] < mas[j])
            {
                temp = mas[j + 1];
                mas[j + 1] = mas[j];
                mas[j] = temp;
            }
        }
    }
    return mas;
}

Delphi

Сортировка одномерного динамического целочисленного массива:

type
 TIntVec = array of Integer;
...
procedure BubbleSort(var a: TIntVec);
 var i, t, n, nn: Integer;
begin
 n:= Lenght(a);
 repeat
  nn:= 0;
  for i:= 1 to n-1 do
   if a[i-1] > a[i] then
    begin
     t:= a[i];
     a[i]:= a[i-1];
     a[i-1]:= t;
     nn:= i;
    end;
  n:= nn;
 until n=0;
end;

D

void bubbleSort(alias op, T)(T[] inArray) {
    foreach (i, ref a; inArray) {
        foreach (ref b; inArray[i+1..$]) {
            if (mixin(op)) {
                auto tmp = a;
                a = b;
                b = tmp;
            }
        }
    }
}

Fortran

do i=n-1,1,-1
do j=1,i
    if (a(j).gt.a(j+1)) then
        t=a(j)
        a(j)=a(j+1)
        a(j+1)=t
    end if
end do
end do

Java

 public int[] Sort(int[] array) {
        int i = 0;
        int goodPairsCounter = 0;
        while (true) {
            if (array[i] > array[i + 1]) {
                int q = array[i];
                array[i] = array[i + 1];
                array[i + 1] = q;
                goodPairsCounter = 0;
            } else {
                goodPairsCounter++;
            }
            i++;
            if (i == array.length - 1) {
                i = 0;
            }
            if (goodPairsCounter == array.length - 1) break;
        }
        return array;
}

Perl

for ( @out ) {
  for ( 0..$#out-1 ) {
      ( $out[$_], $out[$_+1] ) = ( $out[$_+1], $out[$_] ) if ( $out[$_] gt $out[$_+1] );
  }
}

Ruby

arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10]
swap = true
size = arr.length - 1
while swap
  swap = false
  for i in 0...size
    swap = arr[i] > arr[i + 1]
    arr[i], arr[i+1] = arr[i + 1], arr[i] if swap
  end
  size -= 1
end
puts arr.join(' ')
# output => 1 3 3 5 8 10 11 12 17 20

Python

from random import randint

N = 10
a = []

for i in range(N):
    a.append(randint(1, 99))
print(a)

i = 0
while i < N - 1:
    j = 0
    while j < N - 1 - i:
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
        j += 1
    i += 1
print(a)

VBA

Sub Sort(Mus() As Long)
Dim i As Long, tmp As Long, t As Boolean
t = True
Do While t
    t = False
    For i = 0 To UBound(Mus()) - 1
        If Mus(i) > Mus(i + 1) Then
            tmp = Mus(i)
            Mus(i) = Mus(i + 1)
            Mus(i + 1) = tmp
            t = True
        End If
    Next i
Loop
End Sub

PHP

for ($i = 0; $i < count($arr); $i++){
	for ($j = $i + 1; $j < count($arr); $j++) {
		if ($arr[$i] > $arr[$j]) {
			$temp = $arr[$j];
			$arr[$j] = $arr[$i];
			$arr[$i] = $temp;
		}
	}         
}

Bubble Sort

$size = count($arr)-1;
   for ($i=0; $i<$size; $i++) {
       for ($j=0; $j<$size-$i; $j++) {
           $k = $j+1;
           if ($arr[$k] < $arr[$j]) {
           	$temp = $arr[$k];
           	$arr[$k] = $arr[$j];
           	$arr[$j] = $temp;
           }
       }
   }

JavaScript

function sortBubble(data) {
    var tmp; 
    for (var i = data.length - 1; i > 0; i--) {  
        var counter=0;
        for (var j = 0; j < i; j++) {
            if (data[j] > data[j+1]) {
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
                counter++;
            }
        }  
        if(counter==0){
          break;
        } 
    }
  return data;
 };

JavaScript

function bubbleSort(seq:Number[]):Number[]{

    var sort = seq;
    var elem:Number;

    for(n in reverse [0..sizeof seq - 2]){
        for(i in [0..n] ){
            if(sort[i+1] < sort[i] ){
                elem = sort[i];
                sort[i] = sort[i+1];
                sort[i+1] = elem;
            }
        }
    }

    return sort;
}

Nemerle

using System.Console;
using Nemerle.Collections;

def arr = array [100, 45, 2, 5, 3, 122, 3, 5, 6, 1, 3];

foreach (i in [0..arr.Length-1])
    foreach (j in [0..arr.Length-2])
       when (arr[j] > arr[j+1])
           (arr[j], arr[j+1]) = (arr[j+1], arr[j]);

WriteLine($"Sorted list is a $(arr.ToList())");

TurboBasic 1.1

CLS
RANDOMIZE TIMER
DEFINT X, Y, N, I, J, D
N = 10 ' 32 766 - 62.7 SEC
DIM Y[N], Y1[N], Y2[N], Y3[N], Y4[N] 'FRE(-1)=21440-21456

PRINT " ZAPOLNENIE MASSIVA ELEMENTAMI"

FOR X = 1 TO N
   Y[X] = X
   PRINT Y[X];
NEXT X:PRINT

PRINT " PEREMESHIVANIJE ELEMENTOV MASSIVA"

PRINT " SLUCHAINYE CHISLA"

FOR X = 1 TO N
   YD=Y[X]
   XS=INT(RND*N)+1
   PRINT XS;
   Y[X]=Y[XS]
   Y[XS]=YD
NEXT X:PRINT

PRINT " PEREMESHANNYJ MASSIV"

FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT

'ALGORITM "SORTIROVKA PROSTYM OBMENOM" O(N^2)
MTIMER
FOR J=1 TO N-1 STEP 1
   F=0
   FOR I=1 TO N-J STEP 1
      'IF Y[I] > Y[I+1] THEN D=Y[I]:Y[I]=Y[I+1]:Y[I+1]=D:F=1
      IF Y[I] > Y[I+1] THEN SWAP Y[I],Y[I+1]:F=1

      LOCATE 8,1                    REM
      PRINT " ANYMACIJA SORTIROVKI" REM
      FOR X1=1 TO N                 REM ANIMATION BLOCK
         PRINT Y[X1];               REM
      NEXT X1:PRINT                 REM
      DELAY .5                      REM

   NEXT I
   IF F=0 THEN EXIT FOR
NEXT J
T1=MTIMER

PRINT " OTSORTIROVANNYJ MASSIV"

FOR X=1 TO N
   PRINT Y[X];
NEXT X:PRINT
PRINT "ELAPSED TIME=";T1

PL/SQL

type sort_lst is table of integer; 
--------------------------------------------------------
Function buble_sort(in_list IN sort_lst) return sort_lst
  IS   
   l_list sort_lst := sort_lst();
   l_flag boolean := true; -- есть перестановка?
   k pls_integer :=1;      -- номер просмотра
   n pls_integer;
   l_buffer pls_integer;
begin
    l_list := in_list;
    
         while l_flag loop
             l_flag := false;
               for i in l_list.first..l_list.last-k loop
                   if l_list(i) > l_list(i+1) then
                       l_buffer := l_list(i);
                       l_list(i):=l_list(i+1);
                       l_list(i+1) := l_buffer;
                       l_flag := true;
                   end if;
               end loop;
               k:=k+1;
         end loop;
         
         return l_list;
         
end buble_sort;

Flex, ActionScript

function bubbleSort(array:Vector.<Number>) {
    for (var i:uint = 0; i < array.length; i++) {
        for (var j:uint = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                var t:int = array[j];
                array[j] = array[j + 1];
                array[j + 1] = t;
            }
        }
    }
}

Ссылки