quick.hxx

Go to the documentation of this file.

/*===========================================================================================================
 *
 * SHA - Simple Hybesis Algorithms
 *
 * Copyright (c) Michael Jeulin-Lagarrigue
 *
 *  Licensed under the MIT License, you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         https://github.com/michael-jeulinl/Simple-Hybesis-Algorithms/blob/master/LICENSE
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License is
 * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and limitations under the License.
 *
 * The above copyright notice and this permission notice shall be included in all copies or
 * substantial portions of the Software.
 *
 *=========================================================================================================*/
#ifndef MODULE_SORT_QUICK_HXX
#define MODULE_SORT_QUICK_HXX

#include <partition.hxx>

namespace SHA_Sort
{
  template <typename IT, typename Compare = std::less_equal<typename std::iterator_traits<IT>::value_type>>
  void QuickSort(const IT& begin, const IT& end)
  {
    const auto distance = static_cast<const int>(std::distance(begin, end));
    if (distance < 2)
      return;

    auto pivot = begin + (rand() % distance);                   // Pick Random Pivot € [begin, end]
    auto newPivot = Partition<IT, Compare>(begin, pivot, end);  // Proceed partition

    QuickSort<IT, Compare>(begin, newPivot);   // Recurse on first partition
    QuickSort<IT, Compare>(newPivot + 1, end); // Recurse on second partition
  }
}

#endif // MODULE_SORT_QUICK_HXX