Этот алгоритм сортировки уже существует?

Question

#include <iostream>
#include <vector>

using namespace std;

int main() {
  vector<int> arr;
  for (int i = 1; i <= 1000; i++)
    arr.push_back(rand() % 100000);

  //algorithm ----
  vector<int> sorted;
  sorted.push_back(arr[0]);
  for (int i = 1; i < arr.size(); ++i) {
    //case: element is smaller than the smallest sorted element
    if (arr[i] < sorted[0]) {
      sorted.insert(sorted.begin(), arr[i]);
      continue;
    }
    //case: element is inside the sorted elements, search where
    if (arr[i] < sorted[sorted.size() - 1]) {

      //linear search, really slow
      // for (int j = 0; j < sorted.size() - 1; ++j) {
      //     if (sorted[j] < arr[i] && arr[i] < sorted[j + 1]) {
      //         sorted.insert(sorted.begin() + j, arr[i]);
      //     }
      // }

      //binary search
      int low, mid, high;
      low = 0;
      high = sorted.size() - 2;
      while (low <= high) {
        mid = (low + high) / 2;
        if ( (sorted[mid] < arr[i] && arr[i] < sorted[mid + 1]) 
          || sorted[mid] == arr[i] 
          || sorted[mid + 1] == arr[i]) {
          sorted.insert(sorted.begin() + mid, arr[i]);
          break;
        }
        if (sorted[mid] < arr[i])
          low = mid + 1;
        else
          high = mid - 1;
      }
      if (low > high) {
        for (auto x : sorted)
          cout << x << " ";
        cout << "\nsomething broke!\n";
      }
    }
    //case: the element is larger than the largest sorted element
    //goes to the end
    else {
      sorted.push_back(arr[i]);
    }
  }
  //----

  for(auto x : sorted)
    cout << x << " ";
  cout << "\n";
  return 0;
}

На днях у меня появилась идея об алгоритме сортировки, реализующем бинарный поиск, вот код на c ++ 11.

Мой вопрос: кто-нибудь уже создал алгоритм, подобный этому, или это даже пригодный для использования алгоритм?

Я думаю, что это около O (n Log n), но я не знаю, какова сложность функций вставки и push_back.

Любая помощь приветствуется. ;)

Я также включил версию с линейным поиском, возможно, это немного проще для понимания, но очень медленно.

Answer 1

Ваш код довольно долго похож на это

if (arr.size() < 2)
  return arr;
for (auto i = std::next(arr.begin()); i != arr.end(); ++i) {
    std::rotate(std::upper_bound(arr.begin(), i, *i), i, i+1);
}

Выполнение сортировки вставки на месте, которая является O (N²).

Теперь давайте посмотрим на ваш вклад

if (arr.size() < 2)
  return arr;
for (auto i = std::next(arr.begin()); i != arr.end(); ++i) {
    if (*i < *arr.begin())
      std::rotate(arr.begin(), i, i+1);
    else 
      if (*i > *std::prev(i)) // already in the right spot
        continue;
    std::rotate(std::upper_bound(arr.begin(), i, *i), i, i+1);
}

Итак, стоит ли это того, что мы получаем стоимость std::upper_bound, которая равна log N, каждый раз, когда значения if верны, поэтому стоимость 2 if там, где это не так. Таким образом, в случайном порядке список случаев, когда if помогает нам, будет быстро уменьшаться, так как он будет равен 1 / n для каждого, в случае почти отсортированного списка или почти обратного отсортированного списка вы выиграете некоторые, но во всех остальных случаях это просто трата времени.

Answer 2

Я бы сказал, что это (возможно, заново изобретенная) версия типа вставки. Смотрите это:

Сортировка вставок в Википедии