Can someone explain me how i can change the following code to use the last element of my array as the pivot? In this code example i am using the first element as my pivot.

I found a couple of other codes but they are sorting the array in a different way which is not what i want.

In my attempts to change the pivot to use the last element i didn't get an errorcode but the sorting failed in the middle of my array. Any help is very much appreciated.

int partition(vector<int>& v,int low, int high){
    int pivot = v[low];
    int ui{low};
    int oi{high   1};
    
    while(true){

        while(v[  ui] < pivot){
            if(ui == high){
                break;
            }
        }
        
        while(pivot<v[--oi]){
            if(oi == low){
                break;
            }
        }
        
        if(ui >= oi){
            break;
        }
        swap(v[ui],v[oi]);
    }
    
    swap(v[low],v[oi]);
    
    return oi;
}

void quicksort(vector<int>& v, int low, int high){
    
    if(high>low){
        
        int pivot = partition(v,low,high);
        
        quicksort(v,low, pivot - 1);
        quicksort(v,pivot   1,high);
    }
}

CodePudding user response：

It does not matter where you choose your pivot. All that matters is that you chose one. You could even choose a random one each time.

Once your pivot is chosen, then you can start moving elements around, using the place where the pivot was as the initial unused, move-to spot when shuffling elements.

When you are done with the partitioning, your unused, move-to spot should be between the left and right sides. Stick the pivot value there, and return the index of that spot to the caller.

CodePudding user response：

To switch from using low as the pivot index to using high, you need to following changes:

int partition(vector<int>& v,int low, int high){
    // before:
    //int pivot = v[low];
    //int ui{low};
    //int oi{high   1};

    // after:
    int pivot = v[high];
    int ui{low - 1};
    int oi{high};

    while(true){

        while(v[  ui] < pivot){
            if(ui == high){
                break;
            }
        }
        
        while(pivot<v[--oi]){
            if(oi == low){
                break;
            }
        }
        
        if(ui >= oi){
            break;
        }
        swap(v[ui],v[oi]);
    }
    
    //before:
    //swap(v[low],v[oi]);
    
    //after:
    swap(v[high],v[oi]);
    
    return oi;
}