Split Quick Sort a Multi-Threaded Sort
source link: https://www.codeproject.com/Tips/5328216/Split-Quick-Sort-a-Multi-Threaded-Sort
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Introduction
This is an example of a sort that is multi threaded. Sorting can cause delays for the user. Most sorts are single threaded, but most computers have multiple cores that could help with the sort and remove the slowdown. This sort is intended to provide an example of how a sort can be multi-threaded and also faster than the original it is based on.
Using the code
This code is primarly set up for timing and takes a vector or ints.
// Example of calling into the sort //loading the vector with numbers std::vector<int> arr; for(int i = 0; i < 10000; i++) { arr.push_back(temp); } // creating randomness in the vector std::random_shuffle( arr.begin(), arr.end()); //Calling the sort: splitQuick(arr);
Points of Interest
The statical part of this algorithm, the place were we pick the ideal
pivot is very short.
We simple create a list of Candidates, we then sort the list and then select the one that is in
the center to best aproximate what we think the complete list will be.
std::vector<int> arr; for(int i = 0; i < 10000; i++) { arr.push_back(temp); } int selection = 513; std::vector<int> candidates; for(int j = 0; j < selection, j++) { candidates.push_back( arr[ rand() % array.size() ); } std::sort (candidates.begin(), candidates.end()); int pivot = candidates[candidates.size()/2];
This algorithm lets the worker threads recruit additional threads. It allows the work the be properly divided quickly. The "magnitude" variable tells the thread how many more times it can split.
// total(int magnitude) { while (magnitude > 0) { //split the work name = name << 1; int tempName = name | 1; magnitude--; //start new thread total(magnitude, tempName); } //perform own work ] std::cout << name << std::endl; } void splitQuick() { total(3, 0); } int main() { splitQuick(); } /* output: 7 6 5 4 3 2 1 0 */
Result
This sort does have extra overhead and does consume extra processing power but gets the results faster by using the additional resources available.
History
5/24/2022 First Draft Complete.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK