Finding the Kth smallest element in an array using recursion

This is a discussion on Finding the Kth smallest element in an array using recursion within the C Programming forums, part of the General Programming Boards category; I am working on a problem that requires me to determine the Kth smallest element in an array using recursion. ...

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    2

    Finding the Kth smallest element in an array using recursion

    I am working on a problem that requires me to determine the Kth smallest element in an array using recursion. I've written 2 programs to do that, both are based on the partitioning of the array based on selecting a pivot element (elements less than on one side and greater than on the other side), but both seem to be giving wrong answers. I need help with the codes.......

    Program 1:
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 10
    int find(int ar[],int low,unsigned int high,int k);
    int length(int ar[]);
    int main()
    {
    int ar[MAX],k,ans;
    register int i=0;
    printf("\nPlease enter the numbers in the array");
    while(i<MAX){
    scanf("%d",&ar[i]);
    i++;
    }
    printf("\nPlease enter the value of k ");
    scanf("%d",&k);
    ans=find(ar,0,MAX-1,k);
    printf("\nThe %d smallest element in the array is %d",k,ans);
    return 0;
    }
    int find(int ar[],int low,unsigned int high,int k)
    {
    int mid;
    mid=(low+high)/2;
    unsigned int i,j;
    int p[MAX],q[MAX];
    for(i=0,j=0;i<length(ar);i++){
    if(ar[i]<ar[mid]){
    p[j]=ar[i];
    j++;
    }
    }
    for(i=0,j=0;i<length(ar);i++){
    if(ar[i]>ar[mid]){
    q[j]=ar[i];
    j++;
    }
    }
    if(length(p)>=k){
    find(p,0,length(p)-1,k);
    }
    else if(length(p)==k-1){
    return (ar[mid]);
    }
    else{
    find(q,0,length(q)-1,k-mid+1);
    }
    }
    int length(int ar[])
    {
    return(sizeof(ar)/4);
    }
    Program 2:
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 10
    int select(int ar[],int low, int high,int k);
    int partition(int ar[],int left,int high,int pivot);
    int main()
    {
    int ar[MAX],k,ans;
    register int i=0;
    printf("\nPlease enter the numbers in the array");
    while(i<MAX){
    scanf("%d",&ar[i]);
    i++;
    }
    printf("\nPlease enter the value of k ");
    scanf("%d",&k);
    ans=select(ar,0,MAX-1,k);
    printf("\nThe %d smallest element in the array is %d",k,ans);
    return 0;
    }
    int partition(int ar[],int low,int high,int pivot)
    {
    register int i;
    int storeindex,temp,pivotvalue;
    pivotvalue=ar[pivot];
    temp=ar[pivot];
    ar[pivot]=ar[high];
    ar[high]=temp;
    storeindex=low;
    for(i=low;i<(high-1);i++)
    {
    if(ar[i]<pivotvalue){
    temp=ar[storeindex];
    ar[storeindex]=ar[i];
    ar[i]=temp;
    storeindex++;
    }
    }
    temp=ar[high];
    ar[high]=ar[storeindex];
    ar[storeindex]=temp;
    return(storeindex);
    }
    int select(int ar[],int low,int high,int k)
    {
    int mid,newpivotindex;
    mid=(low+high)/2;
    newpivotindex=partition(ar,low,high,mid);
    if(k<newpivotindex){
    return select(ar,low,newpivotindex-1,k);
    }
    else if (k==newpivotindex){
    return (ar[k]);
    }
    else{
    return select(ar, newpivotindex+1, high, k-newpivotindex-1);
    }
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,762
    Indent style - Wikipedia, the free encyclopedia
    Pick an indent style other than "none"
    Nobody wants to look at code looking like that.
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    2
    Sorry for absence of indentation, i had written the code in notepad so there was no indentation. Here are the codes (with indentation).
    1.
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 10
    int find(int ar[],int low,unsigned int high,int k);
    int length(int ar[]);
    int main()
    {
        int ar[MAX],k,ans;
        register int i=0;
        printf("\nPlease enter the numbers in the array");
        while(i<MAX){
            scanf("%d",&ar[i]);
            i++;
            }
        printf("\nPlease enter the value of k ");
        scanf("%d",&k);
        ans=find(ar,0,MAX-1,k);
        printf("\nThe %d smallest element in the array is %d",k,ans);
        return 0;
    }
    int find(int ar[],int low,unsigned int high,int k)
    {
        int mid;
        mid=(low+high)/2;
        unsigned int i,j;
        int p[MAX],q[MAX];
        for(i=0,j=0;i<length(ar);i++){
            if(ar[i]<ar[mid]){
                p[j]=ar[i];
                j++;
                }
        }
        for(i=0,j=0;i<length(ar);i++){
            if(ar[i]>ar[mid]){
                q[j]=ar[i];
                j++;
                }
        }
        if(length(p)>=k){
            find(p,0,length(p)-1,k);
            }
        else if(length(p)==k-1){
            return (ar[mid]);
            }
        else{
            find(q,0,length(q)-1,k-mid+1);
            }
    }
    int length(int ar[])
    {
        return(sizeof(ar)/4);
    }
    2.
    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 10
    int select(int ar[],int low, int high,int k);
    int partition(int ar[],int left,int high,int pivot);
    int main()
    {
        int ar[MAX],k,ans;
        register int i=0;
        printf("\nPlease enter the numbers in the array");
        while(i<MAX){
            scanf("%d",&ar[i]);
            i++;
            }
        printf("\nPlease enter the value of k ");
        scanf("%d",&k);
        ans=select(ar,0,MAX-1,k);
        printf("\nThe %d smallest element in the array is %d",k,ans);
        return 0;
    }
    int partition(int ar[],int low,int high,int pivot)
    {
        register int i;
        int storeindex,temp,pivotvalue;
        pivotvalue=ar[pivot];
        temp=ar[pivot];
        ar[pivot]=ar[high];
        ar[high]=temp;
        storeindex=low;
        for(i=low;i<(high-1);i++)
        {
            if(ar[i]<pivotvalue){
                temp=ar[storeindex];
                ar[storeindex]=ar[i];
                ar[i]=temp;
                storeindex++;
                }
        }
        temp=ar[high];
        ar[high]=ar[storeindex];
        ar[storeindex]=temp;
        return(storeindex);
    }
    int select(int ar[],int low,int high,int k)
    {
        int mid,newpivotindex;
        mid=(low+high)/2;
        newpivotindex=partition(ar,low,high,mid);
        if(k<newpivotindex){
            return select(ar,low,newpivotindex-1,k);
            }
        else if (k==newpivotindex){
            return (ar[k]);
            }
        else{
            return select(ar, newpivotindex+1, high, k-newpivotindex-1);
            }
    }
    Last edited by Rohit_1989; 06-14-2009 at 08:59 AM.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    You know you can actually press the space bar in notepad and indent...
    Code:
    int length(int ar[])
    {
        return(sizeof(ar)/4);
    }
    You cannot get the size of an array passed to a function using the sizeof operator. All it's going to give you is the size of the pointer to the first element (and in this case, divide that by four).

    Also, you seem to be assuming that the values are entered in a sorted order.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    603
    Book recomendation that addresses this very matter..."Algorithms in C"

    Amazon.com: Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching (3rd Edition) (Pts. 1-4): Robert Sedgewick: Books


    Your code is a bit overwhelming to accomplish this task.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    That's a well-known sorting program called quicksort and in your case, once the array is sorted, you also need to print out the kth smallest element.

  7. #7
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Quote Originally Posted by itCbitC View Post
    That's a well-known sorting program called quicksort and in your case, once the array is sorted, you also need to print out the kth smallest element.
    Judging by the title & the post, probably not. There's an algorithm to select the K'th element of an unsorted array - it runs in O(n) time. Faster than a quicksort, but doesn't sort your array. (If you used it for sorting, you'd get O(n^2), so quicksort wins there.)
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  8. #8
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,049
    I was going by the description of the algorithm that the o/p provided, which closely mirrored quicksort.
    IMO too the o/p should use the algorithm that finds the kth smallest element w/o sorting to reduce runtime.

    Edit:: @Cactus_Hugger: can you post a link or some info on that algorithm.
    Last edited by itCbitC; 06-14-2009 at 02:04 PM.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by itCbitC View Post
    I was going by the description of the algorithm that the o/p provided, which closely mirrored quicksort.
    IMO too the o/p should use the algorithm that finds the kth smallest element w/o sorting to reduce runtime.

    Edit:: @Cactus_Hugger: can you post a link or some info on that algorithm.
    He is, that's what the select function he wrote does.

    I don't think Cactus_Hugger is correct about the running time of the algorithm though, if we're talking about "Hoare's selection algorithm". It is worse than O(n) worst case, like quicksort, when the partitions are often very unequal. That still means log n recursions on average and n-1 at worst. Introselect is better.

    Ah, here it is:
    Selection algorithm - Wikipedia, the free encyclopedia
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Modify an single passed array element
    By swgh in forum C Programming
    Replies: 3
    Last Post: 08-04-2007, 09:58 AM
  2. 2d array question
    By gmanUK in forum C Programming
    Replies: 2
    Last Post: 04-21-2006, 01:20 PM
  3. problems finding the average of an array column
    By mrgeoff in forum C Programming
    Replies: 4
    Last Post: 04-19-2005, 12:49 AM
  4. Finding greatest element of an array
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 12-10-2001, 04:30 PM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21