Sorting algorithm refreshers........Quick Sort!

Another sorting algorithm post. This is probably the most famous one. Operating at O(n log n) it's considered very good and not crappy at all! I might make some more posts with other sorts like merge sort and radix sort, but I think I've reviewed sorting enough for now!

steps are the following:

1. Choose a pivot (I just pick the right most in array)
2. Parition the array such that all values less than pivot are to the left and all values greater than pivot are to the right of the array
3. Place the pivot in it's correct spot after partitioning
4. Recursively do the previous steps for each array partition

#include


int list[] = { 3, 4, 1, 10, 23, 40, 2, 9};
int arr_length = sizeof(list)/sizeof(list[0]);

int partition(int left, int right, int pivot);
void rec_quick_sort(int left, int right);


int main(void) {
    
    
    rec_quick_sort(0, 7);
    
    
    
    
    for( int i = 0; i < arr_length; ++i) {
        printf("%d ", list[i]);
    }
    
    printf("\n");
    
}


void rec_quick_sort(int left, int right) {
    
    if( right - left <= 0 ) {
        return;
    }
    
    int pivot = list[right];
    
    int partition_i = partition(left, right, pivot);
    rec_quick_sort(left, partition_i-1);
    rec_quick_sort(partition_i, right);
}

int partition(int left, int right, int pivot) {
    
    
    int left_p = left -1;
    int right_p = right;
    
    while(1) {
        
        
        //find bigger than pivot
        while(++left_p < right_p && list[left_p] < pivot);
        
        //find smaller than pivot
        while(--right_p > left_p && list[right_p] > pivot);
        
        
        if(left_p >= right_p) {
            break;
        
        }else {
            
            int temp = list[left_p];
            list[left_p] = list[right_p];
            list[right_p] = temp;
        }
        
        
    }
    
    int temp2 = list[left_p];
    list[left_p] = list[right];
    list[right] = temp2;
    
    return left_p;
    
    
    
}