Quicksort and Quick Select

Quicksort

Selection

Partition Implementation

#define swap(x,y) temp=y;y=x;x=temp; //could get the addresses and swap without temp

//Partition the array range (left-right) and returns the partition index
int partition(int numbers[], int left, int right, int pivotIndex)
{
    int temp;
    int pivotValue = numbers[pivotIndex];
    swap(numbers[pivotIndex], numbers[right]); // Move pivot to end
    int storeIndex = left;

    for(int i = left; i < right; i++) // left <= i < right
    {
        if(numbers[i] <= pivotValue)
        {
            swap(numbers[i], numbers[storeIndex]);
        }
    }

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

Quick Sort Implementation

void quick_sort(int numbers[], int left ,int right)
{
    int ipivot;
    if(left<right)
    {
        ipivot= left + (right-left)/2;
        ipivot = partition(numbers, left, right, ipivot);
        quick_sort(numbers, left, ipivot-1); //left
        quick_sort(numbers, ipivot+1 ,right); //right
    }
}

Quick Select Implementation

//Returns kth smallest number -
//this also gives all numbers smaller than the kth number in the array
//That is the array has fist k smallest numbers - unsorted-
int quick_select(int numbers[], int left ,int right, int k)
{
    int ipivot;
    if(left<right)
    {
        ipivot= left + (right-left)/2;
        ipivot = partition(numbers, left, right, ipivot);
        if(ipivot == k)
        {
            return numbers[ipivot];
        }
        if(ipivot<k)
        {
            return quick_select(numbers, left, ipivot-1); //left
        }
        else
        {
                return quick_select(numbers, ipivot+1 ,right); //right
        }
    }
    else
    {
        return -1;
    }
}