配列の中でn番目に小さい要素をソートせずに見つけますか？

Question

ソート手法を使用せずにn番目に小さい要素を見つけるプログラムを作成したいと思います。

クイックソートのように再帰的に分割して征服できますか？

どうすればいいですか？

Answer 1

この問題に関する情報は、Selection algorithmにあります。

Answer 2

このように2つのスタックを使用して、1回のパスでN番目に小さい番号を見つけることができます。

• 空のスタックA及びスタックB
• PUSHとスタート
• スタックへの最初の数以降の次数、数がより少ない場合にのみスタックAにPUSHすることを選択しますトップ
• これらの手順
  • スタック-AのTOPは、新しい番号、スタック-AのPOPのTOPよりも大きくなっているものの を介して実行し、スタック-Bに押し込み、スタック-Aにプッシュする必要が
  • WhスタックAが空になるか、またはTOPが新しい番号よりも小さい場合は、新しい番号にPUSHを入力してStack-Bの内容を復元してください。
  • この時点で、新しい番号を正しい番号のソートされた場所に挿入しました。スタック-Aとスタック-Bは、スタックの深さは、今あなたが検索

---

の終わりに達しているされ、十分な場合は、私は一般的にNoldorins'最適化分析に同意再び

空です。
このスタックソリューションは、（2つのスタック全体で、より多くのデータを移動させることで）うまくいくような簡単なスキームに向かっています。ヒープ・スキームは、N番目に小さい番号のフェッチをツリー・トラバース（log m）に減らします。

ターゲットが最適な解決策である場合（最適化とそのデモンストレーションが重要な場合には、数多くの数値やプログラミング割り当ての場合など）、ヒープ技術を使用する必要があります。

スタックソリューションは、K要素の同じスペース（Kはデータセットのサイズ）内に2つのスタックを実装することで、スペース要件で圧縮できます。つまり、挿入するだけでスタックの動きが余分になります。

Answer 3

この作業では使用しておおよそO(n)時間（nは、リストの長さである）内に完了することはかなり可能であるheap structure（具体的には、Fibonacci heapに基づいpriority queue）O(1)挿入時間とO(log n)除去時間を与えます）。

リストからm番目に小さい要素を検索するタスクを考えてみましょう。単純にリストをループし、優先度キュー（サイズm）に各アイテムを追加するだけで、リスト内の各アイテムのキューをO(n)時間で効果的に作成することができます。これは非常に有益です）。キュー内で最も優先度の低い要素（最も優先度が最も小さい要素）を削除することは簡単です。合計はO(log m)になります。これで完了です。

ので、全体的な、アルゴリズムの時間計算量はO(n + log n)だろうが、log n << n以来（すなわちnがlog nよりもはるかに高速成長する）、これは単にO(n)に減少します。私はあなたが一般的なケースでこれよりもはるかに効率的な何かを得ることができるとは思わない。

Answer 4

あなたが言及しているのは、前述の選択アルゴリズムです。具体的には、quicksortへの参照は、あなたがpartition based selectionを考えていることを示唆しています。ここで

は、それがどのように動作するかです：あなたはあなたのリストをほぼ 途中だと思う何か：クイックソートで

• と同様に、あなたは良い ピボットを選ぶことから始めます。そして、あなたはピボット より すべての項目以下まで スワップ物事を前後の項目のあなたの全体のリストを経る リストの先頭にあり、あなたのピボット より大きい すべての物事は終わりです。あなたのピボットは真ん中の残りの部分に入ります。あなたはピボットの両側に を再帰的だろうが、 選択アルゴリズムのためにあなたが欲しい 場合は、。だから、に興味がある インデックスが含まれている側にのみ 再帰をよクイックソートで通常
• 3番目に小さい 値を見つけるには、 にインデックス2が含まれています（インデックス0は1番目に小さい値の であるため）。
• が領域を インデックスに絞り込んだときに再帰を停止できます。最終的には、 の「m-1」の最小の オブジェクトと、「n-m」の最大の オブジェクトのソートされていないリストが1つずつ表示されます。 "m"番目のオブジェクトは中間にあります。

このアルゴリズムは、最も高いm個の要素のソートされたリストを検索するのにも適しています... m番目の最大要素を選択し、その上のリストをソートするだけです。または、アルゴリズムが少し速い場合は、クイックソートアルゴリズムを実行しますが、ソートされた値を検索する領域と重複しない領域に再帰しないようにします。

これについての本当に素敵なことは、通常、O（n）時間で実行されることです。最初は、リスト全体が表示されます。最初の再帰では、それは約半分、次に四分の一などを見ます。したがって、約2n個の要素を調べるので、O（n）時間で実行されます。残念ながらクイックソートのように、一貫して悪いピボットを選ぶと、O（n ）時間で実行されます。

Answer 5

フィボナッチヒープを使用しない場合は、バイナリヒープを使用できます。

アルゴ：

1. この操作はO（N）時間がかかるアレイから分バイナリヒープをContruct。

2. これはminバイナリヒープなので、ルートの要素は最小値です。uはウルk番目の最小値を得るまで

3. だから、要素FRMのルートを削除するに保ちます。すべてのあなたは、ヒープKO（LOGN）操作を再保存し削除した後、O（1）操作

4. を確認してください。

だからここに時間を実行すると、O（klogn）+ O（n）は............そう、それはO（klogn）です...

Answer 6

Here is the Ans to find Kth smallest element from an array: 

#include<stdio.h> 
#include<conio.h> 
#include<iostream> 
using namespace std; 
int Nthmin=0,j=0,i; 
int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall); 
int main() 
{ 
    int size; 
    cout<<"Enter Size of array\n"; 
    cin>>size; 
    int *arr=(int*)malloc(sizeof(int)*size); 
    cout<<"\nEnter array elements\n"; 
    for(i=0;i<size;i++) 
     cin>>*(arr+i); 
    cout<<"\n"; 
    for(i=0;i<size;i++) 
     cout<<*(arr+i)<<" "; 
    cout<<"\n"; 
    int n=sizeof(arr)/sizeof(int); 
    int result=GetNthSmall(arr,size,3); 
    printf("Result = %d",result); 
    getch(); 
    return 0; 
} 

int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall) 
{ 
    int min=numbers[0]; 
    while(j<Nthsmall) 
    { 
     Nthmin=numbers[0]; 
     for(i=1;i<NoOfElements;i++) 
     { 
      if(j==0) 
      { 
       if(numbers[i]<min) 
       { 
        min=numbers[i]; 
       } 
       Nthmin=min; 
      } 
      else 
      { 
       if(numbers[i]<Nthmin && numbers[i]>min) 
        Nthmin=numbers[i]; 
      } 
     } 
     min=Nthmin; 
     j++; 
    } 
    return Nthmin; 
}