Thread: please help to understand how recursion works in the following program or function.

  1. #1
    Registered User
    Join Date
    May 2015
    Posts
    2

    please help to understand how recursion works in the following program or function.

    Quicksort algorithm where it asks the user to enter 10 integers and it calls quicksort function to sort the array and print all the integers in sorted order.

    Code:
    #include<stdio.h>
    #define N 10
    
    
    void quicksort(int a[],int low , int high);
    int split(int a[], int low, int high);
    
    
    int main(void)
    {
    int a[N], i;
    
    
    printf("enter 10 no.:");
    
    
    for(i=0;i<N;i++)
    {scanf("%d", &a[i]);}
    
    
    quicksort(a, 0,N-1);
    
    
    printf("In sorted order:");
    for(i=0;i<N;i++)
    printf("%d  ", a[i]);
    
    
    printf("\n");
    return 0;
    
    
    
    
    }
    
    
    void quicksort(int a[], int low, int high)
    {
    int middle;
    
    
    if(low>=high)
    return;
    
    
    middle=split(a,low,high);
    
    
    quicksort(a,low,middle-1);
    quicksort(a,middle+1,high);
    }
    
    
    int split(int a[], int low, int high)
    {
        int part=a[low];
        for( ; ;)
        {
    
    
            while(low < high && part<=a[high])
            {
                high--;
            }
            if(low>=high)
                break;
            else
                a[low++]=a[high];
    
    
    
    
            while(low<high && a[low] <= part)
            {
                low++;
            }
            if(low>=high)
                break;
            a[high--]=a[low];
    
    
        }
        a[high]=part;
    return high;
    
    
    }
    please explain the steps in details regarding how recursion takes place in quicksort function. i m confused..sorry

    Code:
    void quicksort(int a[], int low, int high)
    {
    int middle;
    
    
    if(low>=high)
    return;
    
    
    middle=split(a,low,high);
    
    
    quicksort(a,low,middle-1);
    quicksort(a,middle+1,high);
    }

    thank you.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,383
    You can change the code to add print statements and run the code again.
    Code:
    void quicksort(int a[], int low, int high)
    {
    printf("DEBUG: Start sort between %d .. %d\n", low, high);
    int middle;
    
    
    if(low>=high)
    return;
    
    
    middle=split(a,low,high);
    
    
    quicksort(a,low,middle-1);
    quicksort(a,middle+1,high);
    printf("DEBUG: End sort between %d .. %d\n", low, high);
    }
    > printf("enter 10 no.:");
    Then call your function say 3 numbers to start with, rather than 10.
    Increase N slowly, until you understand the pattern that emerges.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    May 2015
    Posts
    2
    Okay,i will do accordingly.
    Thanks Salem.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursion and stack - trying to understand
    By bos1234 in forum C Programming
    Replies: 2
    Last Post: 09-01-2013, 01:58 AM
  2. Replies: 2
    Last Post: 04-08-2012, 10:32 AM
  3. don't understand an array in function program
    By ashlee in forum C Programming
    Replies: 3
    Last Post: 12-01-2010, 10:55 PM
  4. Replies: 4
    Last Post: 08-18-2009, 03:32 PM
  5. Replies: 14
    Last Post: 03-02-2008, 01:27 PM