Сортировка пузырьком
Материал из Википедии — свободной энциклопедии
Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n2).
Содержание |
[править] Алгоритм
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Иногда на каждом шаге массив просматривается то с начала, то с конца. Это называется шейкерная сортировка.
[править] Примеры реализации
[править] Псевдокод
function bubblesort (A : list[1..n]) {
var int i, j;
for i from n downto 1 {
for j from 1 to i-1 {
if (A[j] > A[j+1])
swap(A[j], A[j+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];{{неоднозначность}} a[j+1] = tmp; } }
[править] 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++
template <class T> void Bubble_sort( T a[], const int n ) { for (int i = n-1; i>0; --i) for (int j = 0; j<i; ++j) if (a[j] > a[j+1]) { swap(a[j], a[j+1]); } }
[править] 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); }
[править] PHP
for ($i = (count($arr)-1); $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; } }
[править] Pascal
Процедура сортировки одномерного динамического целочисленного массива в среде Delphi (Коднянко Владимир): type TIntVec = array of Integer; ... procedure BubbleSort(var a: TIntVec); var i,p: 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;
[править] 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
[править] Assembler
mov bx, offset array mov cx, n for_i: dec cx xor dx, dx for_j: cmp dx, cx jae exit_for_j mov si, dx mov di, dx inc di mov al, byte ptr bx[si] cmp al, byte ptr bx[di] 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
[править] Пример реализации усовершенствованного алгоритма (язык Pascal)
Источник: Программирование на языке высокого уровня: Текст лекций/ Н. В. Ефимушкина, С. П. Орлов, В. М. Чухонцев; Самар. гос. техн. ун-т. — Самара, 2002. 182 с.
P := True; {Перестановка есть} K := 1; {Номер просмотра} While P Do Begin L:=0; {Количество перестановок} 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; inc(L); End; If L=0 Then P:=False; k:=k+1; {Я бы тут написал inc(k)!} End;
[править] Литература
- Ананий В. Левитин Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 144-146. — ISBN 0-201-74395-7
