An array is a collection of data items, all of the same type, accessed using a common name.

A one-dimensional array is like a list;  A two dimensional array is like a table;  The C language places no limits on the number of dimensions in an array, though specific implementations may.

Some texts refer to one-dimensional arrays as vectors, two-dimensional arrays as matrices, and use the general term arrays when the number of dimensions is unspecified or unimportant.

Declaring Arrays

Array variables are declared identically to variables of their data type, except that the variable name is followed by one pair of square [ ] brackets for each dimension of the array.

Uninitialized arrays must have the dimensions of their rows, columns, etc. listed within the square brackets.

Dimensions used when declaring arrays in C must be positive integral constants or constant expressions.

In C99, dimensions must still be positive integers, but variables can be used, so long as the variable has a positive value at the time the array is declared. ( Space is allocated only once, at the time the array is declared. The array does NOT change sizes later if the variable used to declare it changes. )

Examples:

        int i, j, intArray[ 10 ], number;

        float floatArray[ 1000 ];

        int tableArray[ 3 ][ 5 ];      /* 3 rows by 5 columns */

        const int NROWS = 100;      // ( Old code would use #define NROWS 100 )

        const int NCOLS = 200;      // ( Old code would use #define NCOLS 200 )

        float matrix[ NROWS ][ NCOLS ];

4.1.1 Array notation and representation

Array is defined as a collection of elements of same data type. Hence it is also called as homogeneous variable. Total number of elements in array defines size of array. Position of element in an array defines index or subscript of particular element. Array index always starts with zero. If the size of array is n then index ranges from 0 to n–1. There can be array of integer, floating point or character values. Character array is called as String.

Eg.1  A=      

                                          0                   1                 2               3              4

• This example illustrates integer array A of size 5.
• Array index ranges from 0 to 4.
• Elements of array are {10, 20, 40, 5, 25}.

4.1.2 Manipulating array elements

An element is accessed by indexing the array name. This is done by placing the index of the element within square brackets after the name of the array.

For example −

double salary = balance[9];

The above statement will take the 10th element from the array and assign the value to salary variable.

The following example Shows how to use all the three above mentioned concepts viz. declaration, assignment, and accessing arrays −

#include <stdio.h>

int main () {

   int n[ 10 ]; /* n is an array of 10 integers */

   int i,j;

   /* initialize elements of array n to 0 */        

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

      n[ i ] = i + 100; /* set element at location i to i + 100 */

   }

   /* output each array element's value */

   for (j = 0; j < 10; j++ ) {

      printf("Element[%d] = %d\n", j, n[j] );

   }

   return 0;

}

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

Element[0] = 100

Element[1] = 101

Element[2] = 102

Element[3] = 103

Element[4] = 104

Element[5] = 105

Element[6] = 106

Element[7] = 107

Element[8] = 108

Element[9] = 109

4.1.3 Using multi-dimensional arrays

1-D array has 1 row and multiple columns but multidimensional array has of multiple rows and multiple columns.

Two Dimensional array:

It is the simplest multidimensional array. They are also called as matrix.

Declaration:

data-type array_name[no.of rows][no. of columns];

Total no of elements= No.of rows * No. of Columns

Example 3: int a[2][3]

This example illustrates two dimensional array a of 2 rows and 3 columns.

   Col 0  Col 1  Col 2

Row 0

Row 1

  Fig.2: Index positions of elements of a[2][3]

Total no of elements: 2*3=6

Total no of bytes occupied: 6( total no.of elements )*2(Size of one element)=12

Initialization and Storage Representation:

In C, two dimensional arrays can be initialized in different number of ways. Specification of no. of columns in 2 dimensional array is mandatory while no of rows is optional.

int a[2][3]={{1,3,0},   // Elements of 1st row

      {-1,5,9}}; //  Elements of 2nd  row

                 OR

int a[][3]={{1,3,0},    // Elements of 1st row

      {-1,5,9}}; //  Elements of 2nd  row

                             OR

