Back to Study material
PPS

Unit - 4Arrays & Basic Algorithms Q1) What is an Array explain?A1)

An array is defined as the collection of similar type of data items stored at contiguous memory locations. Arrays are the derived data type in C programming language which can store the primitive type of data such as int, char, double, float, etc. It also has the capability to store the collection of derived data types, such as pointers, structure, etc. The array is the simplest data structure where each data element can be randomly accessed by using its index number.

C array is beneficial if you have to store similar elements. For example, if we want to store the marks of a student in 6 subjects, then we don't need to define different variables for the marks in the different subject. Instead of that, we can define an array which can store the marks in each subject at the contiguous memory locations.

By using the array, we can access the elements easily. Only a few lines of code are required to access the elements of the array.

Properties of Array

The array contains the following properties.

  • Each element of an array is of same data type and carries the same size, i.e., int = 4 bytes.
  • Elements of the array are stored at contiguous memory locations where the first element is stored at the smallest memory location.
  • Elements of the array can be randomly accessed since we can calculate the address of each element of the array with the given base address and the size of the data element.

Advantage of C Array

1) Code Optimization: Less code to the access the data.

2) Ease of traversing: By using the for loop, we can retrieve the elements of an array easily.

3) Ease of sorting: To sort the elements of the array, we need a few lines of code only.

4) Random Access: We can access any element randomly using the array.

Disadvantage of C Array

1) Fixed Size: Whatever size, we define at the time of declaration of the array, we can't exceed the limit. So, it doesn't grow the size dynamically like LinkedList which we will learn later.

Declaration of C Array

We can declare an array in the c language in the following way.

  1. data_type array_name[array_size];  

Now, let us see the example to declare the array.

  1. int marks[5];  

Here, int is the data_type, marks are the array_name, and 5 is the array_size.

Initialization of C Array

The simplest way to initialize an array is by using the index of each element. We can initialize each element of the array by using the index. Consider the following example.

  1. marks[0]=80;//initialization of array  
  2. marks[1]=60;  
  3. marks[2]=70;  
  4. marks[3]=85;  
  5. marks[4]=75;  

initialization of array in c language

 Q2) Program to print the largest and second largest element of the array.A2)
  1. #include<stdio.h>  
  2. void main ()  
  3. {  
  4.     int arr[100],i,n,largest,sec_largest;  
  5.     printf("Enter the size of the array?");  
  6.     scanf("%d",&n);  
  7.     printf("Enter the elements of the array?");  
  8.     for(i = 0; i<n; i++)  
  9.     {  
  10.         scanf("%d",&arr[i]);  
  11.     }  
  12.     largest = arr[0];  
  13.     sec_largest = arr[1];  
  14.     for(i=0;i<n;i++)  
  15.     {  
  16.         if(arr[i]>largest)  
  17.         {  
  18.             sec_largest = largest;  
  19.             largest = arr[i];  
  20.         }  
  21.         else if (arr[i]>sec_largest && arr[i]!=largest)  
  22.         {  
  23.             sec_largest=arr[i];  
  24.         }  
  25.     }  
  26.     printf("largest = %d, second largest = %d",largest,sec_largest);  
  27.       
  28. }  
 Q3) Explain Two Dimensional Arrays with examplesA3)

The two-dimensional array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns. However, 2D arrays are created to implement a relational database lookalike data structure. It provides ease of holding the bulk of data at once which can be passed to any number of functions wherever required.

Declaration of two dimensional Array in C

The syntax to declare the 2D array is given below.

  1. data_type array_name[rows][columns];  

Consider the following example.

  1. int twodimen[4][3];  

Here, 4 is the number of rows, and 3 is the number of columns.

Initialization of 2D Array in C

In the 1D array, we don't need to specify the size of the array if the declaration and initialization are being done simultaneously. However, this will not work with 2D arrays. We will have to define at least the second dimension of the array. The two-dimensional array can be declared and defined in the following way.

  1. int arr[4][3]={{1,2,3},{2,3,4},{3,4,5},{4,5,6}};  

