Algorithm Implementation/Sorting/Bubble sort
From Wikibooks, the open-content textbooks collection
Contents |
[edit] Ada
Sorts an array of integers.
type Integer_array is Array (Natural range <>) of Integer; procedure Bubble_Sort (A : in out Integer_Array) is Temp : Integer; begin for I in reverse A'Range loop for J in A'First .. I loop if A(I) < A(J) then Temp := A(J); A(J) := A(I); A(I) := Temp; end if; end loop; end loop; end Bubble_Sort;
[edit] Assembly
MASM. Sorts an array of DWORDS with len elements.
bs proc array:DWORD,len:DWORD mov ecx,len mov edx,array bs_o: xor ebp,ebp bs_i: mov eax,DWORD PTR [edx+ebp*4+4] cmp DWORD PTR [edx+ebp*4],eax jb @F xchg eax,DWORD PTR [edx+ebp*4] mov DWORD PTR [edx+ebp*4+4],eax @@: add ebp,1 cmp ebp,ecx jb bs_i loop bs_o pop ebp retn 8 bs endp
[edit] AutoIt
Sorts an array of variant data types
Func BubbleSort(ByRef $bs_array) For $i = UBound($bs_array) - 1 To 1 Step -1 For $j = 2 To $i If $bs_array[$j - 1] > $bs_array[$j] Then $temp = $bs_array[$j - 1] $bs_array[$j - 1] = $bs_array[$j] $bs_array[$j] = $temp EndIf Next Next Return $bs_array EndFunc ;==>BubbleSort
[edit] BASIC
Sub Bubblesort(Array() as Integer, Length as Integer) Dim I as Integer Dim J as Integer Dim Temp as Integer For I = Length -1 To 1 Step -1 For J = 0 to I - 1 IF Array(J)>Array(J+1) THEN ' Compare neighboring elements Temp = Array(j) Array(J) = Array(J+1) Array(J+1) = Temp End If Next J Next I End Sub
[edit] BlitzBasic
unsorted=1 while unsorted unsorted=0 for x = 1 to 10 if ar[x]<ar[x-1] unsorted=1 tmp = ar[x] ar[x] = ar[x-1] ar[x-1] = tmp end if next wend
[edit] FORTRAN
SUBROUTINE sort (array_x, array_y, datasize)
Global Definitions
REAL array_x(*)
REAL array_y(*)
INTEGER datasize
Local
REAL x_temp
REAL y_temp
LOGICAL inorder
inorder = .false.
do 90 while (inorder.eq..false.)
inorder = .true.
do 91 i=1, datasize
Check Equilivant Points and swap those on Y
if (array_x(i).eq.array_x(i+1) ) then
if (array_y(i).lt.array_y(i+1) ) then
x_temp = array_x(i)
y_temp = array_y(i)
array_x(i) = array_x(i+1)
array_y(i) = array_y(i+1)
array_x(i+1) = x_temp
array_y(i+1) = y_temp
inorder = .false.
endif
endif
If x needs to be swapped, do so
if (array_x(i).lt.array_x(i+1) )then
x_temp = array_x(i)
y_temp = array_y(i)
array_x(i) = array_x(i+1)
array_y(i) = array_y(i+1)
array_x(i+1) = x_temp
array_y(i+1) = y_temp
inorder = .false.
endif
91 continue
90 continue
END SUBROUTINE sort
[edit] C
void bubbleSort(int* array, int size) { int swapped; int i; for (i = 1; i < size; i++) { swapped = 0; //this flag is to check if the array is already sorted int j; for(j = 0; j < size - i; j++) { if(array[j] > array[j+1]) { int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; swapped = 1; } } if(!swapped){ break; //if it is sorted then stop } } }
[edit] C++
C++ can use the C bubble sort above, or use this for random-access iterators of generic containers and a generic comparison operator:
#include <algorithm> template<typename Iterator> void bubbleSort(Iterator first, Iterator last) { Iterator i, j; for (i = first; i != last; i++) for (j = first; j < i; j++) if (*i < *j) std::iter_swap(i, j); // or std::swap(*i, *j); } template<typename Iterator, class StrictWeakOrdering> void bubbleSort(Iterator first, Iterator last, StrictWeakOrdering compare) { Iterator i, j; for (i = first; i != last; i++) for (j = first; j < i; j++) if (compare(*i, *j)) std::iter_swap(i, j); }
[edit] C#
static void BubbleSort(IComparable[] array) { int i, j; IComparable temp; boolean flag = true; for (i = array.Length - 1; i > 0 && flag; i--) { flag = false; for (j = 0; j < i; j++) { if (array[j].CompareTo(array[j + 1]) > 0) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; flag = true; } } } }
[edit] C# 2.0
static void BubbleSort<T>(IList<T> array) where T : IComparable<T> { int i, j; T temp; for (i = array.Count - 1; i > 0; i--) { for (j = 0; j < i; j++) { if (array[j].CompareTo(array[j + 1]) > 0) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } }
[edit] D
void bubbleSort(T)(T[] array) { bool swapped; T temp = void; for (int j, i = array.length - 1; i; swapped = false, i--) { for (j = 0; j < i; j++) if (array[j] > array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; swapped = true; } if (!swapped) break; } }
[edit] Haskell
bubbleSort []=[]
bubbleSort x=
(iterate swapPass x) !! ((length x)-1)
where
swapPass [x]=[x]
swapPass (x:y:zs)
| x>y = y:swapPass (x:zs)
| otherwise = x:swapPass (y:zs)
[edit] Java
public static int[] bubblesort(int[] numbers) { boolean swapped = true; for(int i = numbers.length - 1; i > 0 && swapped; i--) swapped = false; for (int j = 0; j < i; j++) { if (numbers[j] > numbers[j+1]) { int temp = numbers[j]; numbers[j] = numbers[j+1]; numbers[j+1] = temp; swapped = true; } } } return numbers; }
[edit] JavaScript
JavaScript Implementation with simple HTML test page
<html> <head> <script type="text/javascript"> // GLOBAL FUNCTION Array.prototype.bubble_sort = function() { var i, j; var newarray = this.slice(0); var swap = function(j, k) { var temp = newarray[j]; newarray[j] = newarray[k]; newarray[k] = temp; return(true); } var swapped = false; for(i=1; i<newarray.length; i++) { for(j=0; j<newarray.length - i; j++) { if (newarray[j+1] < newarray[j]) { swapped = swap(j, j+1); } } if (!swapped) break; } return(newarray) } // LOCAL FUNCTION show = function (inarray, title) { document.writeln("<h4>"+title+":</h4>"); document.writeln(inarray.join(", ")+"<br />"); } </script> </head> <body> <script> // MAIN // test bubble_sort function sorted_array = [1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1].bubble_sort(); show(sorted_array, "Sorted Array"); // result: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7] </script> </body> </html>
[edit] Pascal
Procedure BubbleSort:
const
MAXINTARRAY : 1000; { Set this value to fit your data needs for max array size }
STARTINTARRAY : 1; { Set 1 _or_ 0; indicates the lower index of the array }
Type
IntArray : Array[STARTINTARRAY..MAXINTARRAY] of integer;
BubbleSort is an all purpose sorting procedure that is passed an array of
integers and returns that same array with the array elements sorted as desired.
Parameters are used to control the sorting operation:
If you want to sort the entire array, pass a value in Count that signals the number
of elements you want sorted. BubbleSort will then sort Count number of elements starting
with the first element in the array.
If you want to sort a subset of elements within the array, pass 0 in Count and pass
a beginning and ending subset index number in First and Last, respectively.
The sort will be either ascending or decending as controlled by the parameter Acend:
Pass True in Acend and the sort will be ascending. Pass False and the sort will be
decending.
Data: The array to be sorted.
NOTE: Sample is a var and will be modified by BubbleSort, unless the array is
already in a sorted state.
Count: 0 _or_ the number of elements to be sorted, starting with the first element.
First: The first element to be sorted in a subset of the array.
Last: The last element to be sorted in a subset of the array.
Acend: Flag to indicate the sort order. True is ascending order. False is decending.
Succ: Flag returns result of BubbleSort
0 = success.
1 = Failed. Parameter First has value below allowed first index value.
2 = Failed. Parameter Last has value above allowed last index value.
3 = Failed. Parameter Last has value below allowed first index value.
===================================================================================*)
Procedure BubbleSort( Var Data : IntArray; Count : integer; First : integer; Last : integer; Acend : boolean; Var Succ : integer ); var i, temp, s_begin, s_end, numsort : integer; sorted : boolean; Begin { initialize for full array sort } s_begin := STARTINTARRAY; s_end := STARTINTARRAY + count - 1 ; numsort := Count; Succ := 0; { assume success } { check for a subset sort; check parameters for correctness } if (Count = 0) then Begin If (First < STARTINTARRAY) then Begin { error: sort start index too low } Succ := 1; Exit; End; If (Last > MAXINTARRAY) then Begin { error: sort end index too high } Succ := 2; Exit; End; if (Last < STARTINTARRAY) then Begin { error: sort end index too low } Succ := 3; Exit; End; s_begin := First; s_end := Last; numsort := Last - First + 1; End; If numsort <= 1 then Exit; { only one element, so exit } If Acend then Begin { do the ascending sort } Repeat sorted := true; { flag default is true } For i := s_begin to s_end -1 do if (Data[i] < Data[i+1]) then Begin { swap contents of Data[i] and Data[i+1] } temp := Data[i]; Data[i] := Data[i+1]; Data[i+1] := temp; { set flag to indicate a swap occured; i.e., sort may not be completed } sorted := false; End; Until sorted; End Else Begin { do the descending sort } Repeat sorted := true; { flag default is true } For i := s_begin to s_end -1 do if (Data[i] < Data[i+1]) then Begin { swap contents of Data[i] and Data[i+1] } temp := Data[i]; Data[i] := Data[i+1]; Data[i+1] := temp; { set flag to indicate a swap occured; i.e., sort may not be completed } sorted := false; End; Until sorted; End; End;
A simplified version:
Procedure BubbleSort(var a:IntArray; size:integer); var i,j,temp: integer; begin for i:=1 to size-1 do for j:=1 to size do if a[i]>a[j] then begin temp:=a[i]; a[i]:=a[j]; a[j]:=temp; end; end;
[edit] Perl
sub swap { @_[0, 1] = @_[1, 0]; } sub bubble_sort { for ($i=$[; $i < $#_; ++$i) { for ($j=$[; $j < $#_; ++$j) { ($_[$j] > $ _[$j+1]) and swap($_[$j], $_[$j+1]); } } }
[edit] PHP
function bubbleSort ($items) { $size = count($items); for ($i=0; $i<$size; $i++) { for ($j=0; $j<$size-1-$i; $j++) { if ($items[$j+1] < $items[$j]) { arraySwap($items, $j, $j+1); } } } return $items; } function arraySwap (&$arr, $index1, $index2) { list($arr[$index1], $arr[$index2]) = array($arr[$index2], $arr[$index1]); }
[edit] Python
def bubblesort(lst): "Sorts lst in place and returns it." for passesLeft in range(len(lst)-1, 0, -1): for index in range(passesLeft): if lst[index] > lst[index + 1]: lst[index], lst[index + 1] = lst[index + 1], lst[index] return lst
[edit] Ruby
module BubbleSort def self.sort(keys) sort!(keys.clone) end def self.sort!(keys) 0.upto(keys.size-1) do |i| (keys.size-1).downto(i+1) do |j| (keys[j], keys[j-1] = keys[j-1], keys[j]) if keys[j] < keys[j-1] end end keys end end
[edit] Scheme
(define (bubblesort l) (define (swap-pass l) (if (eq? (length l) 1) l (let ((fst (car l))(snd (cadr l))(rest (cddr l))) (if (> fst snd) (cons snd (swap-pass (cons fst rest))) (cons fst (swap-pass (cons snd rest))))))) (let for ((times (length l)) (val l)) (if (> times 1) (for (- times 1)(swap-pass val)) (swap-pass val))))
[edit] VBA
Private Sub bubble(N as integer, array() as integer) 'N is the number of integers in the array' '0 to N-1' Dim I, J, P, Temp as Integer For I = n - 1 To 0 Step -1 P=0 For J = 0 To I If array(J) > array(J + 1) Then Temp = array(J) array(J) = array(J + 1) array(J + 1) = Temp Else P=P+1 End If If P=I then GoTo premend Next J Next I 'premend = premature ending = all integers are allready sorted' premend: End Sub
see discussion for possible mistake
[edit] Visual Basic
Public Sub BubbleSort(ByRef ArrayAngka() As Long) Dim i, j As Integer Dim t As Long For i = ArrayAngka.GetUpperBound To 0 Step -1 For j = 0 To i - 1 If ArrayAngka(j) > ArrayAngka(j + 1) Then Call tukar(ArrayAngka(j), ArrayAngka(j + 1)) End If Next j Next i End Sub Private Sub tukar(ByRef data1 As Long, ByRef data2 As Long) Dim temp As Long temp = data1 data1 = data2 data2 = temp End Sub
[edit] MEL
global proc int[] SortList(int $list[])
{
int $i;
int $j;
int $temp;
int $flag;
int $n = `size($list)`;
for($i=$n-1; $i>0; $i--)
{
$flag = 1;
for($j=0; $i>$j; $j++)
{
if($list[$j]>$list[$j+1])
{
$flag = 0;
$temp = $list[$j];
$list[$j] = $list[$j+1];
$list[$j+1] = $temp;
}
}
if($flag) {
break;
}
}
return $list;
}
[edit] COBOL
If you are dealing with a large volume of data, use the COBOL SORT using sequential files. For sorting a WORKING STORAGE table, the following example assumes that the table is already loaded. The literals "a" indicates the size of the row, and "b" how many rows in the table.
WORKING-STORAGE SECTION.
*
01 WS-SORT-AREA.
05 WS-SORT-TABLE.
10 WS-SORT-ROW PIC X(a) OCCURS b.
05 WS-TEMP-ROW PIC X(a).
05 WS-ROW-MAX PIC S9(4) COMP VALUE b.
05 WS-SORT-MAX PIC S9(4) COMP.
05 WS-SORT-UP PIC S9(4) COMP.
05 WS-SORT-DOWN PIC S9(4) COMP.
05 WS-SORT-INCR PIC S9(4) COMP.
05 WS-SORT-TEST PIC S9(4) COMP.
*
PROCEDURE DIVISION.
*
MY-SORT SECTION.
MY-SORT-START.
*
* find the last entry
*
PERFORM VARYING WS-SORT-MAX FROM WS-ROW-MAX BY -1
UNTIL WS-SORT-MAX = ZERO
OR WS-SORT-ROW (WS-SORT-MAX) NOT = SPACES
END-PERFORM.
*
* bubble sort into required sequence
*
PERFORM VARYING WS-SORT-UP FROM WS-SORT-MAX BY -1
UNTIL WS-SORT-UP = ZERO
*
MOVE ZERO TO WS-SORT-TEST
*
PERFORM VARYING WS-SORT-DOWN FROM 1 BY 1
UNTIL WS-SORT-DOWN = WS-SORT-UP
*
ADD 1 TO WS-SORT-DOWN GIVING WS-SORT-INCR
*
IF WS-SORT-ROW (W30-SORT-DOWN)
> WS-SORT-ROW (W30-SORT-INCR)
*
MOVE WS-SORT-ROW (WS-SORT-DOWN)
TO WS-TEMP-ROW
MOVE WS-SORT-ROW (WS-SORT-INCR)
TO WS-SORT-ROW (WS-SORT-DOWN)
MOVE WS-TEMP-ROW
TO WS-SORT-ROW (WS-SORT-INCR)
ADD 1 TO WS-SORT-TEST
END-IF
END-PERFORM
*
IF WS-SORT-TEST = ZERO
NEXT SENTENCE
END-IF
END-PERFORM.
*
MY-SORT-EXIT.
EXIT.