int a[2][3]={1,3,0,-1,5,9};

Fig. 3 gives general storage representation of 2 dimensional array     

      Col 0    Col 1                  Col n

 Row 0             

        Row 1

 -

        -

    Row m

  Fig.3 General Storage Representation of 2 dimensional array.

Eg 4.  int a[2][3]={1,3,0,-1,5,9}

           Row 0

                                Row 1

                Col 0      col1      col2

Accessing Two-Dimensional Array Elements:

An element in 2-dimensional array is accessed by using the subscripts i.e. row index and column index of the array. For example:

int val = A[1][2];

The above statement will access element from the 2nd row and third column of the array A i.e. element 9.

4.1.4 Character arrays and strings

If the size of array is n then index ranges from 0 to n-1. There can be array of integer, floating point or character values. Character array is called as String.

Eg.1  A=      

                0        1       2      3        4

• This example illustrates integer array A of size 5.
• Array index ranges from 0 to 4.
• Elements of array are {10, 20, 40, 5, 25}.

Arrays can be categorized in following types

1. One dimensional array
2. Multi Dimensional array

These are described below.

The abstract model of string is implemented by defining a character array data type and we need to include header file ‘string.h’, to hold all the relevant operations of string. The string header file enables user to view complete string and perform various operation on the string. E.g. we can call ‘strlen’ function to find length of string, ‘strcat’ to concatenate two string, ‘strcpy’ to copy one string to another, ‘strrev’ to reverse the string. The definitions of all these functions are stored in the header file ‘string.h’.  So string functions with the user provided data becomes the new data type in ‘C’.

Fig. 4.1 : String data type

To use the functions related to strings, user only need to include ‘string.h’ header file. All the definitions details of these functions are keep hidden from the user, user can directly use these function without knowing all the implementation details. This is known as abstraction or hiding.

String Manipulation in C Language

Strings are also called as the array of character.

• A special character usually known as null character (\0) is used to indicate the end of the string.
• To read and write the string in C program %s access specifier is required.
• C language provides several built in functions for the manipulation of the string
• To use the built in functions for string, user need to include string.h header file.
• Syntax for declaring string is

Char  string name[size of string];

 Char is the data type, user can give any name to the string by following all the rules of defining name of variable. Size of the string is the number of alphabet user  wants to store in string.

Example:

Following are the list of string manipulation function

4.1.5 Structure

A structure can be considered as a template used for defining a collection of variables under a single name. Structures help programmers to group elements of different data types into a single logical unit (Unlike arrays which permit a programmer to group only elements of same data type).

• Why Use Structures

•         Ordinary variables can hold one piece of information

•         arrays can hold a number of pieces of information of the same data type.

For example, suppose you want to store data about a book. You might want to store its name (a string), its price (a float) and number of pages in it (an int).

If data about say 3 such books is to be stored, then we can follow two approaches:

      Construct individual arrays, one for storing names, another for storing prices and still another for storing number of pages.

      Use a structure variable.

Suppose we want to create a employee database. Then, we can define a structure

called employee with three elements id, name and salary. The syntax of this structure is as

follows:

struct employee  

{   int id;  

    char name[50];  

    float salary;  

};

Note:

• Struct keyword is used to declare structure.
• Members of structure are enclosed within opening and closing braces.
• Usually structure type declaration appears at the top of the source code file, before any variables or functions are defined or maintained in separate header file.
• Declaration of Structure reserves no space.
• It is nothing but the “ Template / Map / Shape ” of the  structure .
• Memory is created , very first time when the variable is created / Instance is created.

• Structure variable declaration:

We can declare the variable of structure in two ways

1. Declare the structure inside main function
2. Declare the structure outside the main function.

1. Declare the structure inside main function

Following example show you, how structure variable is declared inside main function

struct employee  

{  

 int id;  

 char name[50];  

 float salary;  

};  

int main()

