Szybkie wyszukiwanie k-tego największego elementu
Kod był wyświetlany 1362 razy.
    /*
  Name: Szybkie wyszukiwanie k-tego największego elementu
  Author: Magdalena Tukaj
  Description: Wykorzystanie do znalezienia k-tego największego elementu
  podziału zbioru na partycje
*/
#include <iostream>
#include <iomanip>
using namespace std;
// Funkcja dzieli podany zbiór na dwie partycje:
// ZL - elementy mniejsze od elementu zwrotnego
// ZP - elementy większe od elementu zwrotnego
// Zwraca pozycję elementu zwrotnego

int partycje(int *tab, int a, int b)
{
  int i,v,x;
  v=tab[a];
  i=a;
  b++;
  while(i<b)
  {
    while(tab[++i]<v) ;
    while(tab[--b]>v) ;
    if(i<b)
    {
      x=tab[i];
      tab[i]=tab[b];
      tab[b]=x;
    }
  }
  tab[a]=tab[b];
  tab[b]=v;
  return b;
}
int main()
{
  int n,max;
  int a,b,i;
  int k;
  int pv;//pozycja elementu zwrotnego

  do
  {
  cout<<"\n\n\t Podaj ile jest elementow w zbiorze: ";
  cin>>n;
  cout<<"\n\n\tPodaj liczbe maksymalna w zbiorze: ";
  cin>>max;
  if(n<=0||max<=0)
  cout<<"\n\n\tBledne dane";
  }
  while(n<=0||max<=0);

  int *tab=new int[n+1];//dolozenie do tablicy wartownika większego od n
  srand((unsigned)time(NULL));
  for(i=0;i<n;i++)
  tab[i]=rand()%max;
  tab[n]=max;//na końcu tab[] umieszczamy wartownika
  cout<<"\n\n";
  for(i=0;i<n;i++)//zbiór przed podziałem
  cout<<tab[i]<<"\t";

  do
  {
  cout<<"\n\n\t Podaj k: ";
  cin>>k;
  if(k>n||k<1)
  cout<<"\n\n\tBledne dane\n\n";
 }
  while(k>n||k<1);

  a=0;
  b=n-1;
  while(true)//szukanie k-tego elementu
  {
    pv=partycje(tab,a,b);
    if(pv==(n-k))
    break;
    else
    {if((n-k)<pv)
    b=pv-1;
    else
    a=pv+1;}
  }
  cout<<"\n\n\t Zbior po podziale: \n\n";
  for(i=0;i<n;i++)
  cout<<tab[i]<<"\t";
  cout<<"\n\n\t "<<k<<"-ty najwiekszy element to: "<<tab[n-k]<<" i znajduje sie on na pozycji "<<n-k+1;
  delete []tab;
  cin.ignore();
  getchar();
  return 0;
}
      
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT