Studijní materiály

/**
 * @file sequential_select.cpp
 * @brief PRL - Sequential Select
 * @author Kamil Dudka <xdudka00@stud.fit.vutbr.cz>
 * @date 2008-05-10
 */
 
#include <assert.h>
#include <iostream>
#include <vector>
 
using namespace std;
 
typedef int TItem;
typedef vector<TItem> TContainer;
typedef vector<TContainer> TContCont;
 
const size_t Q = 5;
 
// Simply sort container and return the k-th item
TItem dummy_select(TContainer cont, size_t k) {
  assert(cont.size() <= Q);
  sort(cont.begin(), cont.end());
  return cont[k];
}
 
// Sequential select
TItem seq_select(const TContainer &cont, size_t k) {
  const size_t size = cont.size();
  if (size <= Q)
    // Use simple variant
    return dummy_select(cont, k);
 
  // Divide container to Q containers
  const size_t n = size/Q + 1;
  TContCont sub(n);
  for(size_t i=0; i<size; i++)
    sub[i/Q].push_back(cont[i]);
 
  // Compute median of each small container (by calling self)
  TContainer M(n);
  for(size_t i=0; i<n; i++)
    M[i] = dummy_select(sub[i], sub[i].size()/2);
 
  // Compute median of medians (by calling self)
  const TItem m = seq_select(M, M.size()/2);
 
  // Divide items to containers L, E and G
  TContainer L, E, G;
  for(size_t i=0; i<size; i++) {
    const TItem s = cont[i];
    if (s<m)
      L.push_back(s);
    else if (s>m)
      G.push_back(s);
    else
      E.push_back(s);
  }
 
  if (L.size() > k)
    // Select from L
    return seq_select(L, k);
  else if (L.size() + E.size() > k)
    // Item found at this level
    return m;
  else
    // Select from G
    return seq_select(G, k-L.size()-E.size());
}
 
int main(int, char *[]) {
  TContainer cont;
  TItem i;
  cin >> i;
  while (cin) {
    cont.push_back(i);
    cin >> i;
  }
  cout << "--- Input size: " << cont.size() << endl;
  cout << ">>> Median: " << seq_select(cont, cont.size()/2) << endl;
 
  return 0;
}