4.1.4 SEARCHING & SORTING

 Searching

§  Searching is the process of finding the location of the specified element in the list.

§  The specified element is called the search key.

§  F the process of searching finds a match of the search key with a list element value, the search is said to be successful; otherwise it is unsuccessful.

§  The two most commonly used search techniques are:

o   Sequential search / Linear search

o   Binary search

§  Sequential Search / Linear Search

o   WAP to check whether the given element is present in the array or not.

 

Sorting

§  Sorting is the process of arranging elements in the list according to their values, in ascending or descending order.

§  A sorted list is called an ordered list.

§  Sorted list are especially important in list searching because they facilitate rapid search operations. Many sorting techniques are available and among them, the three most important are:

o   Bubble sort

o   Selection sort

o   Insertion sort

§  Bubble Sort

o   In bubble sort, each element is compared with its adjacent elements. If the first element is larger than the second one then the positions of the elements are interchanged, otherwise it is not changed.

o   Then the next element is compared with its adjacent element and the same process is repeated for all the elements of the array.

o   Example: List (26,39,6,35,9)

   Key

number	Swapping
number	No swap

 

Pass 1	26	26	26	26
	39	6	6	6
	6	39	35	35
	35	35	39	9
	9	9	9	39

 

Pass 2	6	6	6	6
	26	26	26	26
	35	35	9	9
	9	9	35	35
	39	39	39	39

 

Pass 3	6	6	6	6
	26	9	9	9
	9	26	26	26
	35	35	35	35
	39	39	39	39

 

Pass 4	6	6	6	6
	9	9	9	9
	26	26	26	26
	35	35	35	35
	39	39	39	39

 

Pass 5	6	6	6	6
	9	9	9	9
	26	26	26	26
	35	35	35	35
	39	39	39	39

                                                   

o   WAP to sort the elements of an array using Bubble sort.

4.1.3 TWO-DIMENSIONAL ARRAY

Def:

The two-dimensional array is generally called a matrix.

Horizontal arrangement of elements is called row and vertical arrangement of elements is called column.

Memory Layout:

The elements of all arrays are stored contiguously in increasing memory locations, essentially in a single list.

  

Declaration of two-dimensional arrays

General form:

            type   array_name[row_size] [column_size];

The type specifies the type of element that will be contained in the array, the row_size indicates the maximum number of rows of the matrix and column_size indicates the maximum number of columns in the matrix.

e.g.      int attd[50][30];

           

Initialization of two-dimensional array

§  Compile-time Initialization

e.g.      float     total[2][3] = { 0, 0, 0, 1, 1, 1};

 

§  Run-time Initialization

e.g.      int   num[10][10];

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

                        {

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

            {

                        scanf ( “%d”, &num[i][j]);

                        }

            }

4.1.2 ONE-DIMENSIONAL ARRAY

Def:

A list of items can be given one variable name using only one subscript and such a variable is called a single-subscripted variable or a one-dimensional array. 

e.g.    If we want to represent a set of five numbers, say (35,40, 20, 57, 19) by an array variable ‘number’, then we may declare the variable ‘number’ as follows:

            int   number[5];

and the computer reserves five storage locations as shown below:

          

35

40

20

57

19

number[0]

number[1]

number[2]

number[3]

number[4]

NOTE: In C, the counting of elements begins with 0 and not 1.

Declaration of one-dimensional arrays

General form:

            type   array_name[size];

The type specifies the type of element that will be contained in the array, and the size indicates the maximum number of elements that can be stored inside the array.

e.g.      float salary[50];

            int group[10];

 Initialization of one-dimensional array

§  Compile-time Initialization

We can initialize the elements of arrays in the same way as the ordinary variables when they are declared.

General form:

            type   array_name[size] = { list of values };

            e.g.      float     total[5] = { 0.0, 15.75, -10, 6.3, 2.4};

 NOTE: If the array is not initialized, it would contain garbage values.

 §  Run-time Initialization

An array can be explicitly initialized at run-time. This approach is usually applied for initializing large arrays.

e.g.

(i)         int   num[10];

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

                        {

           scanf ( “%d”, &num[i]);

            }

(ii)        for ( i = 0; i < 100; i++)

            {

                        if ( i < 50)

                            sum[i] = 0.0;

                        else

                            sum[i] = 1.0;

            }

The first 50 elements of the array ‘sum’ are initialized to zero while the remaining 50 elements are initialized to 1.0 at run time.