Design and analyses of algorithm

 Kth smallest element in an array:

 

Aim:

          Write a program to find the Kth smallest element in array(we need to find two minimum’s)

 

 

Program implementation:

I/p:                       

25

5

3

30

4

 

IF K=1, O/P=3

IF K=2, O/P=4

 

Ist pass:

min

25

5

3

30

4

 

Set 1^st element as min:

(Compare min to I ‘<‘ or not. If lesser interchange both)

 

Min                          i

25

5

3

30

4

 

I < min   (min=i)

Min                                                          I

5

25

3

30

4

 

Condition satisfied

 

Min                                                                                    I

3

25

5

30

4

 

CONDITION NOT SATISFIED

 

Min                           I

3

25

5

30

4

 

CONDITION NOT SATISFIED

 

IInd pass

 

       Min   I

3

25

5

30

4

═

 

Condition satisfied

        Min           I

3

5

25

30

4

 

Condition not satisfied

       Min                    I

3

5

25

30

4

 

CONDITION SATISFIED (MIN=I)

 

3

4

25

30

5

 

 

IIIrd pass:

                Min   I

3

4

25

30

5

▬▬▬

 

CONDITION NOT SATISFIED

                 Min          I

3

4

25

30

5

CONDITION SATISFIED

(MIN =I)

 

                 Min          I

3

4

5

30

25

 

IVth pass:

 

                        Min    I

3

4

5

30

25

▬▬▬▬▬▬

 

Condition satisfied

 

 

                         Min   I

3

4

5

25

30

▬▬▬▬▬▬▬▬

 

Algorithm:

 

Step 1: set the given no’s in sorted order

 

Step 2: set the first element as min

 

Step 3: compare min to next to next elements

 

Step 4: if it’s ‘<’ than min,swap the both elements through the temporary element

 

Step 5: Then i++ the array element.

 

Step 6: compare the other elements in this same order. Then we find the smallest element in an array.

 

Coding:

 

Void main()

{

Int a[15],temp,k,n,i,j,min;

 

Printf(“enter the no of elements”);

 

Scanf(“%d”,&n);

 

For(i=0;i<n;i++)

 

Printf(“enter the elements’);

 

Scanf(“%d”,&k);

 

For(i=0;i<k-1;i++)

{

Min=a[0];

 

For(j=i++;j<n;j++)

 

If(a[i]<min)

{

Min=a[j];

 

T=a[j];

 

A[i]=a[j];

 

A[i]=t;

Printf(“%d”,a[k-1];

}}

 

 

 

Queston 2: Find the Kth largest element in an array.

 

Aim: write a program to find the largest element in an array.

 

Program implementation:

                

       (Set 1^st element as ‘max’,&compare with next to next elements with condition ‘>’ or not if condition satisfied swap both element.)

 

  I/P:                      Max   I

50

40

60

2

45

 

                   O/P: IF K=1, 60

                           IF K=2, 50

Ist pass:

                             Max   I

50

40

60

2

45

 

(not satisfied)

                            Max            I

50

40

60

2

45

 

60>50,CONDITION SATISFIED. (MAX=I)

                        

                             Max                      I  

60

40

50

2

45

 

NOT SATISFIED

                            Max                               I

60

40

50

2

45

 

NOT SATISFIED

 

2^ND PASS:                    Max  I

60

40

50

2

45

   Satisfied.        ▬▬

 

              Max             i

60

50

40

2

45

 

Not satisfied

                                      Max                     i

60

50

40

2

45

Not satisfied.

 

3^rd pass:

 

                                              Max     i

60

50

40

2

45

  Not satisfied.   ▬▬▬▬▬

 

                                              Max           i

60

50

40

2

45

  Satisfied.

 

   4^th pass:

                                                         Max  i

60

50

45

2

40

Satisfied.            ▬▬▬▬▬▬▬

                                                          max

60

50

45

40

2

              ▬▬▬▬▬▬▬▬▬

 

 

Algorithm:

 

Step 1: set arrays first element as ‘max’.

 

Step 2: compare that element with ‘I th’ element.

 

Step 3: if I > max swap the both values through temporary element.

 

Step 4then compare other element,s with max if condition not satisfied i++ the array element

 

Step 5:after that all comparition the kth largest element will be found.

 

Coding:

  

Void main()

{

Int a[15],temp,k,n,i,j,max;

 

Printf(“enter the no of elements”);

 

Scanf(“%d”,&n);

 

For(i=0;i<n;i++)

 

Printf(“enter the elements’);

 

Scanf(“%d”,&k);

 

For(i=0;i<k-1;i++)

{

Max=a[0];

 

For(j=i++;j<n;j++)

 

If(a[i]>max)

{

Max=a[j];

 

T=a[j];

 

A[i]=a[j];

 

A[i]=t;

Printf(“%d”,a[k-1];

}}