問題タブ [insertion-sort]

申し訳ありませんが、これは簡単だと思いますが、疲れていて理解できません。

私は要素の配列を持っています、各要素は実際には粒子の現在の位置（int x、y、z）を含むデータ構造（cの構造体）である粒子です。要素自体だけでなく、要素のx位置を比較したいと思います。

ウィキペディアの擬似コードを見て、必要な属性を比較するためにそれを変更しようとしましたが、何か（おそらく単純な）間違ったことをしたと思います。

これが私が変更したものです：

誰かが私の間違いを指摘できれば、それは素晴らしいことです！

アダム

頻繁に挿入ソートされるリストがあります。挿入ソートがしなければならない作業を最小限に抑えるために、このリストに追加するのに適した位置 (最後以外) はありますか?

挿入ソートのさまざまな実装に関していくつか質問があります。

実装1：

実装2：

これが私の最初の質問です。最初のバージョンは2番目のバージョンよりも少し速いはずですが（割り当てが少ないため）、そうではありません（または少なくとも違いはごくわずかです）。しかし、なぜ？

次に、JavaのArrays.sort（）メソッドも2番目のアプローチを使用しているのではないかと思いました（おそらく、swapメソッドがさまざまな場所で使用されているため、コードが再利用されているためか、理解しやすいためです）。

実装3（binaryInsertionSort）：

バイナリ挿入は実用的なものですか、それとも理論的なものですか？小さなアレイでは、他のアプローチがはるかに高速であり、大きなアレイでは、mergesort/quicksortのパフォーマンスがはるかに優れています。

このコードでは、これはどのように機能しますか (Java):

これは、オンラインで受講しているバークレーCSクラスから取得し、独学しています。それは宿題ではありません（私はそれが幸運ではありませんでした）。私が理解していないのは次のとおりです。

A[] の数値が 8、2、10、5、4、12 であるとします。上記でそれらを使用すると、反復でこれを取得し、トレースします。

1. 最上部の添字は U、またはこの場合は 12、U-1 は 4、スワップは行われません
2. U は 4 (再帰 U-1) になり、その上の数字は 5 (もう 1 つの U-1) になります。彼らは交換されます。
3. 4 が上に移動したため、U は 4 になり、10 は U-1 で交換されます。

私のシーケンスは現在 8,2,4,10,5,12 です。

私の質問は、すでに通過した番号を取得するにはどうすればよいですか? たとえば、テストのためにその添え字に戻らない場合、どうすれば 5 つ上に移動できますか。

プログラムを正しくトレースしているとは思えず、再帰と混同されています。このため、スワップが正しく行われたと仮定してください。

ありがとうございました。

せ

初めて x86 アセンブリをいじっていますが、(挿入ソートを使用して) 配列をソートする方法がわかりません。アルゴリズムは理解していますが、主に Java と C++ を使用しているため、アセンブリは私を混乱させます。ここに私がこれまでに持っているすべてがあります

基本的に何もありません:(何かアイデアはありますか??事前に感謝します。

わかりました、これは私を完全なばかのように聞こえるようにするだけですが、_asm の配列の値を変更することさえできません

それをテストするために、私は入れました：

そして、これによりエラー C2415: 不適切なオペランド型が発生しました

だから私は試しました：

これは準拠しましたが、配列は変更されませんでした...

10,000 intのファイルからダブルリンクリスト（最高から最低）に挿入ソートを実装し、逆の順序でファイルに出力しました。

私の知る限り、私はそのようなプログラムを実装しましたが、出力ファイルで気づいたのですが、1つの番号が適切ではありません。他のすべての番号は正しい順序です。

場違いの番号は繰り返し番号ですが、この番号の他の繰り返しは正しい順序になっています。この番号が間違って配置されているのは奇妙なことです。また、ソートされていない番号は、同期していない6つの場所だけです。

私は何日もプログラムを調べてきましたが、問題がどこにあるのかわからないので、助けを求めます。

以下は問題のコードです、

（補足：私の質問は自分で削除できますか？むしろ私の大学は私のコードを盗むことはありませんが、そうでない場合はどうすれば削除できますか？）

お時間をいただきありがとうございます。

私は現在、主に楽しみのために、Java でさまざまな並べ替えアルゴリズムを実装して遊んでいますが、それを「正しく」実行する方法に苦労しています。つまり、s int、longs、Strings、booleans (実際には、これらは Java で比較可能ですか?)、独自のクラスなど、比較可能なものに対して選択した並べ替えアルゴリズムをユーザーが呼び出すことができるようにしたいと考えています。なんでもいい。問題は、これをどのように行うかです。

クラスを使用して並べ替えアルゴリズムを表すことを考えていたため、汎用リストなどを使用して並べ替え対象を内部に格納することを考えていました ( List<E>)。これにより、複数のコンストラクターを使用できるようになり、ユーザーがさまざまな形式 (リスト、配列など) でデータを渡すことができるようになります。これは正しい方法ですか？私の現在の問題は、ユーザーが何かをソートしたいときにクラスを作成する必要がないようにしたいということSystem.out.printlnです。

基本的な質問のように思えるかもしれませんが、プログラミング言語で自分のやり方を学んでいるだけです。夏の仕事のためにソフトウェア会社で働く 2 年生のコンピューティングの学生にとって、これは少しばかげていますが、私の仕事のほとんどにプログラミングの知識がほとんど必要ないことに驚かれることでしょう^...それは通常、より多くのデザインの知識です。

編集：

明確にするために、私の3つの主な質問は次のとおりです。

• ソートを行うクラスをユーザーに作成してもらうのと、ユーザーがインポートするクラスに静的メソッドを作成させるのとではどちらがよいでしょうか?
• プリミティブ データ型とジェネリック オブジェクトの両方を簡単に処理できますか? 同等の（または同様に）実装する汎用オブジェクトを処理できるようにしたいので、これによりプリミティブに問題が発生します（何も実装しないため;））。
• 一般的な入力を処理する最良の方法は何ですか?並べ替えを試みる前に何をチェックすればよいですか (たとえば、Comparable を実装するなど)?

MATLABで挿入ソートを書いています。私は次のように自分の関数を呼び出しました：

しかし、実行するとエラーが発生します

これが私の元のコードです：

私が間違っていることを知っている人はいますか？

次のような文字列の配列がある場合

挿入ソートを使用して、この配列をソートするにはどうすればよいですか？

ウィキペディアにはいくつかの例があります：https：//en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Insertion_sort#C.23

と

しかし、何か間違ったことをしていない限り、文字列の配列では機能しないようです。

私は走らないだろう

同じ100,000の乱数配列をすべてソートするさまざまなソート方法があります。

次の方法を使用して、それぞれのランタイムを見つけています

そして、乱数配列の場合は次のとおりです

これを変更して、それぞれが 1 つではなく 100 個の配列を並べ替え、各配列の時間をカウントできるようにするにはどうすればよいですか? 例えば。Run1 - 23ms; Run2 - 25ms; ... Run100 - 22ms

編集: 最後に 1 つのことがあります。したがって、各反復では、配列をいくつかの方法で並べ替えます。たとえば、挿入、マージ、およびクイック 並べ替えです。したがって、挿入 = 300 ミリ秒、マージ = 200 ミリ秒、クイック = 100 ミリ秒とします。反復ごとに、どのメソッドが最も速くソートされたかを見つける必要があります。

これは、下位のプログラミングクラスで何千回も行う単純な最小/最大タイプのことです。各値を配列にスローして、array.min 呼び出しを使用する方が簡単でしょうか? （それが実際に何であれ、Java構文には新しい..）