quicksort parallelisieren

hi,

wie kann ich mein quicksort als parallelen algo implementieren?

int partition(vector<int> &vec, int left, int right) {
    int pivot_index = left + rand() % (right - left + 1);
    int pivot = vec[pivot_index];

    swap(vec[pivot_index], vec[right]);  // Move pivot to end
    int store_index = left;

    for(int i = left; i < right; i++) {
    	if(vec[i] <= pivot) {
            swap(vec[store_index], vec[i]);
            store_index++;
    	}
    }

    swap(vec[right], vec[store_index]);  // Move pivot to its final place
    return store_index;
}

void quicksort(int *a, int l, int r) {
    // If the list has 2 or more items
    // sort left part
    if(l < j) {
    	// Get lists of bigger and smaller items and final position of pivot
        int pivot_index = partition(a, left, right);

        // Recursively sort elements smaller than the pivot (assume pivotNewIndex - 1 does not underflow)
        quicksort(a, left, pivot_index - 1);
        // Recursively sort elements at least as big as the pivot (assume pivotNewIndex + 1 does not overflow)
        quicksort(a, pivot_index + 1, right);
    }
}

Nexus

Was wäre bei Divide-and-Conquer naheliegend?

man koennte folgende aufrufe parallelisieren?

// Recursively sort elements smaller than the pivot (assume pivotNewIndex - 1 does not underflow)
quicksort(a, left, pivot_index - 1);
// Recursively sort elements at least as big as the pivot (assume pivotNewIndex + 1 does not overflow)
quicksort(a, pivot_index + 1, right);

icarus2

mike1 schrieb:

man koennte folgende aufrufe parallelisieren?

// Recursively sort elements smaller than the pivot (assume pivotNewIndex - 1 does not underflow)
quicksort(a, left, pivot_index - 1);
// Recursively sort elements at least as big as the pivot (assume pivotNewIndex + 1 does not overflow)
quicksort(a, pivot_index + 1, right);

Jester

Dann wird aber der größte teil der arbeit immer noch nicht parallel gemacht. Eine echte parallele implementierung sollte auch das partitionieren parallelisieren. Wichtig ist auch, dass man seine prozessoren zumindest gemäß der paritionsgröße aufteilt. Sonst hat man irgendwann mit etwas pech irgendwann ganz viele prozessoren die fast nix machen und einen der ackern muss.

patrick246

Innerhalb der quicksort-Aufrufe wird die Liste ja nochmal partitioniert, deshalb ist das schon paralell. Die obere und untere Liste wird ja dann gleichzeitig partitioniert.

Jester

Ja, aber der erste partitionierungsschritt ist mit Abstand der größte. Du beschränkst damit effektiv den möglichen speedup.