1
\$\begingroup\$

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_);
}
\$\endgroup\$
2
  • \$\begingroup\$ Minor: Consider a spell checker //Base condtion. --> condition \$\endgroup\$ Commented Nov 27, 2018 at 19:43
  • \$\begingroup\$ I rolled back your edit. In this exchange you should not edit question after it has been answered, because it invalidates the answer. \$\endgroup\$ Commented Nov 28, 2018 at 3:16

2 Answers 2

Reset to default
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Good detection of quick_sort(a, 0, 0); failure. \$\endgroup\$ Commented Nov 27, 2018 at 19:42
  • \$\begingroup\$ 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... \$\endgroup\$ Commented Nov 28, 2018 at 1:42
  • \$\begingroup\$ in the last 231 condition I think there should be expected = {1,2,3}; \$\endgroup\$ Commented Nov 28, 2018 at 1:50
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks, I found out that if the input is in the sorted form either ascending or descending it. It doesn't work:-'(... \$\endgroup\$ Commented Nov 28, 2018 at 1:37
  • \$\begingroup\$ and now updated code if (pivot_ >= right_) solves problem. \$\endgroup\$ Commented Nov 28, 2018 at 1:48

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.