Сортировка пузырьком
Материал из Википедии — свободной энциклопедии
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).
Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками.
Содержание |
[править] Алгоритм
Пример сортировки пузырьком списка случайных чисел.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка.
[править] Примеры реализации
[править] Псевдокод
function bubblesort (A : list[1..n]) {
var int i, j;
for i from n downto 2 {
for j from 1 to i-1 {
if (A[j] > A[j+1])
swap(A[j], A[j+1])
}
}
}
[править] Assembler
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
[править] GNU Assembler
.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) {A=A^B;B=A^B;A=A^B;} void bubblesort(int A[], int n) { int i, j; for(i = n-1 ; i > 0 ; i--) { for(j = 0 ; j < i ; j++) { if( A[j] > A[j+1] ) SWAP(A[j],A[j+1]); } } }
[править] C++
#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 ); }
[править] C#
void BubbleSort(ref int[] a) { for(int i = a.Length - 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]; {{1}} a[j+1] = tmp; } }
[править] Delphi
Сортировка одномерного динамического целочисленного массива: type TIntVec = array of Integer; ... procedure BubbleSort(var a: TIntVec); var i,p,n: Integer; b: boolean; begin n:= Length(a)-1; if n < 1 then exit; repeat b:= true; Dec(n); for i:= 0 to n do if a[i] > a[i+1] then begin p:= a[i]; a[i]:= a[i+1]; a[i+1]:= p; b:= false; end; until b; end;
[править] D
void bubleSort(int[] array) { int length = array.length; for (int i = length - 1; i > 0; --i) { for (int j = 0; j < i; ++j) { if (array[j] > array[j + 1]) { int tmp = array[j + 1]; array[j + 1] = array[j]; array[j] = 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 endif enddo enddo
[править] Java
void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } void bubblesort(int[] arr){ for(int i = arr.length-1 ; i >= 0 ; i--){ for(int j = 0 ; j < i ; j++){ if( arr[j] > arr[j+1] ) swap(arr, j, j+1); } } }
[править] Pascal
for i:=n-1 downto 1 do {n - размер массива M[]} for j:=1 to i do if M[j]>M[j+1] then begin tmp:= M[j]; M[j]:= M[j+1]; M[j+1]:= tmp; end; write('вывод значений M[]: '); for i:=1 to n do write(M[i]:4); writeln;
[править] Ruby
arr = [5, 20, 3, 11, 1, 17, 3, 12, 8, 10] swap = 1 while swap > 0 swap = 0 for i in 0..arr.length - 1 break if arr[i + 1] == nil swap += 1 if arr[i] > arr[i + 1] arr[i], arr[i+1] = arr[i + 1], arr[i] if arr[i] > arr[i + 1] end end puts "#{arr.join(" ")}" # output => 1 3 3 5 8 10 11 12 17 20
[править] Python
def swap(arr, i, j): arr[i], arr[j] = arr[j], arr[i] def bubble_sort(arr): i = len(arr) while i > 1: for j in xrange(i - 1): if arr[j] > arr[j + 1]: swap(arr, j, j + 1) i -= 1
[править] VBA
Sub Sort(Mus() As Long) Dim n As Long, i As Long, tmp As Long i = 1 Do While (i < UBound(Mus)) If Mus(i) > Mus(i + 1) Then tmp = Mus(i) Mus(i) = Mus(i + 1) Mus(i + 1) = tmp If i > 1 Then i = i - 1 Else i = i + 1 End If Else i = i + 1 End If Loop End Sub
[править] Усовершенствованный алгоритм сортировки пузырьком в Pascal
P:=True; {Перестановка есть} K:=1; {Номер просмотра} While P Do Begin P:=false; For i:=1 To n-k Do If X[i] > X[i+1] Then Begin A:=X[i]; X[i]:=X[i+1]; X[i+1]:=A; P:=true; End; k:=k+1; End;
[править] PHP
$size = count($arr)-1; for ($i = $size; $i>=0; $i--) { for ($j = 0; $j<=($i-1); $j++) if ($arr[$j]>$arr[$j+1]) { $k = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $k; } }
[править] JavaScript
function sortBubble(data) { var tmp; for (var i = data.length - 1; i > 0; i--) { 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; } } } return data; }
[править] JavaFX
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; }
[править] Литература
- Ананий В. Левитин Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 144-146. — ISBN 0-201-74395-7
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