Two-dimensional array example in C

  1. #include<stdio.h>  
  2. int main(){      
  3. int i=0,j=0;    
  4. int arr[4][3]={{1,2,3},{2,3,4},{3,4,5},{4,5,6}};     
  5. //traversing 2D array    
  6. for(i=0;i<4;i++){    
  7.  for(j=0;j<3;j++){    
  8.    printf("arr[%d] [%d] = %d \n",i,j,arr[i][j]);    
  9.  }//end of j    
  10. }//end of i    
  11. return 0;  
  12. }    

Output

arr[0][0] = 1

arr[0][1] = 2

arr[0][2] = 3

arr[1][0] = 2

arr[1][1] = 3

arr[1][2] = 4

arr[2][0] = 3

arr[2][1] = 4

arr[2][2] = 5

arr[3][0] = 4

arr[3][1] = 5

arr[3][2] = 6

C 2D array example: Storing elements in a matrix and printing it.

  1. #include <stdio.h>    
  2. void main ()    
  3. {    
  4.     int arr[3][3],i,j;     
  5.     for (i=0;i<3;i++)    
  6.     {    
  7.         for (j=0;j<3;j++)    
  8.         {    
  9.             printf("Enter a[%d][%d]: ",i,j);                
  10.             scanf("%d",&arr[i][j]);    
  11.         }    
  12.     }    
  13.     printf("\n printing the elements ....\n");     
  14.     for(i=0;i<3;i++)    
  15.     {    
  16.         printf("\n");    
  17.         for (j=0;j<3;j++)    
  18.         {    
  19.             printf("%d\t",arr[i][j]);    
  20.         }    
  21.     }    
  22. }    

Output

Enter a[0][0]: 56  

Enter a[0][1]: 10  

Enter a[0][2]: 30 

Enter a[1][0]: 34 

Enter a[1][1]: 21

Enter a[1][2]: 34   

 

Enter a[2][0]: 45

Enter a[2][1]: 56

Enter a[2][2]: 78  

 

 printing the elements ....

 

56      10      30 

34      21      34 

45       56      78

 Q4) Give an example Using StructureA4)

The structure is a user-defined data type that can contain a collection of items of different types. Now, we will create a program that returns an array by using structure.

  1. #include <stdio.h>  
  2. #include<malloc.h>  
  3. struct array  
  4. {  
  5.     int arr[8];  
  6. };  
  7. struct array getarray()  
  8. {  
  9.     struct array y;  
  10.     printf("Enter the elements in an array : ");  
  11.     for(int i=0;i<8;i++)  
  12.     {  
  13.         scanf("%d",&y.arr[i]);  
  14.     }  
  15.     return y;  
  16. }  
  17. int main()  
  18. {  
  19.   struct array x=getarray();  
  20.   printf("Elements that you have entered are :");  
  21.   for(int i=0;x.arr[i]!='\0';i++)  
  22.   {  
  23.       printf("%d ", x.arr[i]);  
  24.   }  
  25.     return 0;  
  26. }  

Output

Return an Array in C


 

 Q5) Explain character array and string in detailA5)

Strings are actually one-dimensional array of characters terminated by a null character '\0'. Thus a null-terminated string contains the characters that comprise the string followed by a null.

The following declaration and initialization create a string consisting of the word "Hello". To hold the null character at the end of the array, the size of the character array containing the string is one more than the number of characters in the word "Hello."

char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

If you follow the rule of array initialization then you can write the above statement as follows

char greeting[] = "Hello";

Following is the memory presentation of the above defined string in C/C++

String Presentation in C/C++

Actually, you do not place the null character at the end of a string constant. The C compiler automatically places the '\0' at the end of the string when it initializes the array. Let us try to print the above mentioned string

#include <stdio.h>

 

int main () {

 

   char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

   printf("Greeting message: %s\n", greeting );

   return 0;

}

When the above code is compiled and executed, it produces the following result

Greeting message: Hello

C supports a wide range of functions that manipulate null-terminated strings

Sr.No.

Function & Purpose

1

strcpy(s1, s2);

Copies string s2 into string s1.

2

strcat(s1, s2);

Concatenates string s2 onto the end of string s1.

3

strlen(s1);

Returns the length of string s1.

4

strcmp(s1, s2);

Returns 0 if s1 and s2 are the same; less than 0 if s1<s2; greater than 0 if s1>s2.

5

strchr(s1, ch);

Returns a pointer to the first occurrence of character ch in string s1.

