DATA STRUCTURE USING C (22317)
Unit– II Searching and Sorting
Searching
Searching is used to find the location where an element is available. There are two
types of search techniques. They are:
Linear or sequential search
Binary search
Linear Search:
This is the simplest of all searching techniques. In this technique, an ordered or
unordered list will be searched one by one from the beginning until the desired element is
found. If the desired element is found in the list then the search is successful otherwise
unsuccessful. Suppose there are n elements organized sequentially on a List. The number of
comparisons required to retrieve an element from the list, purely depends on where the
element is stored in the list. If it is the first element, one comparison will do; if it is second
element two comparisons are necessary and so on. On an average you need [(n+1)/2]
comparisons to search an element. If search is not successful, you would need ‗n’
comparisons.
The time complexity of linear search is O(n).
Algorithm :-
LINEAR_SEARCH(A, N, VAL)
Step 1: [INITIALIZE] SET POS = -1
Step 2: [INITIALIZE] SET I = 1
Step 3: Repeat Step 4 while I<=N
Step 4: IF A[I] = VAL
SET POS = I
PRINT POS
Go to Step 6
[END OF IF]
[END OF LOOP]
Step 6: EXIT
SET I = I + 1
Step 5: IF POS = –1
PRINT VALUE IS NOT PRESENT
IN THE ARRAY
[END OF IF]
BY PROF V.D.GHOGARE Page 10
DATA STRUCTURE USING C (22317)
Example
14.3 Binary Search
Binary search is a searching algorithm that works efficiently with a sorted list. The mechanism
of binary search can be better understood by an analogy of a telephone directory. When we are
searching for a particular name in a directory, we first open the directory from the middle and
then decide whether to look for the name in the first part of the directory or in the second part
ofthe directory. Again, we open some page in the middle and the whole process is repeated
untilwe finally find the right name.. The same mechanism is applied in the binary search.
Now, let us consider how this mechanism is applied to search for a value in a sorted array.
Consider an array A[] that is declared and initialized as
int A[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; and the value to be searched is VAL = 9. The
algorithm will proceed in the following manner.
BEG = 0, END = 10, MID = (0 + 10)/2 = 5
Now, VAL = 9 and A[MID] = A[5] = 5
A[5] is less than VAL, therefore, we now search for the value in the second half of the array.
So,
we change the values of BEG and MID.
Now, BEG = MID + 1 = 6, END = 10, MID = (6 + 10)/2 =16/2 = 8
VAL = 9 and A[MID] = A[8] = 8
A[8] is less than VAL, therefore, we now search for the value in the second half of the
segment.
So, again we change the values of BEG and MID.
BY PROF V.D.GHOGARE Page 11
DATA STRUCTURE USING C (22317)
Now, BEG = MID + 1 = 9, END = 10, MID = (9 + 10)/2 = 9
Now, VAL = 9 and A[MID] = 9.
Algorithm
Example
BY PROF V.D.GHOGARE Page 12
DATA STRUCTURE USING C (22317)
Comparision between Linear search and binary search
BY PROF V.D.GHOGARE Page 13
DATA STRUCTURE USING C (22317)
Sorting
Sorting means arranging the elements of an array so that they are placed in some relevant
order which may be either ascending or descending.
There are two types of sorting techniques:
1. Internal sorting
2. External sorting
If all the elements to be sorted are present in the main memory then such sorting is called
internal sorting on the other hand, if some of the elements to be sorted are kept on the
secondary storage, it is called external sorting. Here we study only internal sorting
techniques.
Sorting techniques
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Quick Sort
5. Radix Sort.
1. Bubble Sort
Bubble sort is a very simple method that sorts the array elements by repeatedly moving the
largest element to the highest index position of the array segment (in case of arranging
elements in ascending order). In bubble sorting, consecutive adjacent pairs of elements in the
array are compared with each other. If the element at the lower index is greater than the
element at the higher index, the two elements are interchanged so that the element is placed
before the bigger one. This process will continue till the list of unsorted elements exhausts.
This procedure of sorting is called bubble sorting because elements ‗bubble‘ to the top of the
list. Note that at the end of the first pass, the largest element in the list will be placed at its
proper position (i.e., at the end of the list).
The basic methodology of the working of bubble sort is given as follows:
[1] In Pass 1, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is
compared with A[3], and so on. Finally, A[N–2] is compared with A[N–1]. Pass 1
involves n–1 comparisons and places the biggest element at the highest index of the
array.
[2] In Pass 2, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is
compared with A[3], and so on. Finally, A[N–3] is compared with A[N–2]. Pass 2
involves n–2 comparisons and places the second biggest element at the second highest
index of the array.
BY PROF V.D.GHOGARE Page 14
DATA STRUCTURE USING C (22317)
[3] In Pass 3, A[0] and A[1] are compared, then A[1] is compared with A[2], A[2] is
compared with A[3], and so on. Finally, A[N–4] is compared with A[N–3]. Pass 3
involves n–3 comparisons and places the third biggest element at the third highest
index of the array.
[4] In Pass n–1, A[0] and A[1] are compared so that A[0]<A[1]. After this step, all the
elements of the array are arranged in ascending order.
BY PROF V.D.GHOGARE Page 15
DATA STRUCTURE USING C (22317)
Program for Bubble Sort:
#include <stdio.h>
#include <conio.h>
void bubblesort(int x[], int n)
int i, j, temp;
for (i = 0; i < n; i++)
for (j = 0; j < n–i-1 ; j++)
BY PROF V.D.GHOGARE Page 16
DATA STRUCTURE USING C (22317)
if (x[j] > x[j+1])
temp = x[j];
x[j] = x[j+1];
x[j+1] = temp;
main()
int i, n, x[25]; clrscr();
printf("\n Enter the number of elements: "); scanf("%d", &n);
printf("\n Enter Data:"); for(i = 0; i < n ; i++)
scanf("%d", &x[i]); bubblesort(x, n);
printf ("\n Array Elements after sorting: ");
for (i = 0; i < n; i++)
printf ("%5d", x[i]);
BY PROF V.D.GHOGARE Page 17
DATA STRUCTURE USING C (22317)
2. Selection Sort
It is a natural sorting algorithm in which we find minimum, second minimum, third minimum
and so on and arrange them in increasing order. Like bubble sort, irrespective of the input,
during ith stage this algorithm incurs (n − i) comparisons.
Working of Selection sort: Selection Sort algorithm is used to arrange a list of elements in a
particular order (Ascending or Descending). In selection sort, the first element in the list is
selected and it is compared repeatedly with remaining all the elements in the list. If any element
is smaller than the selected element (for ascending order), then both are swapped. Then we select
the element at second position in the list and it is compared with remaining all elements in the
list. If any element is smaller than the selected element, then both are swapped. This procedure is
repeated till the entire list is sorted
BY PROF V.D.GHOGARE Page 18
DATA STRUCTURE USING C (22317)
3. Insertion sort
Insertion sort is a very simple sorting algorithm in which the sorted array (or list) is built one
element at a time. The main idea behind insertion sort is that it inserts each item into its proper
place in the final list. To save memory, most implementations of the insertion sort algorithm
work by moving the current data element past the already sorted values and repeatedly
interchanging it with the preceding value until it is in its correct place. Insertion sort is less
efficient as compared to other more advanced algorithms such as quicksort, heap sort, and merge
sort.Insertion sort provides several advantages:
Simple implementation
Efficient for (quite) small data sets
Stable; i.e., does not change the relative order of elements with equal keys
In-place; i.e., only requires a constant amount O(1) of additional memory space
BY PROF V.D.GHOGARE Page 19
DATA STRUCTURE USING C (22317)
4. Radix sort
Radix sort is a linear sorting algorithm for integers and uses the concept of sorting names in
alphabetical order. When we have a list of sorted names, the radix is 26 (or 26 buckets) because
there are 26 letters in the English alphabet. So radix sort is also known as bucket sort. Observe
that words are first sorted according to the first letter of the name. That is, 26 classes are used
to arrange the names, where the first class stores the names that begin with A, the second class
contains the names with B, and so on. During the second pass, names are grouped according to
the second letter. After the second pass, names are sorted on the first two letters. This process is
continued till the nth pass, where n is the length of the name with maximum number of letters.
After every pass, all the names are collected in order of buckets. That is, first pick up the names
in the first bucket that contains the names beginning with A. In the second pass, collect the
namesfrom the second bucket, and so on. When radix sort is used on integers, sorting is done on
each of the digits in the number. The sorting procedure proceeds by sorting the least significant
to the most significant digit. While sorting the numbers, we have ten buckets, each for one digit
(0, 1, 2, …, 9) and the number of passes will depend on the length of the number having
maximum number of digts.
BY PROF V.D.GHOGARE Page 20
DATA STRUCTURE USING C (22317)
BY PROF V.D.GHOGARE Page 21
DATA STRUCTURE USING C (22317)
5. Quick Sort
Quick sort is a divide and conquer algorithm. Quick sort first divides a large list into two smaller
sublists: the low elements and the high elements. Quick sort can then recursively sort the sub-
lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot,
while all elements with values greater than the pivot come after it (equal values can go either
way). After this partitioning, the pivot is in its final position. This is called the partition
operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values and
separately the sub-list of elements with greater values. The base case of the recursion is lists of
size zero or one, which never need to be sorted.
Quick sort, or partition-exchange sort, is a sorting algorithm developed by Tony Hoare that, on
average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n 2 )
comparisons, though this behavior is rare. Quick sort is often faster in practice than other O(n log
n) algorithms. It works by first of all by partitioning the array around a pivot value and then
dealing with the 2 smaller partitions separately. Partitioning is the most complex part of quick
sort. The simplest thing is to use the first value in the array, a[l] (or a[0] as l = 0 to begin with) as
the pivot. After the partitioning, all values to the left of the pivot are <= pivot and all values to
the right are > pivot. The same procedure for the two remaining sub lists is repeated and so on
recursively until we have the entire list sorted.
Advantages:
One of the fastest algorithms on average.
Does not need additional memory (the sorting takes place in the array - this is called in-place
processing).
Disadvantages:
he worst-case complexity is O(N2 )
Example
10,1,9,4,3
BY PROF V.D.GHOGARE Page 22
DATA STRUCTURE USING C (22317)
BY PROF V.D.GHOGARE Page 23
DATA STRUCTURE USING C (22317)
BY PROF V.D.GHOGARE Page 24
DATA STRUCTURE USING C (22317)
Unit– III Stacks and Queues
Stack
A stack is a list of elements in which an element may be inserted or deleted only at one end,
called the top of the stack. Stacks are sometimes known as LIFO (last in, first out) lists.As the
items can be added or removed only from the top i.e. the last item to be added to a stack is the
first item to be removed.
The two basic operations associated with stacks are:
Push: is the term used to insert an element into a stack.
Pop: is the term used to delete an element from a stack.
All insertions and deletions take place at the same end, so the last element added to the stack will
be the first element removed from the stack. When a stack is created, the stack base remains
fixed while the stack top changes as elements are added and removed. The most accessible
element is the top and the least accessible element is the bottom of the stack.
Stack (ADT) Data Structure:
Stack is an Abstract data structure (ADT) works on the principle Last In First Out (LIFO). The
last element add to the stack is the first element to be delete. Insertion and deletion can be takes
place at one end called TOP.
The add operation of the stack is called push operation
The delete operation is called as pop operation.
Push operation on a full stack causes stack overflow.
Pop operation on an empty stack causes stack underflow.
SP is a pointer, which is used to access the top element of the stack.
If you push elements that are added at the top of the stack;
In the same way when we pop the elements, the element at the top of the stack is
deleted.
BY PROF V.D.GHOGARE Page 25
