サーチ…
パラメーター
パラメータ | 説明 |
---|---|
安定 | はい |
所定の位置に | はい |
最良の複雑さ | に) |
平均ケース複雑度 | O(n ^ 2) |
最悪の場合の複雑さ | O(n ^ 2) |
空間の複雑さ | O(1) |
バブルソート
BubbleSort
は、順序付けられていないリスト内の各要素の連続したペアを比較し、要素が順序どおりでない場合はその要素を反転します。
次の例は、リスト{6,5,3,1,8,7,2,4}
のバブルソートを示しています(各ステップで比較されたペアは '**'でカプセル化されています)。
{6,5,3,1,8,7,2,4}
{**5,6**,3,1,8,7,2,4} -- 5 < 6 -> swap
{5,**3,6**,1,8,7,2,4} -- 3 < 6 -> swap
{5,3,**1,6**,8,7,2,4} -- 1 < 6 -> swap
{5,3,1,**6,8**,7,2,4} -- 8 > 6 -> no swap
{5,3,1,6,**7,8**,2,4} -- 7 < 8 -> swap
{5,3,1,6,7,**2,8**,4} -- 2 < 8 -> swap
{5,3,1,6,7,2,**4,8**} -- 4 < 8 -> swap
リストを1回反復した後、 {5,3,1,6,7,2,4,8}
ます。配列内の最大のソートされていない値(この場合は8)は常に最終位置に到達することに注意してください。したがって、リストがソートされていることを確認するためには、長さnのリストに対してn-1回繰り返す必要があります。
グラフィック:
Javascriptでの実装
function bubbleSort(a)
{
var swapped;
do {
swapped = false;
for (var i=0; i < a.length-1; i++) {
if (a[i] > a[i+1]) {
var temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
swapped = true;
}
}
} while (swapped);
}
var a = [3, 203, 34, 746, 200, 984, 198, 764, 9];
bubbleSort(a);
console.log(a); //logs [ 3, 9, 34, 198, 200, 203, 746, 764, 984 ]
C#での実装
バブルの並べ替えはSinking Sortとも呼ばれます。これはソートされるリストを繰り返しステップ実行し、隣り合ったアイテムの各ペアを比較し、間違った順序でスワップする単純なソートアルゴリズムです。
バブルソートの実装
バブルソートアルゴリズムを実装するためにC#言語を使用しました
public class BubbleSort
{
public static void SortBubble(int[] input)
{
for (var i = input.Length - 1; i >= 0; i--)
{
for (var j = input.Length - 1 - 1; j >= 0; j--)
{
if (input[j] <= input[j + 1]) continue;
var temp = input[j + 1];
input[j + 1] = input[j];
input[j] = temp;
}
}
}
public static int[] Main(int[] input)
{
SortBubble(input);
return input;
}
}
C&C ++での実装
C++
でのBubbleSort
実装例:
void bubbleSort(vector<int>numbers)
{
for(int i = numbers.size() - 1; i >= 0; i--) {
for(int j = 1; j <= i; j++) {
if(numbers[j-1] > numbers[j]) {
swap(numbers[j-1],numbers(j));
}
}
}
}
C実装
void bubble_sort(long list[], long n)
{
long c, d, t;
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if (list[d] > list[d+1])
{
/* Swapping */
t = list[d];
list[d] = list[d+1];
list[d+1] = t;
}
}
}
}
バブルのポインタによるソート
void pointer_bubble_sort(long * list, long n)
{
long c, d, t;
for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++)
{
if ( * (list + d ) > *(list+d+1))
{
/* Swapping */
t = * (list + d );
* (list + d ) = * (list + d + 1 );
* (list + d + 1) = t;
}
}
}
}
Javaでの実装
public class MyBubbleSort {
public static void bubble_srt(int array[]) {//main logic
int n = array.length;
int k;
for (int m = n; m >= 0; m--) {
for (int i = 0; i < n - 1; i++) {
k = i + 1;
if (array[i] > array[k]) {
swapNumbers(i, k, array);
}
}
printNumbers(array);
}
}
private static void swapNumbers(int i, int j, int[] array) {
int temp;
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static void printNumbers(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n");
}
public static void main(String[] args) {
int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
bubble_srt(input);
}
}
Pythonの実装
#!/usr/bin/python
input_list = [10,1,2,11]
for i in range(len(input_list)):
for j in range(i):
if int(input_list[j]) > int(input_list[j+1]):
input_list[j],input_list[j+1] = input_list[j+1],input_list[j]
print input_list
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow