A QuickSort MT question...
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: A QuickSort MT question...

  1. #1
    Join Date
    Oct 2016
    Posts
    3

    A QuickSort MT question...

    I have a functioning quicksort algorithm, that I am trying to make multithreaded. I know how to divide the array into parts and have multiple threads sort their own section, but how would I go about sorting each part into the final sorted array? Here's my Quicksort functions that are single threaded at the moment.

    Code:
    template <typename Type> void qsort_impl(Type * left, Type * right, long (*CompareFunction)(const Type &, const Type &), void (*SwapFunction)(Type &, Type &))
    		{
    			Type * leftbound = left;
    			Type * rightbound = right;
    			Type pivot = left[(right - left) / 2];
    
    			for (;;)
    			{
    				while ((*CompareFunction)(*leftbound, pivot) < 0)
    				{
    					++leftbound;
    				}
    
    				while ((*CompareFunction)(*rightbound, pivot) > 0)
    				{
    					--rightbound;
    				}
    
    				while ((leftbound != rightbound) && ((*CompareFunction)(*leftbound, *rightbound) == 0))
    				{
    					++leftbound;
    				}
    
    				if (leftbound == rightbound)
    				{
    					break;
    				}
    
    				(*SwapFunction)(*leftbound, *rightbound);
    			}
    
    			if (left < --leftbound)
    			{
    				qsort_impl(left, leftbound, CompareFunction, SwapFunction);
    			}
    
    			if (right > ++rightbound)
    			{
    				qsort_impl(rightbound, right, CompareFunction, SwapFunction);
    			}
    		}
    
    		template <typename Type> void Quick_Sort(Type * pArray, unsigned long dwCount, long(*CompareFunction)(const Type &, const Type &),
    			(*SwapFunction)(Type &, Type &))
    		{
    			qsort_impl(pArray, pArray + dwCount - 1, CompareFunction, SwapFunction);
    		}

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,704

    Re: A QuickSort MT question...

    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

  3. #3

    Re: A QuickSort MT question...

    This is my naive approach:
    Code:
    int naive_quick_sort(std::vector<Type>::iterator begin, std::vector<Type>::iterator end) {
      auto const sz = end - begin;
      if (sz <= 1) return 0;
    
      auto pivot = begin + sz/2;
      auto const pivot_v = *pivot;
    
      std::swap(*pivot, *(end - 1));
      auto p = std::partition(begin, end, [&](const Type& a) { return a < pivot_v; } );
      std::swap(*p, *(end - 1));
    
      if (sz > 4096) {
        auto left = std::async(std::launch::async, [&]() {
          return naive_quick_sort(begin, p);
        });
        naive_quick_sort(p + 1, end);
      } else {
        naive_quick_sort(begin, p);
        naive_quick_sort(p + 1, end);
      }
      return 0;
    }
    
    void quick_sort(std::vector<Type>& arr) {
      naive_quick_sort(arr.begin(), arr.end());
    }

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,704

    Re: A QuickSort MT question...

    Does it work? What are the timings compared to a non MT version?
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)