6

strstr(s1, s2);

Returns a pointer to the first occurrence of string s2 in string s1.

The following example uses some of the above-mentioned functions

#include <stdio.h>

#include <string.h>

 

int main () {

 

   char str1[12] = "Hello";

   char str2[12] = "World";

   char str3[12];

   int  len ;

 

   /* copy str1 into str3 */

   strcpy(str3, str1);

   printf("strcpy( str3, str1) :  %s\n", str3 );

 

   /* concatenates str1 and str2 */

   strcat( str1, str2);

   printf("strcat( str1, str2):   %s\n", str1 );

 

   /* total lenghth of str1 after concatenation */

   len = strlen(str1);

   printf("strlen(str1) :  %d\n", len );

 

   return 0;

}

When the above code is compiled and executed, it produces the following result

strcpy( str3, str1) :  Hello

strcat( str1, str2):   HelloWorld

strlen(str1) :  10

 Q6) Why use structure?A6)

In C, there are cases where we need to store multiple attributes of an entity. It is not necessary that an entity has all the information of one type only. It can have different attributes of different data types. For example, an entity Student may have its name (string), roll number (int), marks (float). To store such type of information regarding an entity student, we have the following approaches:

  • Construct individual arrays for storing names, roll numbers, and marks.
  • Use a special data structure to store the collection of different data types.

Let's look at the first approach in detail.

  1. #include<stdio.h>  
  2. void main ()  
  3. {  
  4.   char names[2][10],dummy; // 2-dimensioanal character array names is used to store the names of the students   
  5.   int roll_numbers[2],i;  
  6.   float marks[2];  
  7.   for (i=0;i<3;i++)  
  8.   {  
  9.       
  10.     printf("Enter the name, roll number, and marks of the student %d",i+1);  
  11.     scanf("%s %d %f",&names[i],&roll_numbers[i],&marks[i]);  
  12.     scanf("%c",&dummy); // enter will be stored into dummy character at each iteration  
  13.   }  
  14.   printf("Printing the Student details ...\n");  
  15.   for (i=0;i<3;i++)  
  16.   {  
  17.     printf("%s %d %f\n",names[i],roll_numbers[i],marks[i]);  
  18.   }  
  19. }  

Output

Enter the name, roll number, and marks of the student 1Arun 90 91       

Enter the name, roll number, and marks of the student 2Varun 91 56     

Enter the name, roll number, and marks of the student 3Sham 89 69

 

Printing the Student details...

Arun 90 91.000000                                                                     

Varun 91 56.000000 

Sham 89 69.000000

The above program may fulfill our requirement of storing the information of an entity student. However, the program is very complex, and the complexity increase with the amount of the input. The elements of each of the array are stored contiguously, but all the arrays may not be stored contiguously in the memory. C provides you with an additional and simpler approach where you can use a special data structure, i.e., structure, in which, you can group all the information of different data type regarding an entity.

 Q7) What is Structure?A7)

Structure in c is a user-defined data type that enables us to store the collection of different data types. Each element of a structure is called a member. Structures ca; simulate the use of classes and templates as it can store various information

The ,struct keyword is used to define the structure. Let's see the syntax to define the structure in c.

  1. struct structure_name   
  2. {  
  3.     data_type member1;  
  4.     data_type member2;  
  5.     .  
  6.     .  
  7.     data_type memeberN;  
  8. };  

Let's see the example to define a structure for an entity employee in c.

  1. struct employee  
  2. {   int id;  
  3.     char name[20];  
  4.     float salary;  
  5. };  

The following image shows the memory allocation of the structure employee that is defined in the above example.

c structure memory allocation

Here, struct is the keyword; employee is the name of the structure; id, name, and salary are the members or fields of the structure. Let's understand it by the diagram given below:

Declaring structure variable

We can declare a variable for the structure so that we can access the member of the structure easily. There are two ways to declare structure variable:

  1. By struct keyword within main() function
  2. By declaring a variable at the time of defining the structure.

1st way:

Let's see the example to declare the structure variable by struct keyword. It should be declared within the main function.

  1. struct employee  
  2. {   int id;  
  3.     char name[50];  
  4.     float salary;  
  5. };  

Now write given code inside the main() function.

  1. struct employee e1, e2;  