{

struct employee e1, e2; 

return 0;

}

In this example the variable of structure employee is created inside main function that e1 ,e2.

2. Declare the structure outside main function

Following example show you, how structure variable is declared outside the main function

struct employee  

{  

 int id;  

 char name[50];  

 float salary;  

}e1,e2;  

• Memory allocation for structure

Memory is allocated to the structure only when we create the variable of structure.

Consider following example

• Structure Initialization

1. When we declare a structure, memory is not allocated for un-initialized variable.

2. Let us discuss very familiar example of structure student , we can initialize structure variable

in different ways –

Way 1 : Declare and Initialize

struct student

{

char name[20];

int roll;

float marks;

}std1 = { "Poonam",89,78.3 };

In the above code snippet, we have seen that structure is declared and as soon as after declaration we

have initialized the structure variable.

std1 = { "Poonam",89,78.3 }

This is the code for initializing structure variable in C programming

Way 2 : Declaring and Initializing Multiple Variables

struct student

{

char name[20];

int roll;

float marks;

}

std1 = {"Poonam" ,67, 78.3};

std2 = {"Vishal",62, 71.3};

In this example, we have declared two structure variables in above code. After declaration of variable we have initialized two variable.

std1 = {"Poonam" ,67, 78.3};

std2 = {"Vishal",62, 71.3};

Way 3 : Initializing Single member

struct student

{

int mark1;

int mark2;

int mark3;

} sub1={67};

Though there are three members of structure,only one is initialized , Then remaining two members

are initialized with Zero. If there are variables of other data type then their initial values will be –

Data Type Default value if not initialized

integer 0

float 0.00

char NULL

Way 4 : Initializing inside main

struct student

{

int mark1;

int mark2;

int mark3;

};

void main()

{

struct student s1 = {89,54,65};

- - - - --

- - - - --

- - - - --

};

When we declare a structure then memory won’t be allocated for the structure. i.e only writing below

declaration statement will never allocate memory

struct student

{

int mark1;

int mark2;

int mark3;

};

We need to initialize structure variable to allocate some memory to the structure.

struct student s1 = {89,54,65};

4.1.6 Union

Unions are quite similar to the structures in C. Union is also a derived type as

structure. Union can be defined in same manner as structures just the keyword

used in defining union in union where keyword used in defining structure was struct.

union car

{

char name[50];

int price;

};

Union variables can be created in similar manner as structure variable.

union car

{

char name[50];

int price;

}c1, c2, *c3;

OR;

union car

{

char name[50];

int price;

};

-------Inside Function-----------

union car c1, c2, *c3;

In both cases, union variables c1, c2 and union pointer variable c3 of type union

car is created.

• Memory allocation for union

Like structure memory is allocated to union only when we create the variable of it.

The memory is allocated to union according to the largest data members of the union.

• Accessing members of an union

• Array elements are accessed using the Subscript variable , Similarly Union members are accessed using dot [.] operator.
• (.) is called as “union member Operator”.
• Use this Operator in between “Union variable” & “member name”

union employee  

   {  

 int id;  

 char name[50];  

 float salary; 

} ;

void main()

   {

      union employee e1= { 1, “ABC”, 50000 };

    printf(“%d”, e. id);

     printf(“%s”, e. name);

   }

O/P-  garbage value, ABC

4.1.7 Enumerated data types

Enumeration is a user defined datatype in C language. It is used to assign names to the integral constants which makes a program easy to read and maintain. The keyword “enum” is used to declare an enumeration.

Here is the syntax of enum in C language,

enum enum_name{const1, const2, ....... };

The enum keyword is also used to define the variables of enum type. There are two ways to define the variables of enum type as follows.

enum week{sunday, monday, tuesday, wednesday, thursday, friday, saturday};

enum week day;

4.1.8 Array of structures

Structure is collection of different data type. An object of structure represents a singlerecord in memory, if we want more than one record of structure type, we have tocreate an array of structure or object. As we know, an array is a collection of similartype, therefore an array can be of structure type.

