KTUQBANK.

COM

MODULE 5

Module V
Sorting and Searching : Bubble sort, Selection sort, Linear Search and Binary
search. Scope rules Storage classes. Bit-wise operations.

Bubble sort

Algorithm :
Step 1: [Start]

Begin

Step 2: [Input the number of elements in the array]

Read n
 KTUQBANK.COM

Step 3: [Input the n integer numbers]

For i =-1 in steps of 1

Read num[ i ]

End for

Step 4: [Display the original array]

For i = 0 through n-1 in steps of 1

Print num[ i]

End for

Step 5: [Repeat step 5 for i varies from 0 thru n-1]

For i  0 thru n-1 in steps of 1

For j = 0 through n-i-1 in steps of 1

IF ( num[j] > num[j + 1] ) then

temp= num[j]

num[j] = num[j + 1]

num[j+1] = temp

End if

End for

End for

Step 6: [Output the sorted array]

For i = 0 through n-1 in steps of 1

Print num[i]

End for

Selection Sort
Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially. The first position
where 14 is stored presently, we search the whole list and find that 10 is the lowest value.
 KTUQBANK.COM

So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list,
appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list in a linear
manner.

We find that 14 is the second lowest value in the list and it should appear at the second place. We
swap these values.

After two iterations, two least values are positioned at the beginning in a sorted manner.

The same process is applied to the rest of the items in the array. Following is a pictorial depiction

of the entire sorting process −

 KTUQBANK.COM

Selection sort

1. Start with the result as the first element of the input.

2. Loop over the input until it is empty, "removing" the first remaining (leftmost) element.

3. Compare the removed element against the current result, starting from the highest (rightmost)
element, and working left towards the lowest element.

4. If the removed input element is lower than the current result element, copy that value into the
following element to make room for the new element below, and repeat with the next lowest
result element.

5. Otherwise, the new element is in the correct location; save it in the cell left by copying the
last examined result up, and start again from (2) with the next input element.

Algorithm :

Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Linear Search And Binary Search

Linear Search
Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[].
A simple approach is to do linear search, i.e
• Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
• If x matches with an element, return the index.
• If x doesn’t match with any of elements, return -1.

Example:
 KTUQBANK.COM

// Linearly search x in arr[]. If x is present then return its

// location, otherwise return -1
int search(int arr[], int n, int x)
{
int i;
for (i=0; i<n; i++)
if (arr[i] == x)
return i;
return -1;
}

The time complexity of above algorithm is O(n).

Linear search is rarely used practically because other search algorithms such as the binary search
algorithm and hash tables allow significantly faster searching comparison to Linear search.
Binary Search
Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].
A simple approach is to do linear search.The time complexity of above algorithm is O(n). Another
approach to perform the same task is using Binary Search.
Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with
an interval covering the whole array. If the value of the search key is less than the item in the
middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half.
Repeatedly check until the value is found or the interval is empty.
 KTUQBANK.COM

Example:

Image Source : http://www.nyckidd.com/bob/Linear%20Search%20and%20Binary

%20Search_WorkingCopy.pdf
The idea of binary search is to use the information that the array is sorted and reduce the time
complexity to O(Logn).
We basically ignore half of the elements just after one comparison.
1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the
mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.
Recursive implementation of Binary Search

#include <stdio.h>

// A recursive binary search function. It returns location of x in

// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;

// If the element is present at the middle itself

if (arr[mid] == x) return mid;

// If element is smaller than mid, then it can only be

present
// in left subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

// Else the element can only be present in right subarray

 KTUQBANK.COM

return binarySearch(arr, mid+1, r, x);

}

// We reach here when element is not present in array

return -1;
}

int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}

Output:
Element is present at index 3

Iterative implementation of Binary Search

#include <stdio.h>

// A iterative binary search function. It returns location of x in

// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;

// Check if x is present at mid

if (arr[m] == x)
return m;

// If x greater, ignore left half

if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half

else
r = m - 1;
}

// if we reach here, then element was not present

return -1;
 KTUQBANK.COM

int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d",
result);
return 0;
}

Output:
Element is present at index 3

Scope rules Storage classes.

