3. a) Kth Smallest

3. Find the K^th smallest element of the array.

Problem link :- click here

C code

//Kth Smallest element
#include<stdio.h>

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int A[], int start, int end)
{
    int pivot, i, j;

    pivot = A[end];
    i = start - 1;
    j = start;

    for(j=start; j<end; j++)
    {
        if(A[j] < pivot)
        {
            i++;
            swap(&A[i], &A[j]);
        }
    }
    i++;
    swap(&A[i], &A[end]);

    return i;
}

int kth_smallest(int A[], int start, int end, int k)
{
    int pos, length;

	if(start < end)
    {
    	pos = partition(A, start, end);
    	length = pos + 1;

    	if(k == length)
        	return A[pos];
    	if(k < length)
        	return kth_smallest(A, start, pos-1, k);
    	else
        	return kth_smallest(A, pos+1, end, k);
    }
}



void main()
{
    int arr1[30];
    int n;
    int i;
    int ans, k;

    printf("Enter the size of the array\n");
    scanf("%d",&n);
    printf("Enter the elements of the array\n");
    for(i=0; i<n; i++)
        scanf("%d",&arr1[i]);

    printf("Enter a integer less than %d\n",n);
    scanf("%d",&k);
    if(k>n)
    {
        printf("\n\nInvalid input\n");
        return;
    }

    printf("Given array\n");
    for(i=0; i<n; i++)
        printf("\t%d",arr1[i]);

    ans = kth_smallest(arr1, 0, n-1, k);
    printf("\n\n%d Smallest element in the array is %d\n\n", k, ans);
}

Java code

//kth smallest
package programs;

import java.util.*;

public class Array__3
{

	static int partition(int arr[], int start, int end)
	{
		int pivot, i, j, temp;
		pivot = arr[end];
		i = start-1;
		j = start;
		for(j=start; j<end; j++)
		{
			if(arr[j] < pivot)
			{
				i++;
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		i++;
		temp = arr[i];
		arr[i] = arr[end];
		arr[end] = temp;
		
		return i;
	}
	
	static int kth_smallest(int arr[], int start, int end, int k)
	{
		int pos;
		
		if(start < end)
		{
			pos = partition(arr, start, end);
			int length = pos + 1;
			if( k == length )
				return arr[pos];
			else if( k < length )
				return kthSmallest(arr, start, pos-1, k);
			else 
				return kthSmallest(arr, pos+1, end, k);
		}
	}
	
	public static void main(String[] args)
	{
		int array[] = new int[20];
		int n, i, k, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array :");
		n = s.nextInt();
		System.out.println("Enter the elements of the array :");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.println("Enter a integer less than " + n);
		k = s.nextInt();
		System.out.println("Given Array :");
		print_array(array, n);
		System.out.println("\n\n");
		
		ans = kth_smallest(array, 0, n-1, k);
		System.out.println(k + "th smallest element in the array is : " + ans);

	}
	
	static void print_array(int arr[], int n)
	{
		int i;
		for(i=0; i<n; i++)
			System.out.print(arr[i] + " ");
	} 
}

Time complexity = O(n)
            Because only one for loop is used.
Space complexity = O(1)
            Because space required for the variables used in functions does not depend on size of array(n).