Please help to understand the running time of the following algorithm
I have d already sorted arrays (every array have more than 1 element) with total n elements.
i want to have one sorted array of size n
if i am not mistaken insertion sort is running linearly on partially sorted arrays
if i will concatenate this d arrays into one n element array and sort it with insertion sort
isn't it a partially sorted array and running time of insertion sort on this array wont be O(n) ?
4 に答える
3
元の配列がいくつかの事前にソートされた配列の連結であっても、挿入ソートはO(n²)です。複数の並べ替えられた配列を 1 つの並べ替えられた配列に結合するには、おそらくmergesortを使用する必要があります。これにより、O(n·ln(d))パフォーマンスが得られます
于 2013-02-25T12:32:40.437 に答える
2
いいえ、これには2次の時間がかかります。挿入ソートは、各要素がソートされた配列内のポイントから最大で一定の距離d離れている場合にのみ線形になります。この場合、O（nd）時間がかかります。これは、部分的にソートされていることを意味します。その保証はありません。
サブアレイの数が小さな定数であることが保証されているという仮定の下でのみ、線形時間でこれを行うことができます。その場合、k -wayマージを使用できます。
于 2013-02-25T12:30:53.920 に答える
1
配列がソートされていることがわかっている場合、各配列をキューとして扱い、「ヘッド」をソートし、最小のヘッドを選択して新しい配列に入れ、選択した値をその配列から「ポップ」するだけです。 .
D が小さい場合、単純なバブル ソートがヘッドのソートに適しています。それ以外の場合は、1 つの要素のみを順序に配置する必要があるため、ある種の挿入ソートを使用する必要があります。
これは基本的に「マージソート」だと思います。ソートするリストが作業用ストレージを超える場合に非常に便利です。最初に小さなリストをスラッシングせずにソートしてから、ごくわずかな作業用ストレージを使用して結合できるためです。
于 2013-02-25T12:35:26.473 に答える
1
N の値が小さい場合、挿入ソートはかなり (比較的) 線形です。N が大きい場合、パフォーマンスは N^2 になる可能性が高くなります。
Nが十分に大きい場合、サブアレイがソートされているという事実はそれほど役に立たないと私は信じています。
Timsor t は部分的にソートされた配列の良い候補です
于 2013-02-25T12:30:07.930 に答える