The variables e1 and e2 can be used to access the values stored in the structure. Here, e1 and e2 can be treated in the same way as the objects in C++ and Java.

2nd way:

Let's see another way to declare variable at the time of defining the structure.

  1. struct employee  
  2. {   int id;  
  3.     char name[50];  
  4.     float salary;  
  5. }e1,e2;  
 Q8) Explain Bubble Sort with examplesA8)

In Bubble sort, Each element of the array is compared with its adjacent element. The algorithm processes the list in passes. A list with n elements requires n-1 passes for sorting. Consider an array A of n elements whose elements are to be sorted by using Bubble sort. The algorithm processes like following.

  1. In Pass 1, A[0] is compared with A[1], A[1] is compared with A[2], A[2] is compared with A[3] and so on. At the end of pass 1, the largest element of the list is placed at the highest index of the list.
  2. In Pass 2, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of Pass 2 the second largest element of the list is placed at the second highest index of the list.
  3. In pass n-1, A[0] is compared with A[1], A[1] is compared with A[2] and so on. At the end of this pass. The smallest element of the list is placed at the first index of the list.

Algorithm:

  • Step 1: Repeat Step 2 For i = 0 to N-1
  • Step 2: Repeat For J = i + 1 to N - I
  • Step 3: IF A[J] > A[i]
    SWAP A[J] and A[i]
    [END OF INNER LOOP]
    [END OF OUTER LOOP
  • Step 4: EXIT

Complexity

Scenario

Complexity

Space

O(1)

Worst case running time

O(n2)

Average case running time

O(n)

Best case running time

O(n2)

C Program

  1. #include<stdio.h>  
  2. void main ()  
  3. {  
  4.     int i, j,temp;   
  5.     int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};   
  6.     for(i = 0; i<10; i++)  
  7.     {  
  8.         for(j = i+1; j<10; j++)  
  9.         {  
  10.             if(a[j] > a[i])  
  11.             {  
  12.                 temp = a[i];  
  13.                 a[i] = a[j];  
  14.                 a[j] = temp;   
  15.             }   
  16.         }   
  17.     }   
  18.     printf("Printing Sorted Element List ...\n");  
  19.     for(i = 0; i<10; i++)  
  20.     {  
  21.         printf("%d\n",a[i]);  
  22.     }  
  23. }  

Output:

Printing Sorted Element List . . .

7

9

10

12

23

34

34

44

78

101

 Q9) Explain insertion sort with examplesA9)

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it is to be inserted there. Hence the name insertion sort.

Implementation in C

#include <stdio.h>

#include <stdbool.h>

 

#define MAX 7

 

int intArray[MAX] = {4,6,3,2,1,9,7};

 

void printline(int count) {

   int i;

 

   for(i = 0;i < count-1;i++) {

      printf("=");

   }

 

   printf("=\n");

}

 

void display() {

   int i;

   printf("[");

 

   // navigate through all items

   for(i = 0;i < MAX;i++) {

      printf("%d ",intArray[i]);

   }

 

   printf("]\n");

}

 

void insertionSort() {

 

   int valueToInsert;

   int holePosition;

   int i;

 

   // loop through all numbers

   for(i = 1; i < MAX; i++) {

 

      // select a value to be inserted.

      valueToInsert = intArray[i];

  

      // select the hole position where number is to be inserted

      holePosition = i;

  

      // check if previous no. is larger than value to be inserted

      while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) {

         intArray[holePosition] = intArray[holePosition-1];

         holePosition--;

         printf(" item moved : %d\n" , intArray[holePosition]);

      }

 

      if(holePosition != i) {

         printf(" item inserted : %d, at position : %d\n" , valueToInsert,holePosition);

         // insert the number at hole position

         intArray[holePosition] = valueToInsert;

      }

 

      printf("Iteration %d#:",i);

      display();

  

   } 

}

 

void main() {

   printf("Input Array: ");

   display();

   printline(50);

   insertionSort();

   printf("Output Array: ");

   display();

   printline(50);

}

If we compile and run the above program, it will produce the following result

Output

Input Array: [4 6 3 2 1 9 7 ]

==================================================

Iteration 1#:[4 6 3 2 1 9 7 ]

 item moved : 6

 item moved : 4

 item inserted : 3, at position : 0

