-1

我是一所大学的一年级 CS 学生。我目前的任务是关于并发和快速排序算法。由于这是一项任务，我显然希望自己编写代码以更好地了解一切是如何工作的。因此，我要求您在回答时使用伪代码，而不是 java。

我的程序应该用三个参数在命令行启动；一个包含单词、输出文件名和一个数字的 in-file（它将告诉程序在对 in-file 进行排序时使用多少线程）。当我启动程序时，它应该使用快速排序算法和并发对文件中的单词进行排序。每个线程都被分配了文件中单词数组的一个部分（线程长度除以单词数）。当每个线程完成对其部分数组的排序后，程序会将线程返回的每个数组附加到一个长的、排序的单词数组中，并将它们写入输出文件。

我的问题是：我应该从哪里开始？在什么时候我应该在数组部分中选择一个枢轴元素？一旦我创建了这些部分，或者一旦在该部分上工作的线程开始？你能给我一个使用线程的快速排序算法的伪代码示例吗？

哇，问题太多了！提前致谢！:)

4

3 回答 3

2

这是德语： 

funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler-1)
         quicksort(teiler+1, rechts)
     ende
 ende

funktion teile(links, rechts)
 i := links 
 // Starte mit j links vom Pivotelement
 j := rechts - 1
 pivot := daten[rechts]

 wiederhole

     // Suche von links ein Element, welches größer als das Pivotelement ist
     wiederhole solange daten[i] ≤ pivot und i < rechts
         i := i + 1
     ende

     // Suche von rechts ein Element, welches kleiner als das Pivotelement ist
     wiederhole solange daten[j] ≥ pivot und j > links
          j := j - 1 
     ende

     falls i < j dann
         tausche daten[i] mit daten[j]
     ende

 solange i < j // solange i an j nicht vorbeigelaufen ist 

 // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])

 falls daten[i] > pivot dann
         tausche daten[i] mit daten[rechts]
 ende

 // gib die Position des Pivotelements zurück

 antworte i
 ende
于 2013-04-29T19:10:52.343 回答
2

我会创建多个线程来快速排序数据的相等部分。每个线程完成后，您可以合并排序结果以生成排序文件。

您将面临的主要挑战是读取和写入文件可能需要很长时间，以至于使用多个线程并没有明显加快。

Another approach is to use a pivot point to break the collection into two parts (possibly uneven) and have two threads sort each side. Repeat this until you have as many threads as cpus and then sort each portion single threaded. Again you have to be careful that this is more efficient than just use one thread.

于 2013-04-29T19:12:35.430 回答
1

This is the Wikipedia Quicksort Algorithm (pseudocode)

  function quicksort('array')
      if length('array') ≤ 1
          return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
-----------Partition section----------
      for each 'x' in 'array'
          if 'x' ≤ 'pivot' then append 'x' to 'less'
          else append 'x' to 'greater'
-----------End Partition section------
      return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

The Partition section cannot be done concurrently. However, you can execute the recursive calls with multiple threads, i.e.

return concatenate(quicksort('less'), 'pivot', quicksort('greater'))

Becomes

return concatenate(new Thread(quicksort('less')), 'pivot', new Thread(quicksort('greater')))
于 2013-04-29T19:12:55.117 回答