Intel® Software Network

You wrote:

An array of unsorted items is partitioned around a chosen splitter item. All items with keys less than the splitter item are stored to its left and all items with keys greater than the splitter are to its right.

Also:

The application will read an input text file for the set of integers to be sorted. The first line of the file will be the total number of integers (N) to be sorted; this is followed by N integers, one per line

Where is the splitter?

The first line of the file will be the total number of integers (N) to be sorted, the 2nd line of the file will be the splitter index;  this is followed by N integers, one per line...

Sorry, but your invitation to take part was sent 2 days before deadline, in the result we have very-very-very limited time to do this task. For a case, I append an example to my question:

1) the sequence 2,1,4,5, 12, 7, 8, 9 (where 5 is the splitter)  is compatible with your task, its partions 2,1,4,5 and 12, 7, 8, 9 may be sorted by 2 threads, and the sorted partions may be simply merged into output;

2) the sequence 12,1,4,5, 2, 7, 8, 9 is uncompatible with your task, this one should be sorted by only one thread.

as i understand the task, the splitter (pivot point) won't be provided in input file. The splitter can be calculated in function Partition (see source files attached to the task).
But, i'm not sure if we are allowed to write our version of finding the splitter...

mt2 -

I'm sorry that you did not get an earlier notice of this contest.  The site has been up since the beginning of the month and other notifications have been sent out and made available online. The good news is that there will be 11 more problems for you to enter.  Now that you know the URL for the contest site, be sure to check in at the start on the 1st of each month to find the new problem description and submit a solution by the 20th.

As for the splitter, in Quicksort any item from the data to be sorted can function as a splitter.  It is easy to pick the first item or the last or the item stored in the middle.  There is a whole body of research on how to best choose this splitter.  Once the splitter is chosen, the data is partitioned around that value.  Thus, you don't need to find the value that will create equal sized partitions, just one value from the data. Take a look at the Wikipedia article on Quicksort for more details.

In your examples, you've found the problem with quicksort and almost sorted lists.  The partitioning of the data usually lead to small or empty "halves" of unsorted data.  While the data is still compatible with the algorithm (and the concurrent version), it may not be all that efficient.  If you expect almost or nearly sorted data, there are better algorithms for sorting than quicksort.  This implies, though, that you know something about the data to be sorted ahead of time.

--clay

---

"It's all very complicated and would take a scientist to explain it." -- MST3K