ソートアルゴリズム——バブルソート【コード実装】
79399 ワード
ぎじふごう
repeat
if itemCount <= 1
return
hasChanged := false
decrement itemCount
repeat with index from 1 to itemCount
if (item at index) > (item at (index + 1))
swap (item at index) with (item at (index + 1))
hasChanged := true
until hasChanged = false
ActionScript
public function bubbleSort(toSort:Array):Array
{
var changed:Boolean = false;
while (!changed)
{
changed = true;
for (var i:int = 0; i < toSort.length - 1; i++)
{
if (toSort[i] > toSort[i + 1])
{
var tmp:int = toSort[i];
toSort[i] = toSort[i + 1];
toSort[i + 1] = tmp;
changed = false;
}
}
}
return toSort;
}
bash
$ function bubble_sort() {
local a=("$@")
local n
local i
local j
local t
ft=(false true)
n=${#a[@]} # array length
i=n
while ${ft[$(( 0 < i ))]}
do
j=0
while ${ft[$(( j+1 < i ))]}
do
if ${ft[$(( a[j+1] < a[j] ))]}
then
t=${a[j+1]}
a[j+1]=${a[j]}
a[j]=$t
fi
t=$(( ++j ))
done
t=$(( --i ))
done
echo ${a[@]}
}
> > > > > > > > > > > > > > > > > > > > > > > > > $ # this line output from bash
$ bubble_sort 3 2 8
2 3 8
$ # create an array variable
$ a=(2 45 83 89 1 82 69 88 112 99 0 82 58 65 782 74 -31 104 4 2)
$ bubble_sort ${a[@]}
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
$ b=($( bubble_sort ${a[@]} ) )
$ echo ${#b[@]}
20
$ echo ${b[@]}
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
$
BASIC
適用:QuickBasic version 4.5
DO
changed = 0
FOR I = 1 TO size -1
IF nums(I) > nums(I + 1) THEN
tmp = nums(I)
nums(I) = nums(I + 1)
nums(I + 1) = tmp
changed = 1
END IF
NEXT
LOOP WHILE(NOT changed)
C
#include
" : " ");
bubble_sort(a, n);
for (i = 0; i < n; i++)
printf("%d%s", a[i], i == n - 1 ? "
" : " ");
return 0;
}
出力:
4 65 2 -31 0 99 2 83 782 1
-31 0 1 2 2 4 65 83 99 782
C++
#include
";
}
出力:
-199 -52 2 3 33 56 99 100 177 200
C#
using System;
using System.Collections.Generic;
namespace RosettaCode.BubbleSort
{
public static class BubbleSortMethods
{
//The "this" keyword before the method parameter identifies this as a C# extension
//method, which can be called using instance method syntax on any generic list,
//without having to modify the generic List code provided by the .NET framework.
public static void BubbleSort<T>(this List<T> list) where T : IComparable
{
bool madeChanges;
int itemCount = list.Count;
do
{
madeChanges = false;
itemCount--;
for (int i = 0; i < itemCount; i++)
{
if (list[i].CompareTo(list[i + 1]) > 0)
{
T temp = list[i + 1];
list[i + 1] = list[i];
list[i] = temp;
madeChanges = true;
}
}
} while (madeChanges);
}
}
//A short test program to demonstrate the BubbleSort. The compiler will change the
//call to testList.BubbleSort() into one to BubbleSortMethods.BubbleSort(testList).
class Program
{
static void Main()
{
List<int> testList = new List<int> { 3, 7, 3, 2, 1, -4, 10, 12, 4 };
testList.BubbleSort();
foreach (var t in testList) Console.Write(t + " ");
}
}
}
Dart
List bubbleSort(List list) {
var retList = new List.from(list);
var tmp;
var swapped = false;
do {
swapped = false;
for(var i = 1; i < retList.length; i++) {
if(retList[i - 1] > retList[i]) {
tmp = retList[i - 1];
retList[i - 1] = retList[i];
retList[i] = tmp;
swapped = true;
}
}
} while(swapped);
return retList;
}
Go
package main
import "fmt"
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
fmt.Println("unsorted:", list)
bubblesort(list)
fmt.Println("sorted! ", list)
}
func bubblesort(a []int) {
for itemCount := len(a) - 1; ; itemCount-- {
hasChanged := false
for index := 0; index < itemCount; index++ {
if a[index] > a[index+1] {
a[index], a[index+1] = a[index+1], a[index]
hasChanged = true
}
}
if hasChanged == false {
break
}
}
}
より一般的なバージョンでは、sortを実現することができます.Interfaceの任意の内容をソート
package main
import (
"sort"
"fmt"
)
func main() {
list := []int{31, 41, 59, 26, 53, 58, 97, 93, 23, 84}
fmt.Println("unsorted:", list)
bubblesort(sort.IntSlice(list))
fmt.Println("sorted! ", list)
}
func bubblesort(a sort.Interface) {
for itemCount := a.Len() - 1; ; itemCount-- {
hasChanged := false
for index := 0; index < itemCount; index++ {
if a.Less(index+1, index) {
a.Swap(index, index+1)
hasChanged = true
}
}
if !hasChanged {
break
}
}
}
Groovy
def makeSwap = { a, i, j = i+1 -> print "."; a[[i,j]] = a[[j,i]] }
def checkSwap = { a, i, j = i+1 -> [(a[i] > a[j])].find { it }.each { makeSwap(a, i, j) } }
def bubbleSort = { list ->
boolean swapped = true
while (swapped) { swapped = (1..テスト:
println bubbleSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4])
println bubbleSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])
出力:
[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]
[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]
Java
public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) {
boolean changed = false;
do {
changed = false;
for (int a = 0; a < comparable.length - 1; a++) {
if (comparable[a].compareTo(comparable[a + 1]) > 0) {
E tmp = comparable[a];
comparable[a] = comparable[a + 1];
comparable[a + 1] = tmp;
changed = true;
}
}
} while (changed);
}
JavaScript
Array.prototype.bubblesort = function() {
var done = false;
while (!done) {
done = true;
for (var i = 1; i<this.length; i++) {
if (this[i-1] > this[i]) {
done = false;
[this[i-1], this[i]] = [this[i], this[i-1]]
}
}
}
return this;
}
Julia
Julia version 0.6
function bubblesort!(arr::AbstractVector)
for _ in 2:length(arr), j in 1:length(arr)-1
if arr[j] > arr[j+1]
arr[j], arr[j+1] = arr[j+1], arr[j]
end
end
return arr
end
v = rand(-10:10, 10)
println("# unordered: $v
-> ordered: ", bubblesort!(v))
出力:
# unordered: [7, 4, -1, -8, 8, -1, 5, 6, -3, -5]
-> ordered: [-8, -5, -3, -1, -1, 4, 5, 6, 7, 8]
Kotlin
import java.util.Comparator
fun <T> bubbleSort(a: Array<T>, c: Comparator<T>) {
var changed: Boolean
do {
changed = false
for (i in 0..a.size - 2) {
if (c.compare(a[i], a[i + 1]) > 0) {
val tmp = a[i]
a[i] = a[i + 1]
a[i + 1] = tmp
changed = true
}
}
} while (changed)
}
MATLAB
function list = bubbleSort(list)
hasChanged = true;
itemCount = numel(list);
while(hasChanged)
hasChanged = false;
itemCount = itemCount - 1;
for index = (1:itemCount)
if(list(index) > list(index+1))
list([index index+1]) = list([index+1 index]); %swap
hasChanged = true;
end %if
end %for
end %while
end %bubbleSort
出力:
bubbleSort([5 3 8 4 9 7 6 2 1])
ans =
1 2 3 4 5 6 7 8 9
Objective-C
- (NSArray *) bubbleSort:(NSMutableArray *)unsorted {
BOOL done = false;
while (!done) {
done = true;
for (int i = 1; i < unsorted.count; i++) {
if ( [[unsorted objectAtIndex:i-1] integerValue] > [[unsorted objectAtIndex:i] integerValue] ) {
[unsorted exchangeObjectAtIndex:i withObjectAtIndex:i-1];
done = false;
}
}
}
return unsorted;
}
Perl
# Sorts an array in place
sub bubble_sort {
for my $i (0 .. $#_){
for my $j ($i + 1 .. $#_){
$_[$j] < $_[$i] and @_[$i, $j] = @_[$j, $i];
}
}
}
次の操作を行います.
my @a = (39, 25, 30, 28, 36, 72, 98, 25, 43, 38);
bubble_sort(@a);
Perl 6
sub bubble_sort (@a) {
for ^@a -> $i {
for $i ^..^ @a -> $j {
@a[$j] < @a[$i] and @a[$i, $j] = @a[$j, $i];
}
}
}
PHP
function bubbleSort(array &$array) {
$c = count($array) - 1;
do {
$swapped = false;
for ($i = 0; $i < $c; ++$i) {
if ($array[$i] > $array[$i + 1]) {
list($array[$i + 1], $array[$i]) =
array($array[$i], $array[$i + 1]);
$swapped = true;
}
}
} while ($swapped);
return $array;
}
PowerShell
function bubblesort ($a) {
$l = $a.Length
$hasChanged = $true
while ($hasChanged) {
$hasChanged = $false
$l--
for ($i = 0; $i -lt $l; $i++) {
if ($a[$i] -gt $a[$i+1]) {
$a[$i], $a[$i+1] = $a[$i+1], $a[$i]
$hasChanged = $true
}
}
}
}
Python
def bubble_sort(seq):
"""Inefficiently sort the mutable sequence (list) in place.
seq MUST BE A MUTABLE SEQUENCE.
As with list.sort() and random.shuffle this does NOT return
"""
changed = True
while changed:
changed = False
for i in xrange(len(seq) - 1):
if seq[i] > seq[i+1]:
seq[i], seq[i+1] = seq[i+1], seq[i]
changed = True
return seq
if __name__ == "__main__":
"""Sample usage and simple test suite"""
from random import shuffle
testset = range(100)
testcase = testset[:] # make a copy
shuffle(testcase)
assert testcase != testset # we've shuffled it
bubble_sort(testcase)
assert testcase == testset # we've unshuffled it back into a copy
R
bubblesort v[i+1] ) {
t Ruby
通常RubyでArrayを使用する.sort
class Array
def bubblesort1!
length.times do |j|
for i in 1...(length - j)
if self[i] < self[i - 1]
self[i], self[i - 1] = self[i - 1], self[i]
end
end
end
self
end
def bubblesort2!
each_index do |index|
(length - 1).downto( index ) do |i|
self[i-1], self[i] = self[i], self[i-1] if self[i-1] < self[i]
end
end
self
end
end
ary = [3, 78, 4, 23, 6, 8, 6]
ary.bubblesort1!
p ary
# => [3, 4, 6, 6, 8, 23, 78]
Rust
fn bubble_sort(values: &mut[T]) {
let mut n = values.len();
let mut swapped = true;
while swapped {
swapped = false;
for i in 1..n {
if values[i - 1] > values[i] {
values.swap(i - 1, i);
swapped = true;
}
}
n = n - 1;
}
}
fn main() {
// Sort numbers.
let mut numbers = [8, 7, 1, 2, 9, 3, 4, 5, 0, 6];
println!("Before: {:?}", numbers);
bubble_sort(&mut numbers);
println!("After: {:?}", numbers);
// Sort strings.
let mut strings = ["empty", "beach", "art", "car", "deal"];
println!("Before: {:?}", strings);
bubble_sort(&mut strings);
println!("After: {:?}", strings);
}
Scala
def bubbleSort[T](arr: Array[T])(implicit o: Ordering[T]) {
import o._
val consecutiveIndices = (arr.indices, arr.indices drop 1).zipped
var hasChanged = true
do {
hasChanged = false
consecutiveIndices foreach { (i1, i2) =>
if (arr(i1) > arr(i2)) {
hasChanged = true
val tmp = arr(i1)
arr(i1) = arr(i2)
arr(i2) = tmp
}
}
} while(hasChanged)
}
import scala.annotation.tailrec
def bubbleSort(xt: List[Int]) = {
@tailrec
def bubble(xs: List[Int], rest: List[Int], sorted: List[Int]): List[Int] = xs match {
case x :: Nil =>
if (rest.isEmpty) x :: sorted
else bubble(rest, Nil, x :: sorted)
case a :: b :: xs =>
if (a > b) bubble(a :: xs, b :: rest, sorted)
else bubble(b :: xs, a :: rest, sorted)
}
bubble(xt, Nil, Nil)
}
Swift
func bubbleSort<T:Comparable>(inout list:[T]) {
var done = false
while !done {
done = true
for i in 1..<list.count {
if list[i - 1] > list[i] {
(list[i], list[i - 1]) = (list[i - 1], list[i])
done = false
}
}
}
}
Visual Basic .NET
適用:Visual Basic.NET version 9.0+
Do Until NoMoreSwaps = True
NoMoreSwaps = True
For Counter = 1 To (NumberOfItems - 1)
If List(Counter) > List(Counter + 1) Then
NoMoreSwaps = False
Temp = List(Counter)
List(Counter) = List(Counter + 1)
List(Counter + 1) = Temp
End If
Next
NumberOfItems = NumberOfItems - 1
Loop
より多くのコード、お楽しみに!ネットワークから整理する.