Syntax for declaring structure array

struct struct-name

{

datatype var1;

datatype var2;

- - - - - - - - - -

- - - - - - - - - -

datatype varN;

};

struct struct-name obj [ size ];

Example for declaring structure array

#include<stdio.h>

struct Employee

{

int Id;

char Name[25];

int Age;

long Salary;

};

void main()

{

int i;

struct Employee Emp[ 3 ]; //Statement 1

for(i=0;i<3;i++)

{

printf("\nEnter details of %d Employee",i+1);

printf("\n\tEnter Employee Id : ");

scanf("%d",&Emp[i].Id);

printf("\n\tEnter Employee Name : ");

scanf("%s",&Emp[i].Name);

printf("\n\tEnter Employee Age : ");

scanf("%d",&Emp[i].Age);

printf("\n\tEnter Employee Salary : ");

scanf("%ld",&Emp[i].Salary);

}

printf("\nDetails of Employees");

for(i=0;i<3;i++)

printf("\n%d\t%s\t%d\t%ld",Emp[i].Id,Emp[i].Name,Emp[i].Age,Emp[i].Salary);

}

Output :

Enter details of 1 Employee

Enter Employee Id : 101

Enter Employee Name : Suresh

Enter Employee Age : 29

Enter Employee Salary : 45000

Enter details of 2 Employee

Enter Employee Id : 102

Enter Employee Name : Mukesh

Enter Employee Age : 31

Enter Employee Salary : 51000

Enter details of 3 Employee

Enter Employee Id : 103

Enter Employee Name : Ramesh

Enter Employee Age : 28

Enter Employee Salary : 47000

Details of Employees

101 Suresh 29 45000

102 Mukesh 31 51000

103 Ramesh 28 47000

In the above example, we are getting and displaying the data of 3 employee using

array of object. Statement 1 is creating an array of Employee Emp to store the records

of 3 employees.

Array within Structure

As we know, structure is collection of different data type. Like normal data type, It can

also store an array as well.

Syntax for array within structure

struct struct-name

{

datatype var1; // normal variable

datatype array [size]; // array variable

- - - - - - - - - -

- - - - - - - - - -

datatype varN;

};

struct struct-name obj;

Example for array within structure

struct Student

{

int Roll;

char Name[25];

int Marks[3]; //Statement 1 : array of marks

int Total;

float Avg;

};

void main()

{

int i;

struct Student S;

printf("\n\nEnter Student Roll : ");

scanf("%d",&S.Roll);

printf("\n\nEnter Student Name : ");

scanf("%s",&S.Name);

S.Total = 0;

for(i=0;i<3;i++)

{

printf("\n\nEnter Marks %d : ",i+1);

scanf("%d",&S.Marks[i]);

S.Total = S.Total + S.Marks[i];

}

S.Avg = S.Total / 3;

printf("\nRoll : %d",S.Roll);

printf("\nName : %s",S.Name);

printf("\nTotal : %d",S.Total);

printf("\nAverage : %f",S.Avg);

}

Output :

Enter Student Roll : 10

Enter Student Name : Kumar

Enter Marks 1 : 78

Enter Marks 2 : 89

Enter Marks 3 : 56

Roll : 10

Name : Kumar

Total : 223

Average : 74.00000

In the above example, we have created an array Marks[ ] inside structure representing

3 marks of a single student. Marks[ ] is now a member of structure student and to

access Marks[ ] we have used dot operator(.) along with object S.

4.1.9 Passing arrays to functions

Passing array to function using call by value method

As we already know in this type of function call, the actual parameter is copied to the formal parameters.

#include <stdio.h>

void disp( char ch)

{

   printf("%c ", ch);

}

int main()

