マージソートアルゴリズムに無限大を持つ目的 -- algorithm フィールド と sorting フィールド と mergesort フィールド 関連 問題

Purpose of having infinity in the merge sort algorithm












-6
vote

問題

日本語

行8& 9 ザマージソートアルゴリズムの

英語

What is the purpose of having ∞ on line 8 & 9 of the the merge sort algorithm?

</div
        
   
   

回答リスト

3
 
vote

それ以外の場合、アルゴリズムはアレイバインドの外側にインデックスを索引付けしようとするかもしれません。たとえば

です <事前> <コード> a = [1, 2, 3, 999999, 4, 5] b = [6, 7, 8, 9, 10, 11]

a のポインタが999999に達した後、<コード> b のポインタは範囲外になるまで増加し、プログラムクラッシュ

<事前> <コード> a = [1, 2, 3, 999999, 4, 5, ∞] b = [6, 7, 8, 9, 10, 11, ∞]

その動作を防ぎます

 

Because otherwise the algorithm might try to index outside of array bound. For example

a = [1, 2, 3, 999999, 4, 5] b = [6, 7, 8, 9, 10, 11] 

After pointer of a reaches 999999, the pointer of b will keep increase until it goes out of range and cause program crash

a = [1, 2, 3, 999999, 4, 5, ∞] b = [6, 7, 8, 9, 10, 11, ∞] 

will prevent that behavior

</div
 
 
0
 
vote

これらは sentinel要素と呼ばれます。彼らはあなたがアレイを越えて進むことは決してないこと、そしてそれがテストを節約することを保証します。

 

These are called a sentinel elements. They ensure that you will never progress past the arrays, and that spares a test.

</div
 
 

関連する質問

0  ArrayList <Card>を使用したMergeSort  ( Mergesort with arraylistcard ) 
<事前> <コード> import java.util.*; public class Dealer { public static void main(String[] args){ ArrayList<Card> cards = new Arr...

0  マージソートを使用した反転をカウントする - 予期しない結果  ( Counting inversions using merge sort unexpected result ) 
このコードは、小さい要素のセットに対して正しい結果を生み出しますが、大きな数の数(10万要素)に対して結果が正しくない理由はわかりません。たとえば、これは coursera の10万整数テキストファイル。私はすでに私のPythonコードから正しい結果を持ってい...

1  Python Heapqのマージソート出力ファイルに書き込めない  ( Python heapq merge sort not able to write to output file ) 
並べ替え整数で埋められた一時ファイルの束をマージして出力ファイルに書き込むことを試みています。関数内のジェネレータは値を返しています。 heapq.merge()は大丈夫です。プログラムは、TestWriteOutput.txtファイルに書き込まれていません。...

0  Cでポインタを使用したマージソートの書き方の問題  ( Issues writing merge sort with pointers in c ) 
この質問はスタックオーバーフローガイドラインを満たしていません。現在答えを受け付けていません。 この質問を改善したいですか? ...

1  マージソートアルゴリズムが正しく機能していません  ( Merge sort algorithm is not functioning properly ) 
マージソートアルゴリズムは、それがすると想定されているので機能しません。出力値は昇順で完全にソートされていません。いくつかの値は、バグを指している順序がありません。 <事前> <コード> #include <stdio.h> #include <stdlib....

-2  再帰を使ったMergeSort  ( Mergesort using recursion ) 
私は初心者で、再帰について学び、チュートリアルと古いQ&AMPを通って行ってみました。ここでスタックオーバーフローでは、より良いが理解することができないことができなかった。 次のMergesortスニペットを使用して再帰がどのように機能するかを私に啓発すること...

-1  メリージェール氏が働いていない[クローズ]  ( Mergesort not working ) 
この質問はスタックオーバーフローガイドラインを満たしていません。現在答えを受け付けていません。 この質問を改善したいですか? O...

0  Perlのマージソートの実装の問題は何ですか?  ( Whats wrong with my merge sort implementation in perl ) 
Perlでマージソートアルゴリズムを書き込もうとしていて、疑似Wikipedia 。からのコード だからこれは私が持っているものです: <事前> <コード> sub sort_by_date { my $self = shift; ...

1  原因不明のセグメンテーション断層をPthreads  ( Pthreads unexplained segmentation fault ) 
Cormenの有名なテキストから並列マージソートアルゴリズムを実装しました。私はPthreadsを使ってCでそれを書いて、Win7 x 64でMingWを編集しました(同じ結果を持つUbuntuで後でテストされた)。並列化における私の最初のアプローチはうれし...

2  リンクリストによるMergesortの複雑さ  ( Complexity of mergesort with linked list ) 
リンクされたリストを使用してMergesortのコードを持っています、それはうまく機能します、私の質問このアルゴリズムの複雑さとは何ですか?それはO(nlog(n))ですか?それは安定していますか? 、リンクリストを使用する方法についてはどうですか?他のものと...




© 2022 cndgn.com All Rights Reserved. Q&Aハウス 全著作権所有