Storage class in C decides the part of storage to allocate memory for a variable, it also determines
the scope of a variable. All variables defined in a C program get some physical location in memory
where variable's value is stored. Memory and CPU registers are types of memory locations where a
variable's value can be stored. The storage class of a variable in C determines the life time of the
variable if this is 'global' or 'local'. Along with the life time of a variable, storage class also
determines variable's storage location (memory or registers), the scope (visibility level) of the
variable, and the initial value of the variable. There are four storage classes in C those are
automatic, register, static, and external.

Storage Class Specifiers

There are four storage class specifiers in C as follows, typedef specifier does not reserve storage
and is called a storage class specifier only for syntactic convenience. It is not a storage class
specifier in the common meaning.
• auto
• register
• extern
• static
• typedef
These specifiers tell the compiler how to store the subsequent variable. The general form of a
variable declaration that uses a storage class is shown here:
storage_class_specifier data_type variable_name;

At most one storage class specifier may be given in a declaration. If no storage class specifier is
specified then following rules are used:
1. Variables declared inside a function are taken to be auto.
2. Functions declared within a function are taken to be extern.
3. Variables and functions declared outside a function are taken to be static, with external
linkage.
 KTUQBANK.COM

Variables and functions having external linkage are available to all files that constitute a program.
File scope variables and functions declared as static (described shortly) have internal linkage.
These are known only within the file in which they are declared. Local variables have no linkage
and are therefore known only within their own block.

Types of Storage Classes

There are four storage classes in C they are as follows:
1. Automatic Storage Class
2. Register Storage Class
3. Static Storage Class
4. External Storage Class
Now, let us discuss these storage classes one by one.

1. Automatic Storage Class

A variable defined within a function or block with auto specifier belongs to automatic storage
class. All variables defined within a function or block by default belong to automatic storage class if
no storage class is mentioned. Variables having automatic storage class are local to the block which
they are defined in, and get destroyed on exit from the block.
The following C program demonstrates the visibility level of auto variables.
#include <stdio.h>
int main( )
{
auto int i = 1;
{
auto int i = 2;
{
auto int i = 3;
printf ( "\n%d ", i);
}
printf ( "%d ", i);
}
printf( "%d\n", i);
}

OUTPUT
======
3 2 1

In above example program you see three definitions for variable i. Here, you may be thinking if
there could be more than one variable with the same name. Yes, there could be if these variables are
defined in different blocks. So, there will be no error here and the program will compile and execute
successfully. The printf in the inner most block will print 3 and the variable i defined in the
inner most block gets destroyed as soon as control exits from the block. Now control comes to the
second outer block and prints 2 then comes to the outer block and prints 1. Here, note that automatic
variables must always be initialized properly, otherwise you are likely to get unexpected results
because automatic variables are not given any initial value by the compiler.

2. Register Storage Class

The register specifier declares a variable of register storage class. Variables belonging to
register storage class are local to the block which they are defined in, and get destroyed on exit from
 KTUQBANK.COM

the block. A register declaration is equivalent to an auto declaration, but hints that the
declared variable will be accessed frequently; therefore they are placed in CPU registers, not in
memory. Only a few variables are actually placed into registers, and only certain types are eligible;
the restrictions are implementation-dependent. However, if a variable is declared register, the unary
& (address of) operator may not be applied to it, explicitly or implicitly. Register variables are also
given no initial value by the compiler.
The following piece of code is trying to get the address of variable i into pointer variable p but it
won't succeed because i is declared register; therefore following piece of code won't compile
and exit with error "error: address of register variable requested".
#include <stdio.h>