{

   char arr[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j'};

   for (int x=0; x<10; x++)

   {

       /* I’m passing each element one by one using subscript*/

       disp (arr[x]);

   }

   return 0;

}

Output:

a b c d e f g h i j

Passing array to function using call by reference

When we pass the address of an array while calling a function then this is called function call by reference. When we pass an address as an argument, the function declaration should have a pointer as a parameter to receive the passed address.

#include <stdio.h>

void disp( int *num)

{

    printf("%d ", *num);

}

int main()

{

     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};

     for (int i=0; i<10; i++)

     {

         /* Passing addresses of array elements*/

         disp (&arr[i]);

     }

     return 0;

}

Output:

1 2 3 4 5 6 7 8 9 0

The word algorithm means “a process or set of rules to be followed in calculations or other problem-solving operations”. Therefore, Algorithm refers to a set of rules/instructions that step-by-step define how a work is to be executed upon in order to get the expected results.

 It must have the following characteristics:

• Clear and Unambiguous: Algorithm should be clear and unambiguous. Each of its steps should be clear in all aspects and must lead to only one meaning.
• Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs.
• Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-defined as well.
• Finite-ness: The algorithm must be finite, i.e. it should not end up in an infinite loops or similar.
• Feasible: The algorithm must be simple, generic and practical, such that it can be executed upon will the available resources. It must not contain some future technology, or anything.
• Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain instructions that can be implemented in any language, and yet the output will be same, as expected.

4.2.1 Searching & Basic Sorting Algorithms (Bubble, Insertion and Selection)

Searching (Linear Search, Binary Search Etc.)

Sorting and Searching are fundamental operations in computer science. Sorting refers to the operation of arranging data in some given order. Searching refers to the operation of searching the particular record from the existing information.

Consider a database of banking system where information of all customers such as name, contact number, address, account number is stored. If a manager wants to search for a record of a particular customer, he has to look for that record from among all records that has been stored in a database. This process of looking up for a particular record in a database is referred as searching.

If records in a banking database are not ordered properly it will be very difficult for a manager to search for a specific record. On the contrary if all record are arranged in order according to some criteria like names in alphabetical order or account numbers in ascending order, searching becomes easy and fast. The process of ordering the records in a data base is called sorting. Thus for efficient searching sorting is necessary.

Linear Search

Given a collection of objects, the goal of search is to find a particular object in this collection. The objects have key values on which search is performed and data values which correspond to the information one wishes to retrieve once an object is found. For example, a telephone book is a collection of names on which one searches and telephone numbers which correspond to the data being sought. The collection of objects is often stored in a list or an array. Given a collection of objects in an array A[1.. n], the ith  element A[i] corresponds to the key value of the ith  object in the collection. The input to a search algorithm is an array of objects A, the number of objects n, and the key value being sought x.

 Thus Algorithm for Linear Search is

 1. start at one end of the list

 2. if the current element is not equal to the search target, move to the next element,

 3. stop when a match is found or the opposite end of the list is reached.

 Function for Linear search is

 If element is found this function returns index of that element otherwise it returns –1.

Example : we have an array of integers, like the following:

 Let’s search for the number 7. According to function for linear search index for element 7 should be returned. We start at the beginning and check the first element in the array.

 First element is 9.Match is not found and hence we move to next element i.e 6.

 Again match is not found so move to next element i.e.7.

 We found the match at the index position 2. Hence output is 2.

 If we try to find element 10 in above array, it will return –1,as 10 is not present in the array.

Complexity Analysis of Linear Search:

 Let us assume element x is to be searched in array A of size n.

 An algorithm can be analyzed using following three cases.

 1. Worst case

 2. Average case

 3. Best case

 1. Worst case : In Linear search worst case happens when element to be searched is not present. When x is not present, the linear search function compares it with all the elements of A one by one. The size of A is n and hence x is to be compared with all n elements. Thus, the worst case time complexity of linear search would be O(n).

 2. Average case : In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. Following is the value of average case time complexity.

   Average Case Time = = 

    = O (n)

 3. Best Case : In linear search , the best case occurs when x is present at the first location. So time complexity in the best case would be O(1).

