0
\$\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\$
  • \$\begingroup\$ Minor: Consider a spell checker //Base condtion. --> condition \$\endgroup\$ – chux Nov 27 '18 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\$ – vnp Nov 28 '18 at 3:16
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\$
  • \$\begingroup\$ Good detection of quick_sort(a, 0, 0); failure. \$\endgroup\$ – chux Nov 27 '18 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\$ – Khushit Shah Nov 28 '18 at 1:42
  • \$\begingroup\$ in the last 231 condition I think there should be expected = {1,2,3}; \$\endgroup\$ – Khushit Shah Nov 28 '18 at 1:50
  • \$\begingroup\$ Thanks @KhushitShah - now rewritten to a simpler form where I can't make that mistake again. \$\endgroup\$ – Toby Speight Nov 28 '18 at 8:35
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\$
  • \$\begingroup\$ Thanks, I found out that if the input is in the sorted form either ascending or descending it. It doesn't work:-'(... \$\endgroup\$ – Khushit Shah Nov 28 '18 at 1:37
  • \$\begingroup\$ and now updated code if (pivot_ >= right_) solves problem. \$\endgroup\$ – Khushit Shah Nov 28 '18 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.