Wyszukiwanie elementów w tablicy

Zadaniem projektu było utworzenie niemalejącego ciągu z pseudolosowych liczb oraz znalezienie podanej liczby q (też pseudolosowej) w danym ciągu, a następnie wypisanie indeksu, w którym ona się znajduje. Należało wyszukać tej liczby za pomocą dwóch sposobów: metody liniowej oraz metody binarnej.
Wskazane było także obliczenie w jakim czasie wykonywał się dany algorytm, a następnie porównanie zależności między czasem wykonania zadania a długością danych do przetworzenia.

Szukanie połówkowe z sortowaniem:

#include <iostream>
#include <windows.h>
#include <fstream>
#include <time.h>
#include <stdlib.h>

using namespace std;

void Sort(int tab[], int lewy, int prawy)
      {
      int i = lewy, j = prawy;
      int tmp;
      int srodek = tab[(lewy + prawy) / 2];

      while (i <= j) {
            while (tab[i] < srodek)
                  i++;
            while (tab[j] > srodek)
                  j--;
            if (i <= j) {
                  tmp = tab[i];
                  tab[i] = tab[j];
                  tab[j] = tmp;
                  i++;
                  j--;
            }
      };

      if (lewy < j)
            Sort(tab, lewy, j);
      if (i < prawy)
            Sort(tab, i, prawy);
}

int main()
{

 cout<<"Wpisz '1' aby rozpoczac test \n";
      int cos;
      cin>>cos;

      fstream plik;
      plik.open("plikbin.csv",ios::out);
      plik<<"ilosc danych;sredni czas"<<endl;
       srand(time(NULL));
      for (int n=100;n<=50000;n+=100)
      {
          int* tab=new int[n];

          for(int i=0; i<n; i++)
          {
              tab[i]=rand();
          }
 int l=0;
      int p=n-1;

      Sort(tab,l,p);

int iloscprob=2000;

      LARGE_INTEGER tps,end,start;
      unsigned __int64 czas=0;
      for(int i=0;i<=iloscprob;i++)
      {

          if( QueryPerformanceFrequency(&tps) )
          {
              QueryPerformanceCounter(&start);
              int szukana;
              szukana=rand();
              int lewa=0;
              int prawa=n-1;
              int centrum;
              while (1)
              {
                  if (lewa > prawa)
                  {
                     break;
                  }
                  centrum = (lewa+prawa)/2;
                  if (tab[centrum] == szukana)
                  {

                     break;
                     cout << "Indeks szukanej liczby:  " << tab[i];
                  }
                  else if (tab[centrum] < szukana)
                     lewa= centrum+1;
                  else
                      prawa = centrum-1;
              }
              QueryPerformanceCounter(&end);
              czas = ((end.QuadPart - start.QuadPart)*1000000000/tps.QuadPart) + czas;
          }
      }

      czas=czas/iloscprob;

      cout<<"ilosc danych w tablicy:  " <<n;
      plik<<n<<";"<<czas<<endl;
      cout<<"     sredni czas:  "<< czas<<" mikrosekund."<<endl;
      delete []tab;
      }
      plik.close();
      system("Pause");
}

Wyszukiwanie liniowe:

#include <iostream>
#include <windows.h>
#include <fstream>
#include <time.h>
#include <stdlib.h>

using namespace std;

int main()
{
      cout<<"Wpisz '1' by rozpoczac test: \n";
      int cos;
      cin>>cos;

      fstream plik;
      plik.open("pliksek.csv",ios::out);
      plik<<"ilosc danych;sredni czas"<<endl;




      for (int n=100;n<=50000;n+=200)
      {   srand(time(NULL));
          int* tab=new int[n];
          for(int i=0; i<n; i++)
          {
              tab[i]=rand();
          }


      int iloscProb=2000;

      LARGE_INTEGER tps,end,start;
      unsigned __int64 czas=0;

      for(int i=0;i<=iloscProb;i++)
      {
         if( QueryPerformanceFrequency(&tps) )
          {
              QueryPerformanceCounter(&start);
              int szukana;
              szukana=rand();



              for (int i=0;i<n;i++){
                  if  (szukana==tab[i]){

                        break;
                   cout << "Indeks szukanej liczby:  " << tab[i];
                     }
              }
                QueryPerformanceCounter(&end);
              czas = ((end.QuadPart - start.QuadPart)*1000000000/tps.QuadPart) + czas;
          }
      }

      cout<<"ilosc danych  "<<n;
      plik<<n<<";"<<czas<<endl;
      cout<<"     sredni czas: "<<czas<<" mikrosekund."<<endl;
      delete []tab;
      }
      plik.close();
      system("Pause");
}

w binarnym nie tworzy mi się wykres logarytmiczny.

1. Puść to dla większych zakresów danych
2. Jaki wykres ci wychodzi? ;]

cały czas liniowy. Testowałam to dla tablicy z milionem elementów..

ojjjjj no przepraszam, że w 4 posty mi poszło !! :O poprawiłam się ;>.. haha

Liniowy? Pics or it didn't happen ;] Ja bym powiedzial że czas będzie mniej więcej stały bo wszystko poleci do cache. Żeby takie coś miał sens to trzeba by puścić pewnie dla rozmiaru danych rzędu kilku MB przynajmniej. Ale nie trzeba robić raczej tylu prób, ze 100 powinno być wystarczające.
No i czemu nie używasz std::sort i std::binary_search? o_O

ale im więcej danych tym ten algorytm będzie się wykonywał dłużej

booo nie wiem jak .

Agaaaa napisał(a):

ale im więcej danych tym ten algorytm będzie się wykonywał dłużej

Jak cała tablica poleci do cache to tej różnicy w czasie wykonania algorytmu nawet nie zaważysz bo procesor wykonuje (przy założeniu że mamy wielopotokowość i superskalarność i 3Ghz) pewnie prawie 3 miliardy porównań na sekundę ;] a mamy przecież log2(n) porównań. Różnica jest widoczna tylko jeśli jest cache-miss i trzeba dane ciągnąć z pamięci, no ale to wymaga przynajmniej kilku Mb danych.

Agaaaa napisał(a):

booo nie wiem jak .

To doczytam.
http://www.cplusplus.com/reference/algorithm/binary_search/
http://www.cplusplus.com/reference/algorithm/sort/
Bo wcale nie trudno wywołać

std::sort(tablica,tablica+n);
std::binary_search(tablica,tablica+n);