Merits :

 1. Simple and easy to implement

 2. It works well even on unsorted arrays.

 3. It is memory efficient as it does not require copying and partitioning of the array being searched.

Demerits :

1. Suitable only for small number of values.
2. It is slow as compared to binary search.

Binary Search

Binary Search requires sorted array.

Steps to perform binary search on sorted array A of size n are as follows.

1. Initialize lower and upper limit of array to be searched Low=0,High= n–1.

2. Find the middle position

  Mid=(Low + High)/2

3. Compare the input key value with the key value of the middle element of the array. It has 3 possibilities.

Case 1 : If keys match then return mid and print element found.

Case 2 : If key is less than middle element then element is present in left half of array. Update High and goto step 2. 

Case 3 : If key is greater than middle element then element is present in right half of array. Update Low and goto step 2. 

Case 4: if(Low>High)

Example 1 : Let array A= {–1, 5, 6, 18, 19, 25, 46, 78, 102, 114}. We want to find element ‘6’ using binary search.

Solution:

Step 1 : Low=0, High= 9

Step 2 : Mid=(Low + High)/2

Mid = (0+9)/2 =4.5 i.e 4. It means middle element is located at position 4. So A[Mid] is 19.Thus

 Low=0

 Mid=4

 High=9   

Step 3 : Compare 6 with 19. It satisfies case 2 of step 3. so High= 4–1=3 and element is present in left half of array. We can ignore right half of array.

 Repeat step 2. So mid= (0+3)/2 = 1.5 i.e 1. mid is at position 1. Element 5 is present at position 1.

 Low = 0

 Mid = 1

 High = 3

Again compare 5 with 6. It satisfies case 3 of step 3. so

Low = 1+1=2.  

Repeat step 2. Mid= (2+ 3)/2= 2.5 i.e 2 .Mid is at position 2. Element 6 is at position 2.

Low=2

Mid=2

High=3  

 Compare 6 with 6.

Match is found. Return the position and print element found.

Example 2 : Find 103 in {–1, 5, 6, 18, 19, 25, 46, 78, 102, 114} using Binary Search.

Step 1 : Low=0

High=9

Step 2 : Mid=(0+9)/2=4

 So middle element is 19.

Step 3 : Compare(103,19)

 103>19 hence element is located at right half of array and we can ignore left half of array. Update Low and recalculate mid.

    Low = 4+1=5

    High = 9 

    Mid = (5+9)/2=7

 Middle element is 78. Compare(103,78)

 103>78. Recalculate Low and Mid

    Low = 7+1=8

    High = 9

    Mid = (8+9)/2=8

 Middle element is 102. Compare(103,102)

 103>102. Recalculate Low and Mid.

    Low = 8+1=9

    High = 9

 Here Low=High and match is not found hence we conclude that element is not present in array.

Example 3 : Find 44 in A={5,12,17,23,38,44,77,84,90} using binary search.

Step 1: Low=0

  High=8

  Mid=(0+8)/2=4

 Middle element is 38. Compare(44,38)

 44>38.Thus element is located at right half of array and we can ignore left half of array. Recalculate Low and Mid.

    Low = (4+1)= 5

    High = 8

    Mid = (5+8)/2=6.5 i.e 6

 Middle element is 77. Compare(44,77)

 44<77. Recalculate High and Mid.

 Low=5

    High = 6–1=5

    Mid = (5+5)/2=5

 Middle element is 44. Compare(44,44)

 Match is Found. Return index and print “Element Found.”

 Algorithm for Recursive Binary Search

