Quick Sort c program

Question

I recently learned quick sort through https://www.geeksforgeeks.org/quick-sort/ but found it hard to follow. So, from what I understand wrote the following program.

#include <stdio.h>
void quick_sort(int[],int,int);
int main(){
 int arr[100];
 int n;
 printf("Enter the elements :");
 scanf("%d",&n);
 for(int i = 0 ; i < n ; i++){
 printf("%d:",i+1);
 scanf("%d",&arr[i]);
 }
 int arr_size = sizeof(arr) / sizeof(arr[0]);
 for(int i = 0; i < n; i++){
 printf("%d ",arr[i]);
 }
 printf("\n");
 quick_sort(arr,0,n - 1);
 for(int i = 0; i < n; i++){
 printf("%d ",arr[i]);
 }
 printf("\n");
}
void quick_sort(int arr[],int pivot_, int right_){
 //Base condtion.
 if(pivot_ == right_ )//pivot = left = right == no more check
 return;
 int i ;
 int pivot, left ,right;
 pivot = pivot_;//first element...
 right = right_;//last element...
 left = pivot + 1; // second element.
 int middle;
 while( left <= right ){
 if(arr[left] >= arr[pivot]){
 if(arr[right] <= arr[pivot]){
 int temp = arr[left];
 arr[left] = arr[right];
 arr[right] = temp;
 right --;
 left ++;
 }else{
 right --; // left > pivot but right !< pivot
 }
 }else{
 left ++;// left is not > pivot.
 }
 }
 i = pivot + 1;
 while(arr[i] < arr[pivot]) i++;
 i--; // last smaller value than pivot encountered.
 middle = i; // swappppppp..
 int temp = arr[pivot];
 arr[pivot] = arr[i];
 arr[i] = temp;
 // now left of i is less than pivot and right of is greater than pivot. 
 quick_sort(arr,0,middle);
 quick_sort(arr,middle + 1,right_);
}

• chux: Minor: Consider a spell checker //Base condtion. --> condition
• vnp: I rolled back your edit. In this exchange you should not edit question after it has been answered, because it invalidates the answer.

Answer 1

This is the kind of function that benefits from unit tests. I wrote a few simple tests in C++ with GoogleTest:

extern "C" {
 void quick_sort(int arr[],int pivot_, int right_);
}
#include <gtest/gtest.h>
#include <algorithm>
#include <iterator>
#include <numeric>
TEST(quick_sort, empty)
{
 int a[1] = {};
 quick_sort(a, 0, 0-1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, one_element)
{
 int a[] = { 0 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, two_same)
{
 int a[] = { 0, 0 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, two_asc)
{
 int a[] = { 0, 1 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, two_desc)
{
 int a[] = { 1, 0 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, three_123)
{
 int a[] = { 1, 2, 3 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, three_231)
{
 int a[] = { 2, 3, 1 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, three_312)
{
 int a[] = { 3, 1, 2 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, four)
{
 int a[] = { 3, 1, 2, 0 };
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}
TEST(quick_sort, large)
{
 int a[100];
 std::iota(std::rbegin(a), std::rend(a), -50);
 quick_sort(a, 0, sizeof a / sizeof a[0] - 1);
 EXPECT_TRUE(std::is_sorted(std::begin(a), std::end(a)));
}

The first thing this highlighted was the unusual calling convention - right_ is an inclusive bound, but without any guidance, most C coders would expect an exclusive bound.

(In passing, I'll also point out that pivot_ isn't very meaningful to most callers - I think that left would be a better choice of name there.)

The second thing we see (diagnosed by running under Valgrind) is undefined behaviour when we run off the end of the array here:

 while(arr[i] < arr[pivot]) i++;

That needs to be fixed before this code is ready.

• chux: Good detection of quick_sort(a, 0, 0); failure.
• Khushit Shah: Thanks. for pointing out quick_sort(a, 0, 0); case. now I updated my question.problem was in BASE CONDITION if(pivot_ >= right_){/...} solves the problems...
• Khushit Shah: in the last 231 condition I think there should be expected = {1,2,3}

Answer 2

1) where is the 'compare' function? 2) The prototype for the quicksort() function is missing that parameter

the posted code, (at best) can only handle an array of integers. I.E. it will not handle an array of struct nor an array of strings, etc.

regarding: printf("Enter the elements :"); scanf("%d",&n); this fails to inform the user that the first number to be entered is actually the number of following numbers.

the code does not work!

Here is a typical run of the posted code:

Enter the elements :3
1:3
2:2
3:1
3 2 1 

Then the posted code maxes out a CPU and never gets done with the sorting.

• Khushit Shah: Thanks, I found out that if the input is in the sorted form either ascending or descending it. It doesn't work:-'(...
• Khushit Shah: and now updated code if (pivot_ >= right_) solves problem.