泡の位置合わせ

定義＃テイギ＃

隣接する2つの要素のサイズ関係を比較することによって,必要に応じて繰り返し交換するアルゴリズム

説明:

ランダム配列の配列があり、配列を並べ替えたい場合に使用するアルゴリズムの1つです.
配列内の隣接する2つの要素の関係を比較し,交換のみを行うアルゴリズムは,下図のように分かりやすい.

[5,1,4,2,8]を昇順に並べ替える場合は、隣接する2つのパラメータの大きさを比較することができ、左の係数が右の係数より大きい場合は、順序を変更し、逆も同様である.
例えば、上図のように0番元素5と1番元素1を比較する場合、5は1より大きく、互いに交換すればよい.
次に、1号元素5と2号元素4とを比較する.
..
..
このように続けば、最終的には右端に最大の数字がリストされ、n-1回同じように繰り返すことができます.
動画で下記を確認できます.
단순 교환 정렬とも呼ばれ、個人的にはBubbleソートよりも直感的なネーミング法だと思います.

コード#コード#

ベースインプリメンテーションコード

上記の方法で泡配列を実現し、以下に示す.

1つ目の条件:i=0、j=0によって、アレイ内の最大数が最も右側に移動します.
その後、前の配列の条件を繰り返します.
上のコードで配列[6, 2, 9, 1, 5, 3]をBubbleソートすると...

逆順序

逆に、アレイの右から左に進み、アレイ内の最小の数字を左に移動させることもできます.
コードで以下のように実現する.

アルゴリズムの改良

改善#1

[2, 3, 4, 5, 1]という配列があることを想像してみてください.
上記逆シーケンスアルゴリズムを用いて昇順ソートを行うと、最初のpassでは[1, 2, 3, 4, 5]と同様にソートされ、そこでソートが終了する.
しかし,アルゴリズムはそのソートが終了したか否かを知らないため,コードが終了する前に交換可能か否かを判断するため効率が低下する.
これを改善するために、1つのpassで行われる交換回数を示す変数を指定し、その変数が0のpassで関数breakを直接譲ることができる.
これをコードとして実装し,以下に示す.

上記アルゴリズムに[2, 3, 4, 5, 1]を代入すると、
最初の交換過程では4回の交換が発生する(最後の要素1は最初の過程である).
2番目の交換中は交換が発生しないため、関数は終了します.

上記のアルゴリズムで考えると、
1番目のpassはexchng=4で、2番目のpassはexchng=0で、関数は終了します.

正しい!

改善#2

[1, 3, 9, 4, 7]という配列があることを想像してみてください.
逆順バブルアルゴリズムを使用して昇順に配列する場合.
最初のpassは[1, 3, 4, 9, 7]を生成する.
しかし、ここでは0から2番目の配列1、3、4が昇順名で配列されているので、ここをもう一度通ると効率的ではないかもしれません.
各passで、保存交換が完了したら、2つの任意の変数を作成し、次のpassで使用すればよい.
以下に整理する.

変数lastは、各パスが最後に交換された2つの要素のうち右側の要素a[j]のインデックスを格納する.
すなわち、交換毎に右側要素のインデックス値がlastに代入され、1パス完了時にlastの値がkに代入され、次の実行するパスのスキャン範囲がa[k]に制限される.
この場合、次のパスで最後に比較する2つの要素はa[k]とa[k+1]です.
配列[1, 3, 9, 4, 7]を上記コードに代入すると、
最初のpass形成の方向は以下の通りである.

for j in range(4, 0, -1):
  if a[3] > a[4] (x)           # j=4일 경우 if문 실행x
  if a[2] > a[3] (o)           # j=3일 경우 if문 실행o
                               # 이때 배열은 [1, 3, 4, 9, 7]로 변경이 되고 last=j=3
  if a[1] > a[2] (x)           # j=2일 경우 if문 실행x
  if a[0] > a[1] (x)           # j=1일 경우 if문 실행x
                               # 첫번째 pass가 끝났을 때 배열은 [1, 3, 4, 9, 7]이고 k=last=3의 값을 가진다.
                               # while 3<4이므로 for j in range(4,3,-1)이 실행되여 배열의 4번째 원소와 5번째 원소에 알고리즘이 실행된다 (배열의 1~3번째 원소 무시)

Take Away

第2の改善案は難しい。

バブルソートと変数exchngを用いた最初の改善案を完全に理解しており、ゼロからやり直せばできるはずです.
しかし、すでに完成した案を除いて、第2の改善案は理解しにくいようで、ずっとうろうろしていた.正直、私はまだよく理解していません.△何だかは分かっているが、感じないのか.
まず、Bubbleソートの基本概念を理解し、正しく使用するときは、改善策を逐次漸進的に適用します.

5分以内にバブルのソートを理解

次の動画を見るとすぐにBubbleソートがわかります!!

---

は
を参照
https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-4.php