median find algo



  • Hallo,

    ich habe einen median find algo implementiert. leider hat der algo noch einen kleinen fehler, den ich nicht finde...wo liegt das problem?

    #include <iostream> 
    #include <vector> 
    #include <algorithm> 
    #include <ctime> 
    using namespace std;
    
    int rand_pivot(vector<int> &vec, int left, int right) {
    	int pivot_index = left + rand() % (right - left);
    	int pivot = vec[pivot_index];
    	int store_index = left;
    
    	swap(pivot, vec[right]); // move pivot to the right
    
    	for(int i = left; i < right; i++) {
    		if (vec[i] < pivot) {
    			swap(vec[i], vec[store_index]);
    			store_index++;
    		}		
    	}
    
    	swap(vec[store_index], vec[right]);
    	return store_index;
    }
    
    int quick_select(vector<int> &vec, int left, int right, int k) {
    	if(left == right) {
    		return vec[left];
    	}
    
    	int pivot_index = rand_pivot(vec, left, right);
    	if (pivot_index == k) {
    		return vec[k];
    	} else if (pivot_index < k) {
    		return quick_select(vec, pivot_index + 1, right, k);
    	}
    	return quick_select(vec, left, pivot_index - 1, k);
    }
    
    int get_median(vector<int> &vec) {
    	return quick_select(vec, 0, vec.size() - 1, vec.size() / 2);	
    }
    
    int main() {	
    	srand(time(0));
    
    	vector<int> numbers = { 9, 2, 4, 3, 8, 5, 7, 6, 1 };
    	cout << get_median(numbers) << endl;
    
    	return 0;
    }
    


  • klitschko schrieb:

    wo liegt das Problem?



  • das ergebniss ist random...



  • Ergebnis...



  • klitschko schrieb:

    Ergebnis...

    Was erwartest Du denn, wenn Du einen Deiner Indizes zufällig auswählst?

    Nachdem Du einige Deiner Elemente eh vertauschst, kann Du Deinen vector doch gleich sortieren und den mittleren zurückgeben.

    mfg Martin



  • ich glaub du hast das konzept von quickselect nicht verstanden...
    quickselect laueft im average: O(n), in worst case: O(n log n)



  • meinte worst case: n^2



  • klitschko schrieb:

    ich glaub du hast das konzept von quickselect nicht verstanden...
    quickselect laueft im average: O(n), in worst case: O(n log n)

    mag sein.

    Ein Fehler ist aber sicherlich in Zeile 12:

    Du vertauscht pivo mit vec[right]

    Da Du aber den Wert von pivo nicht wieder zurückschreibst, ist der alte Wert von vec[right] nach dem Rücksprung verloren.

    Vielleicht habe ich auch deswegen aufgehört, mir über Deinen Algorithmus weiter Gedanken zu machen.

    mfg Martin



  • Was spricht gegen einen angepassten quicksort:

    int median( int *array, size_t numElems )
    {
    	size_t	mediaPos = numElems/2;
    	int		pivot = array[mediaPos];
    
    	size_t left = 0, right=numElems-1;
    
    	while( true )
    	{
    		while( left < mediaPos && array[left] <= pivot )
    			left++;
    
    		while( right > mediaPos && array[right] >= pivot )
    			right--;
    
    		if( left < mediaPos && right > mediaPos )
    			swap( array[left++], array[right--] );
    		else if( left < mediaPos )
    		{
    			pivot = array[left];
    			swap( array[left], array[mediaPos] );
    			right=numElems-1;
    		}
    		else if( right > mediaPos )
    		{
    			pivot = array[right];
    			swap( array[right], array[mediaPos] );
    			left = 0;
    		}
    		else
    			break;
    	}
    
    	return pivot;
    }
    

    mfg Martin



  • Ich schätze mal

    // swap(pivot, vec[right]); // move pivot to the right
     swap(vec[pivot_index], vec[right]); // move pivot to the right
    

    ps: Warum nicht einfach std::nth_element nehmen? Oder geht's dir um die Übung?


Anmelden zum Antworten