クラシックソートアルゴリズム(バブルソートBubble Sort)注釈およびコード実装(c++、java)

バブルソート
1.概要:バブルソート(Bubble Sort)は簡単なソートアルゴリズムで、繰り返しの2つの要素を比較することによって、大きさの順序関係が正しくなければ、2つの要素の位置を交換し、要求に合致する要素はゆっくりと配列の先端または末端に「浮かぶ」ので、バブルソートと呼ばれている.
2.アルゴリズム思想:
       (1)隣接する2つの要素を比較し,サイズ関係が要求に合わない場合,2つの配列要素を交換する.
       (2)最初の1対の隣接要素から最後の対の隣接要素まで、2つの比較交換が完了すると最後の数が最大の要素になる.
       (3)最後の要素を除いて残りの要素について(1)、(2)配列全体が整列するまでステップを繰り返す.
3.概略:
/*配列要素を{1,3,5,2,7}*/とする.
配列の下付き:       0     1     2     3     4
循環変数1                                    i
ループ変数2         j    j+1
第1(1)回比較: 1     3     5     2     7   //なぜなら   (arr[j]  = 1)
ループ変数2                j     j+1
第1(2)回比較:1     3     5     2     7    //なぜなら   (arr[j]  = 3)
ループ変数2                       j     j+1
第1(3)回比較:    1     3     5     2     7   //なぜなら   (arr[j]  = 5)>(arr[j+1]=2)、交換
交換後のシーケンス:       1     3     2     5     7
ループ変数2                              j     j+1
第1(4)回比較:    1     3     2     5     7   //なぜなら   (arr[j]  = 5)
現在のシーケンス:          1     3     2     5     7
循環変数1                              i
ループ変数2          j     j+1
第2(1)回比較:    1     3     2     5     7    //なぜなら   (arr[j]  = 1)
ループ変数2                j     j+1
2回目の比較:    1     3     2     5     7   //なぜなら   (arr[j]  = 3)
交換後のシーケンス:       1     2     3     5     7
ループ変数2                       j      j+1
第2(3)回比較:    1     2     3     5     7   //なぜなら   (arr[j]  = 3)
(ここから配列は秩序化されていることがわかりますが、サイズを比較するプロセスは、  i > 0 すなわちi==1 の場合)
に至るまで  i > 0 すなわちi==1 交換が終了し、配列が整列します.
以上から分かるように、ループ変数2は常にループ変数1よりも小さい(すなわち、  j j+1を防止するために、常にiより小さい の配列が境界を越えてアクセスする)  ,当 j ループ変数が配列要素を1回遍歴した後、j に留まる  i - 1 位置、このときの  i  位置すなわちj+1 位置はすでに最大で、今回はi-1 次のサイクルを続行します.
4.コード
(1) c++ 版

#include 
using namespace std ;

void bubble_Sort( int arr[] , int len , int start , int last ){
    for ( int i = len - 1 ; i > start ; i -- ){          ///        ，                     
        for ( int j = 0 ; j < i ; j ++ ){                ///          
            if ( arr[j] > arr[j+1] ) swap( arr[j] , arr[j+1]) ;///      
        }
    }
    return ;
}

int main(){
    int arr[5] = { 1 , 3 , 5 , 2 , 7 } ;
    bubble_Sort( arr , 5 , 0 , 5 ) ;
    for ( int i = 0 ; i < 5 ; i ++ ){
        cout << arr[i] << " " ;
    }
    cout << endl ;
    return 0 ;
}

(2) java 版

import java.util.Scanner;


public class Main{
	/*      */
	public static void swap( int[] arr , int i , int j ){
		int temp = arr[i] ;
		arr[i] = arr[j] ;
		arr[j] = temp ;
		return ;
	}
	
	public static void bubble_Sort( int[] arr , int start , int last ) {
		for ( int i = arr.length - 1 ; i > start ; i -- ) {
			for ( int j = 0 ; j < i ; j ++ ) {
				if ( arr[j] > arr[j+1] ) swap( arr , j , j + 1 ) ;
			}
		}
		return ;
	}
	
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in) ;	
        int[] arr = {1,3,5,2,7} ;
       	bubble_Sort( arr , 0 , 5 ) ;
       	for ( int i = 0 ; i < arr.length ; i ++ ) {
       		System.out.print(arr[i]+" ") ;
        }
    }
}

5.アルゴリズムの時間複雑度の簡単な分析
最悪時間の複雑さ:   O(n^2)        -------->   配列は5  4  3  2  1 似たような状況が最悪の場合
最適時間の複雑さ:   O(n)            --------->   配列自体が整列している場合 のように  1  2  3  4  5 
平均時間の複雑さ:   O(n^2)
(不適切な点があれば、ご指摘ください)