int main()
{
register int i = 10;
int *p = &i; //error: address of register variable requested

printf("Value of i: %d", *p);

printf("Address of i: %u", p);

3. Static Storage Class

The static specifier gives the declared variable static storage class. Static variables can be used
within function or file.Unlike global variables, static variables are not visible outside their function
or file, but they maintain their values between calls. The static specifier has different effects
upon local and global variables. See the following flavours of static specifier.
• When static specifier is applied to a local variable inside a function or block, the
compiler creates permanent storage for it, much as it creates storage for a global variable but
static local variable remains visible only to the function or block in which it is defined. In
simple terms, a static local variable is a local variable that retains its value between function
calls. For example, the following program code defines static variable i at two places in
two blocks inside function staticDemo(). Function staticDemo() is called twice
within from main function. During second call static variables retain their old values and
they are not initialized again in second call of staticDemo().
#include <stdio.h>

void staticDemo()
{
static int i;
{
static int i = 1;
printf("%d ", i);
i++;
}
printf("%d\n", i);
i++;
}

int main()
{
staticDemo();
staticDemo();
}
OUTPUT
 KTUQBANK.COM

======
1 0
2 1

• When static specifier is applied to a global variable or a function then compiler makes
that variable or function known only to the file in which it is defined. A static global variable
has internal linkage that means even though the variable is global; routines in other files
have no knowledge of it and cannot access and alter its contents directly. The following C
program defines one static global variable gInt and a static function staticDemo(), for
the variable and function are defined static they cannot be used outside the file (translation
unit) staticdemo.c..
/* staticdemo.c */
#include <stdio.h>
static int gInt = 1;
static void staticDemo()
{
static int i;
printf("%d ", i);
i++;
printf("%d\n", gInt);
gInt++;
}

int main()
{
staticDemo();
staticDemo();
}
OUTPUT
======
0 1
1 2

Static variables have default initial value zero and initialized only once in their lifetime.

4. External Storage Class

The extern specifier gives the declared variable external storage class. The principal use of
extern is to specify that a variable is declared with external linkage elsewhere in the program. To
understand why this is important, it is necessary to understand the difference between a declaration
and a definition. A declaration declares the name and type of a variable or function. A definition
causes storage to be allocated for the variable or the body of the function to be defined. The same
variable or function may have many declarations, but there can be only one definition for that
variable or function.
When extern specifier is used with a variable declaration then no storage is allocated to that
variable and it is assumed that the variable has already been defined elsewhere in the program.
When we use extern specifier the variable cannot be initialized because with extern specifier
variable is declared, not defined.
In the following sample C program if you remove extern int x; you will get an error
"Undeclared identifier 'x'" because variable x is defined later than it has been used in printf. In
this example, the extern specifier tells the compiler that variable x has already been defined and
it is declared here for compiler's information.
#include <stdio.h>

extern int x;
 KTUQBANK.COM

int main()
{
printf("x: %d\n", x);
}

int x = 10;

Also, if you change the statement extern int x; to extern int x = 50; you will again
get an error "Redefinition of 'x'" because with extern specifier the variable cannot be initialized, if
it is defined elsewhere. If not then extern declaration becomes a definition.
Note that extern can also be applied to a function declaration, but doing so is redundant because
all function declarations are implicitly extern.

Practice Exercises
1. How internal and external linkage are different?
2. How do you make sure if a variable defined with register specifier got stored in CPU
register?
3. Can static global variables be used outside the file in which they have been defined?
4. How declaration of a function is different from its definition?
5. What if you try to assign a value to an extern variable which has already been defined?

References
1. The Complete Reference C
2. The C Programming Language by Brian W Kernighan and Dennis M Ritchie

Bit-wise operations.

Bitwise operator works on bits and perform bit-by-bit operation. The truth tables for &, |, and ^ is as
follows −
p q p&q p|q p^q
0 0 0 0 0
0 1 0 1 1
1 1 1 1 0
1 0 0 1 1
Assume A = 60 and B = 13 in binary format, they will be as follows −
A = 0011 1100
B = 0000 1101
-----------------
A&B = 0000 1100
A|B = 0011 1101
A^B = 0011 0001
~A = 1100 0011
 KTUQBANK.COM

The following table lists the bitwise operators supported by C. Assume variable 'A' holds 60 and
variable 'B' holds 13, then −
Operator Description Example
Binary AND Operator copies a bit to the result if it exists
& (A & B) = 12, i.e., 0000 1100
in both operands.
Binary OR Operator copies a bit if it exists in either
| (A | B) = 61, i.e., 0011 1101
operand.
Binary XOR Operator copies the bit if it is set in one
^ (A ^ B) = 49, i.e., 0011 0001
operand but not both.
Binary Ones Complement Operator is unary and has the (~A ) = -61, i.e,. 1100 0011 in
~
effect of 'flipping' bits. 2's complement form.
Binary Left Shift Operator. The left operands value is
<< moved left by the number of bits specified by the right A << 2 = 240 i.e., 1111 0000
operand.
Binary Right Shift Operator. The left operands value is
>> moved right by the number of bits specified by the right
operand.