Iteration 2#:[3 4 6 2 1 9 7 ]

 item moved : 6

 item moved : 4

 item moved : 3

 item inserted : 2, at position : 0

Iteration 3#:[2 3 4 6 1 9 7 ]

 item moved : 6

 item moved : 4

 item moved : 3

 item moved : 2

 item inserted : 1, at position : 0

Iteration 4#:[1 2 3 4 6 9 7 ]

Iteration 5#:[1 2 3 4 6 9 7 ]

 item moved : 9

 item inserted : 7, at position : 5

Iteration 6#:[1 2 3 4 6 7 9 ]

Output Array: [1 2 3 4 6 7 9 ]

Explain Selection Sort in detail with examples

In selection sort, the smallest value among the unsorted elements of the array is selected in every pass and inserted to its appropriate position into the array.

First, find the smallest element of the array and place it on the first position. Then, find the second smallest element of the array and place it on the second position. The process continues until we get the sorted array.

The array with n elements is sorted by using n-1 pass of selection sort algorithm.

  • In 1st pass, smallest element of the array is to be found along with its index pos. then, swap A[0] and A[pos]. Thus A[0] is sorted, we now have n -1 elements which are to be sorted.
  • In 2nd pas, position pos of the smallest element present in the sub-array A[n-1] is found. Then, swap, A[1] and A[pos]. Thus A[0] and A[1] are sorted, we now left with n-2 unsorted elements.
  • In n-1th pass, position pos of the smaller element between A[n-1] and A[n-2] is to be found. Then, swap, A[pos] and A[n-1].

Therefore, by following the above explained process, the elements A[0], A[1], A[2],...., A[n-1] are sorted.

Example

Consider the following array with 6 elements. Sort the elements of the array by using selection sort.

A = {10, 2, 3, 90, 43, 56}.

Pass

Pos

A[0]

A[1]

A[2]

A[3]

A[4]

A[5]

1

1

2

10

3

90

43

56

2

2

2

3

10

90

43

56

3

2

2

3

10

90

43

56

4

4

2

3

10

43

90

56

5

5

2

3

10

43

56

90

Sorted A = {2, 3, 10, 43, 56, 90}

Complexity

Complexity

Best Case

Average Case

Worst Case

Time

Ω(n)

θ(n2)

o(n2)

Space

 

 

o(1)

Algorithm

SELECTION SORT(ARR, N)

  • Step 1: Repeat Steps 2 and 3 for K = 1 to N-1
  • Step 2: CALL SMALLEST(ARR, K, N, POS)
  • Step 3: SWAP A[K] with ARR[POS]
    [END OF LOOP]
  • Step 4: EXIT

SMALLEST (ARR, K, N, POS)

  • Step 1: [INITIALIZE] SET SMALL = ARR[K]
  • Step 2: [INITIALIZE] SET POS = K
  • Step 3: Repeat for J = K+1 to N -1
    IF SMALL > ARR[J]
    SET SMALL = ARR[J]
    SET POS = J
    [END OF IF]
    [END OF LOOP]
  • Step 4: RETURN POS

C Program

  1. #include<stdio.h>  
  2. int smallest(int[],int,int);  
  3. void main ()  
  4. {  
  5.     int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
  6.     int i,j,k,pos,temp;  
  7.     for(i=0;i<10;i++)  
  8.     {  
  9.         pos = smallest(a,10,i);  
  10.         temp = a[i];  
  11.         a[i]=a[pos];  
  12.         a[pos] = temp;  
  13.     }  
  14.     printf("\nprinting sorted elements...\n");  
  15.     for(i=0;i<10;i++)  
  16.     {  
  17.         printf("%d\n",a[i]);  
  18.     }  
  19. }  
  20. int smallest(int a[], int n, int i)  
  21. {  
  22.     int small,pos,j;  
  23.     small = a[i];  
  24.     pos = i;  
  25.     for(j=i+1;j<10;j++)  
  26.     {  
  27.         if(a[j]<small)  
  28.         {  
  29.             small = a[j];  
  30.             pos=j;  
  31.         }  
  32.     }  
  33.     return pos;  
  34. }  

Output:

printing sorted elements...

7

9

10

12

23

23

34

44

78

101