© 2020 Neveles. All rights reserved.

void HibbardSort(int n, int* arr, int& counter)
{
  counter = 0;
  int k = (int)log2(n + 1);
  for (int step = pow(2, k) - 1; step > 0; step = pow(2, k) - 1)
  {
    for (int i = 0; i < step; ++i)
    {
      List<int> list;
      for (int curr = i; curr < n; curr += step)
      {
        counter += (list += arr[curr]);
      }
      List<int>::Elem* currElem = list.head_;
      for (int curr = i; curr < n; curr += step)
      {
        arr[curr] = currElem->getValue();
        currElem = currElem->getNext();
      }
    }
    k--;
  }
}

void SedgewickSort(int n, int* arr, int& counter)
{
  counter = 0;
  int k = 2 * (int)log2((n - 1) / 9);
  while (k >= 0)
  {
    int step;
    if (k % 2 == 0)
    {
      step = 9 * pow(2, k) - 9 * pow(2, k / 2) + 1;
    }
    else
    {
      step = 8 * pow(2, k) - 6 * pow(2, (k + 1) / 2) + 1;
    }
    for (int i = 0; i < step; ++i)
    {
      List<int> list;
      for (int curr = i; curr < n; curr += step)
      {
        counter += (list += arr[curr]);
      }
      List<int>::Elem* currElem = list.head_;
      for (int curr = i; curr < n; curr += step)
      {
        arr[curr] = currElem->getValue();
        currElem = currElem->getNext();
      }
    }
    k--;
  }
}

int binSearch(int* arr, int value, int begin, int end)
{
  if (begin == end)
  {
    if (value > arr[begin])
    {
      return begin + 1;
    }
    return begin;
  }

  int mid = (begin + end) / 2;
  if (arr[mid] > value)
  {
    return binSearch(arr, value, begin, mid);
  }
  else
  {
    return binSearch(arr, value, mid + 1, end);
  }

}

void binaryInsertSort(int n, int* arr, int& counter)
{
  counter = 0;
  for (int i = 1; i < n; ++i)
  {
    int position = binSearch(arr, arr[i], 0, i - 1);
    for (int j = i - 1; j >= position; --j)
    {
      ++counter;
      std::swap(arr[j], arr[j + 1]);
    }
    ++counter;
  }
}