7. Търсене, бързо сортиране

Търсене в несортирани и сортирани данни
// lsearch.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

int linear_search(vector<int> v, int a)
{
   int i;
   for (i = 0; i < v.size(); i++)
       if (v[i] == a) return i;
   return -1;
}

void print(vector<int> a)
{
   int i;
   for (i = 0; i < a.size(); i++)  cout << a[i] << " ";
   cout << "\n";
}

void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}

int rand_int(int a, int b)
{  return a + rand() % (b - a + 1);  }

int main()
{
   rand_seed();
   vector<int> v(20);
   int i;
   for (i = 0; i < v.size(); i++) v[i] = rand_int(1, 100);
   print(v);
   cout << "Enter number to search for: ";
   int n;
   cin >> n;
   int j = linear_search(v, n);
   cout << "Found in position " << j << "\n";
   return 0;
}

Двоично търсене
// bsearch.cpp
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;

int binary_search(vector<int> v, int from, int to, int a)
{
   if (from > to)  return -1;
   int mid = (from + to) / 2;
   int diff = v[mid] - a;
   if (diff == 0) return mid;          /* v[mid] == a */
   else if (diff < 0)                  /* v[mid] < a */
      return binary_search(v, mid + 1, to, a);
   else
      return binary_search(v, from, mid - 1, a);
}

void print(vector<int> a)
{
   int i;
   for (i = 0; i < a.size(); i++) cout << a[i] << " ";
   cout << "\n";
}

void rand_seed()
{
   int seed = static_cast<int>(time(0));
   srand(seed);
}

int rand_int(int a, int b)
{  return a + rand() % (b - a + 1);  }

int main()
{
   rand_seed();
   vector<int> v(20);
   int i;
   v[0] = 1;
   for (i = 1; i < v.size(); i++)
        v[i] = v[i - 1] + rand_int(1, 10);
   print(v);
   cout << "Enter number to search for: ";
   int n;
   cin >> n;
   int j = binary_search(v, 0, v.size() - 1, n);
   cout << "Found in position " << j << "\n";
   return 0;
}

Търсене и сортиране на реални данни
// esearch.cpp
#include <iostream>
#include <vector>
using namespace std;

#include "ccc_empl.cpp"

int binary_search(vector<Employee> v, int from, int to, string n)
{
   if (from > to) return -1;
   int mid = (from + to) / 2;
   if (v[mid].get_name() == n)  return mid;
   else if (v[mid].get_name() < n)
      return binary_search(v, mid + 1, to, n);
   else
      return binary_search(v, from, mid - 1, n);
}

int main()
{
   vector<Employee> staff(5);
   staff[0] = Employee("Cracker, Carl", 48000.0);
   staff[1] = Employee("Hacker, Harry", 35000.0);
   staff[2] = Employee("Lam, Larry", 78000.0);
   staff[3] = Employee("Reindeer, Rudolf", 63000.0);
   staff[4] = Employee("Sandman, Susan", 51500.0);

   cout << "Enter name of employee to search for: ";
   string name;
   getline(cin, name);

   int i = binary_search(staff, 0, staff.size() - 1, name);

   if (i >= 0)  cout << staff[i].get_name() << " "
                     << staff[i].get_salary() << "\n";
   else         cout << "Not found.\n";

   return 0;
}

Бързо сортиране
 Бързо сортиране
 А. Разделяне на дялове:
 1. Избираме случаен елемент x от масива a
 2. Преглеждаме масива отляво (от началото), докато достигнем до елемент >x
 3. Преглеждаме масива отдясно (от края), докато достигнем до елемент <x
 4. Разменяме местата на двата елемента
vector<int> a(n);
void partition(int x)
{
 int i=1, j=n;
 do
 {
  while (a[i] < x) i++;
  while (a[j] > x) j--;
  if (i<=j)
  { swap(a[i], a[j]);  i++; j--; }
 }
 while (i<=j);
}

Б. Сортиране - след като масивът се раздели, двата му дяла се подлагат на същата
обработка и това продължава, докато се получат дялове само с по един елемент.
void quicksort(int left, int right)
{
 int i=left, j=right;
 int x=a[(i + j)/2];
 do
 {
  while (a[i] < x) i++;
  while (a[j] > x) j--;
  if (i<=j)
  { swap(a[i], a[j]); i++; j--; }
 }
 while (i<=j);
 if (left<j) quicksort(left, j);
 if (i<right) quicksort(i, right);
}