Complexity Analysis of Binary Search : 

 Assume our array size is 16.

 When n= 16 Binary Search is called to reduce size to n=8.

 When n= 8 Binary Search is called to reduce size to n=4.

 When n= 4 Binary Search is called to reduce size to n=2.

 When n= 2 Binary Search is called to reduce size to n=1 .

 Thus we see that Binary Search function is called 4 times

 i.e. 4 elements of the array were examined for n =16.

 Note that 16 = 24

 Let us consider a more general case where

 n is still a power of 2. Let us say n =2k

 After k searches, the while loop is executed k times and n reduces to size 1. Let us assume that each run of the while loop involves at most 4 operations.

 Thus total number of operations: 4k.

 The value of k can be determined from the expression

    2k = n

 Taking log of both sides

    k = log n

 Thus total number of operations = 4 log n.

 We conclude that the time complexity of the Binary search method is O(log n), which is much more efficient than the Linear Search method.

Merits :

 Binary Search is fast and efficient.

 Suitable for large number of values.

Demerits :

 Binary search works only on sorted array or list.

Basic Sorting Algorithms (Bubble, Insertion And Selection)

Bubble Sort     

Steps to perform Bubble sort are as follows.

Assume we want to sort the elements in ascending order and no two elements are equal.

1. Compare first element with second element. If first element is greater than next element, we interchange their position accordingly. i.e first element is moved to second element’s position and second element is moved to first element’s position. If No, then we don’t interchange any elements. 

2. The element in second position is compared with element in third position and the process of interchanging elements is performed if second is greater than third element. The whole process of comparing and interchanging is repeated till last element. When the process gets completed, the largest element in array will get placed in the last position of the array.

Let us consider array A of size n. Then Algorithm for Bubble sort is

1. Set i to 0.

2. Set j to 0.

3. if(A[j]>A[j+1])

    swap A[j],A[j+1]

4. Increment j

5. if j<(n–1–i) goto step 3

6. Increment i

7. if(i<n–1) goto step  2.

Example 1 : Suppose the following numbers are stored in an array A:

 We apply bubble sort to array A. We discuss each pass separately.

Pass 1

 1. Compare j[0] and j[1]. Since 32 < 51, the list is not altered.

 2. Compare j[1] and j[2] Since 51 > 27, interchange 51 and 27 as follows:

 Array A becomes

 3. Compare j[2] and j[3]. Since 51 < 85, array is not altered.

 4. Compare j[3] and j[4]. Since 85 > 66, interchange 85 and 66 as follows:

 Array A becomes

 5. Compare j[4] and j[5]. Since 85 > 23, interchange 85 and 23 as follows:

 Array A becomes

 6. Compare j[5] and j[6]. Since 85 > 13, interchange 85 and 13 as follows:

 7. Compare j[6] and j[7]. Since 85 > 57, interchange 85 and 57 as follows:

 Array A becomes

 At the end of this first pass, the largest number, 85, has moved to the last position. However, the rest of the numbers are not sorted, even though some of them have changed their positions.

 Pass 2 will move second last number at second last position, Pass 3 will move third last number at third last position and so on. Here we show array after every pass.

Pass 2 :

Pass 3 :

Pass 4:

Pass 5 :

Pass 6 :

 Hence the array is sorted in 6 passes.

 We will see one more example

Example 2 : Apply Bubble Sort on array A= {5,3,1,9,8,2,4,7}. 

Pass 2 : i=2 

Pass 3 :

Pass 4 :

 This array gets sorted in 4 passes only.

Example : Apply Bubble Sort on array A= {23,78,45,8,32,56}

Pass 1 :

Pass 2 :

Pass 3 :

 This array is sorted in 3 passes.

Complexity Bubble sort:

 Suppose we have a list with n elements, and each element perform n – 1 comparisons with elements to its left, and swap, if necessary.

 Best Case: If the list is already sorted, only one iteration is performed  and complexity is O(1).

 Average and Worst case: For n elements at most n – 1 swap operations is performed in each pass. The worst and average case complexity is O(n2).

Selection Sort

 Assume we want to sort list in ascending order. Selection sort finds the smallest element from unsorted list and swap it with the element in first position. Then it finds second smallest element and swap it with element at second position. This process is repeated till entire list is sorted in ascending order. Each time we swap elements,  we say that we  have completed a sort pass. A list of  n elements requires  n–1 passes to completely  rearrange the data.

 Procedure for every pass is as follows.

 Pass 1 : Find the position P of the smallest in the list of N elements A[l], A[2], . . . , A[N], and then interchange A[P] and A[1] . Then A[1] is sorted.

 Pass 2 : Find the position P of the smallest in the sublist of N –1 elements A[2], A[3],. . . , A[N], and then interchange A[P]and A[2]. Then A[l], A[2] is sorted.

 Pass 3 : Find the position P of the smallest in the sublist of N–2  elements A[3], A[4], . . . , A[N], and then interchange A[P] and A[3]. Then: A[l], A[2] , A[3] is sorted.

 Pass N –1 : Find the position P of the smaller of the elements A[N –1), A[N], and then interchange A[P] and A[N–1]. Then: A[l], A[2], . . . , A[N] is sorted. Thus A is sorted after N –1 passes.

Example 1 :

Fig. 4.2 : Original List

 We will apply selection sort on this list.

Pass 1 :

 Here smallest element is 9 and 25 is located at first position. so we swap 9 with 25.

After Pass 1

    Sorted      Unsorted sublist

 Now we find smallest element from unsorted sublist and place it in second position.

Pass 2 :

 Unsorted sublist has 25 as a smallest element and 79 is located at second position. Hence we swap 25 and 79.

After Pass 2 :

     Sorted                 Unsorted sublist

Pass 3 :

After Pass 3 :

   Sorted                 Unsorted sublist

Pass 4 :

After Pass 4 :

     Sorted  Unsorted sublist

Pass 5 :

After Pass 5 :

 Thus list is sorted.

 We will see one more example.

 Apply selection sort on array A= {77,30,40,10,88,20,65,56}

Pass 1 :

After Pass 1

Pass 2 :

After Pass 2

Pass 3 :

After Pass 3

Pass 4 :

After Pass 4

Pass 5 :

After Pass 5

Pass 6 :

After Pass 6

 Hence the list is sorted in ascending order by applying selection sort.

Output:

 Enter number of elements

 5

 Enter 5 integers

 4

 1

 7

 5

 9

 Sorted list in ascending order

 1

 4

 5

 7

 9

Complexity of Selection Sort :

 In selection sort outer for loop is executed n–1 times. On the kth time through the outer loop, initially the sorted list holds

 k–1 elements and unsorted portion holds n–k+1 elements.  In inner for loop 2 elements are compared each time.

 Thus, 2*(n–k) elements are examined by the inner loop during the k th pass through the outer loop. But k ranges from 1 to n–1.

 Total number of elements examined is:

    T(n) = 2*(n –1) + 2*(n–2) + 2*(n–3) + .. + 2*(n–(n–2))

     + 2*(n–(n–1))

    = 2*((n–1) + (n–2) + (n–3) + ... + 2 + 1)

 (or 2*(sum of first n–1 integers)

    = 2*((n–1)*n)/2)

    = n2 – n, so complexity of algorithm is O(n2).

Insertion Sort           

 Insertion Sort reads all elements from 1 to n and inserts each element at its proper position. This sorting method works well on small list of elements. 

 Procedure for each pass is as follows.

Pass 1 :

 A[l] by itself is trivially sorted.

Pass 2 :

 A[2] is inserted either before or after A[l] so that: A[l], A[2] is sorted.

Pass 3 :

 A[3] is inserted into its proper place so that: A[l], A[2], A[3] is sorted.

Pass 4 :

 A[4] is inserted into its proper place A[l], A[2], A[3], A[4] is sorted.

Pass N :

 A[N] is inserted into its proper place in  so that:

 A[l], A[ 2 ] , . . . , A[ N ] is sorted

Example : We will apply insertion sort on original list of Fig.3.Assume we are arranging elements in ascending order.