UNIT 1

Syllabus:
• Data Structures - Definition, Classification of Data Structures, Operations on Data Structures, Abstract
Data Type (ADT), Preliminaries of algorithms. Time and Space complexity.
• Searching - Linear search, Binary search, Fibonacci search.
• Sorting- Insertion sort, Selection sort, Exchange (Bubble sort, quick sort), distribution (radix sort), merging
(Merge sort) algorithms.

INTRODUCTION:

• A data structure is a particular way of storing and organizing data in a computer so that it can be
used efficiently.

• A data structure is a specialized format for organizing, processing, retrieving and storing data.
There are several basic and advanced types of data structures, all designed to arrange data to suit
a specific purpose.
• The data structure name indicates itself that organizing the data in memory. There are many
ways of organizing the data in the memory as we have already seen one of the data structures,
i.e., array in C language. This organization of data is done with the help of an array of data
structures. There are also other ways to organize the data in memory.
• Some common examples of data structures are arrays, linked lists, queues, stacks, binary trees,
and hash tables
• The term data means a value or set of values. It specifies either the value of a variable or a constant
(e.g., marks of students, name of an employee, address of a customer, value of pi, etc.).
• A record is a collection of data items. For example, the name, address, course, and marks obtained
are individual data items. But all these data items can be grouped together to form a record.
• A file is a collection of related records. For example, if there are 60 students in a class, then there
are 60 records of the students. All these related records are stored in a file.

CLASSIFICATION OF DATA STRUCTURES:

• Data structures are generally categorized into two classes: primitive and non-primitive data
structures.
Primitive and Non-primitive Data Structures:
• Primitive data structures are the fundamental
data types which are supported by a
programming language. Some basic data types
are integer, real, character, and boolean. The
terms ‘data type, basic data type’, and ‘primitive
data type’ are often used interchangeably.

1
 • Non-primitive data structures are those data structures which are created using primitive data
structures. Examples of such data structures include linked lists, stacks, trees, and graphs.
• Non-primitive data structures can further be classified into two categories: linear and non-linear
data structures.
Linear and Non-linear Structures:
• If the elements of a data structure are stored in a linear or sequential order, then it is a linear data
structure.
o Examples include arrays, linked lists, stacks, and queues.
o Linear data structures can be represented in memory in two different ways. One way is to
have to a linear relationship between elements by means of sequential memory locations.
The other way is to have a linear relationship between elements by means of links.
• If the elements of a data structure are not stored in a sequential order, then it is a non-linear data
structure.
o The relationship of adjacency is not maintained between elements of a non-linear data
structure. Examples include trees and graphs.
Arrays:

• An array is a collection of similar data elements. These data elements have the same data type.
The elements of the array are stored in consecutive memory locations and are referenced by an
index (also known as the subscript).
• In C, arrays are declared using the following syntax: datatype name[size];
Ex: int marks[10];

limitations:
o Arrays are of fixed size.
o Data elements are stored in contiguous memory locations which may not be always available.
o Insertion and deletion of elements can be problematic because of shifting of elements from their
positions.
Linked Lists:
• linked list is a dynamic data structure in which elements (called nodes) form a sequential list.
• In a linked list, each node is allocated space as it is added to the list. Every node in the list points
to the next node in the list.
• Every node contains the following
The value of the node or any other data that corresponds to that node
A pointer or link to the next node in the list

2
 • The first node in the list is pointed by Head/Start/First. The last node in the list contains a NULL
pointer to indicate that it is the end or tail of the list.
Advantage: Easier to insert or delete data elements
Disadvantage: Slow search operation and requires more memory space
Stacks:
• A stack is a linear data structure in which insertion and deletion of elements are done at only one
end, which is known as the top of the stack.
• Stack is called a last-in, first-out (LIFO)
structure because the last element which is
added to the stack is the first element which
is deleted from the stack.
• Stacks can be implemented using arrays or
linked lists.
• Every stack has a variable top associated
with it. Top is used to store the address of
the topmost element of the stack.
• It is this position from where the element will be added or deleted. There is another variable MAX,
which is used to store the maximum number of elements that the stack can store.
• If top = NULL, then it indicates that the stack is empty and if top = MAX–1, then the stack is full.
• A stack supports three basic operations: push, pop, and peep. The push operation adds an element
to the top of the stack. The pop operation removes the element from the top of the stack. And the
peep operation returns the value of the topmost element of the stack (without deleting it).
Queues:
• A Queue is a linear data structure in which insertion can be done at rear end and deletion of
elements can be dome at front end.
• A queue is a first-in, first-out (FIFO) data
structure in which the element that is
inserted first is the first one to be taken
out.
• Like stacks, queues can be implemented by using either arrays or linked lists.

3
Insert element into the Queue:

Delete element from Queue:

• A queue is full when rear = MAX – 1, An underflow condition occurs when we try to delete an
element from a queue that is already empty. If front = NULL and rear = NULL, then there is no
element in the queue.
Trees:
• A tree is a non-linear data structure which consists of a collection of nodes arranged in a
hierarchical order.
• One of the nodes is designated as the root node, and the remaining nodes can be partitioned into
disjoint sets such that each set is a sub-tree of the root
• The simplest form of a tree is a binary tree. A binary tree
consists of a root node and left and right sub-trees, where both
sub-trees are also binary trees.
• Each node contains a data element, a left pointer which points
to the left sub-tree, and a right pointer which points to the right
sub-tree.
• The root element is the topmost node which is pointed by a
‘root’ pointer. If root = NULL then the tree is empty.

• Here R is the root node and T1 and T2 are the left and right subtrees of R. If T1 is non-empty,
then T1 is said to be the left successor of R. Likewise, if T2 is non-empty, then it is called the
right successor of R.
Advantage: Provides quick search, insert, and delete operations
Disadvantage: Complicated deletion algorithm
Graphs:
• A graph is a non-linear data structure which is a collection of vertices (also called nodes) and
edges that connect these vertices.
• A node in the graph may represent a city and the edges connecting
the nodes can represent roads.
• A graph can also be used to represent a computer network where

4
 the nodes are workstations and the edges are the network
connections.
• Graphs do not have any root node. Rather, every node in the graph can be connected with every
another node in the graph.
Advantage: Best models real-world situations
Disadvantage: Some algorithms are slow and very complex

OPERATIONS ON DATA STRUCTURES:

• This section discusses the different operations that can be performed on the various data structures
previously mentioned.
• Traversing Every data structure contains the set of data elements. Traversing the data structure
means visiting each element of the data structure in order to perform some specific operation
like searching or sorting.
• Searching The process of finding the location of an element within the data structure is called
Searching. There are two algorithms to perform searching, Linear Search and Binary Search. We
will discuss each one of them later in this tutorial
• Inserting It is used to add new data items to the given list of data items. For example, to add the
details of a new student who has recently joined the course.
• Deleting It means to remove (delete) a particular data item from the given collection of data items.
For example, to delete the name of a student who has left the course.
• Sorting Data items can be arranged in some order like ascending order or descending order
depending on the type of application. For example, arranging the names of students in a class in
an alphabetical order, or calculating the top three winners by arranging the participants’ scores in
descending order and then extracting the top three.
• Merging Lists of two sorted data items can be combined to form a single list of sorted data items.

ABSTRACT DATA TYPE:

• Abstract Data type (ADT) is a type (or class) for objects whose behaviour is defined by a set of
value and a set of operations.
• The definition of ADT only mentions what
operations are to be performed but not how
these operations will be implemented. It
does not specify how data will be organized
in memory and what algorithms will be used
for implementing the operations. It is called
“abstract” because it gives an
implementation-independent view.
5
 • The process of providing only the essentials and hiding the details is known as abstraction. We
can implement both these ADTs using an array or a linked list.
Advantage of using ADTs
• Modification of a program is simple, For example, if you want to add a new field to a student’s
record to keep track of more information about each student, then it will be better to replace an
array with a linked structure to improve the program’s efficiency.
• In such a scenario, rewriting every procedure that uses the changed structure is not desirable.
Therefore, a better alternative is to separate the use of a data structure from the details of its
implementation.
Various operations on Stack ADT are:
• isFull(), This is used to check whether stack is full or not
• isEmpty(), This is used to check whether stack is empty or not
• push(x), This is used to push x into the stack
• pop(), This is used to delete one element from top of the stack
• top(), This is used to get the top most element of the stack
• size(), this function is used to get number of elements present into the stack
Various operations on Queue ADT are:
• isFull(), This is used to check whether queue is full or not
• isEmpty(), This is used to check whether queue is empty or not
• insert(x), This is used to add x into the queue at the rear end
• delete(), This is used to delete one element from the front end of the queue
• size(), this function is used to get number of elements present into the queue
Various operations on List ADT are:
• size(), this function is used to get number of elements present into the list
• insert(x), this function is used to insert one element into the list
• remove(x), this function is used to remove given element from the list
• get(i), this function is used to get element at position i
• replace(x, y), this function is used to replace x with y value.

PRELIMINARIES OF ALGORITHM:

• Algorithm is step by step logical procedure for solving a problem.

• In Algorithm each step is called Instruction.
• An Algorithm is any well-defined computational procedure that take some values as inputs and
produce some values as output.
• An Algorithm is a sequence of computational steps that transform input into output.
• An Algorithm has 5 basic properties:
6
 1. Input:An Algorithm has take ‘0’ or more number of inputs that can be supplied as externally.
2. Output: An Algorithm must produce at least one output.
3. Definiteness: Each instruction in the algorithm must be clear.
4. Finiteness: An algorithm must terminate after a finite number of steps.
5. Effectiveness: Each operation should be effective. i.e the operations must be terminate after
finite amount of time.
Structure of an Algorithm:

1. Algorithm is a procedure consisting of heading and body. In body part we are writing statements
and in the head part we are writing the following.
Syntax: Algorithm name_of_Algo (param1,param2, …);
2. The beginning and ending of block should be indicated by ‘{‘ and ‘}’ or ‘start’ and ‘end’
respectively.
3. Every statement in the algorithm should be end with semicolon (;).
4. Single line comments are written using ‘//’ as beginning of comments.
5. The identifier should begin with character and it may be combination of alpha numeric.
6. Assignment operator (:=) we can use as follows Variable := expression (or) value;
7. There are other type of operators such as Boolean operators (TRUE/FALSE), logical operators
(AND,OR,NOT) and relational operators (<,>,<=,>=,…..)
8. The input and output we can write it as read and print respectively.
9. The Array index are stored with in [ ] brackets. The index of array starts from ‘0’ to ‘N-1’.
Syntax: datatype Aray_name[size];
10. The conditional statements such as if-then (or) if-then-else are written as follows. if(condition)
then statements;
if(condition) then statements;
else
statements;
7
 TIME AND SPACE COMPLEXITY:

• The efficiency of an algorithm can be computed by measuring the performance of an algorithm.

We can measure the performance of an algorithm in Two(2) ways.
1. Time Complexity
2. Space Complexity
1. Time Complexity:
• The time complexity of an algorithm is the amount of computing time required by an algorithm
to run its completion.
• There are 2 types of computing time 1. Compile time 2. Run time
• The time complexity generally computed at run time (or) execution time.
• The time complexity can be calculated in terms of frequency count.
• Frequency count is a count denoting the number of times the statement should be executed.
• The time complexity can be calculated as
Comments – 0
Assignment / return statement – 1
Conditional (or) Selection Constructs – 1
Example 1: Sum of the elements in an Array
Statements Step count/ Execution Frequency Total Steps
Algorithm Addition (A,n) 0 - 0
{ 0 - 0
//A is an array of size ‘n’ 0 - 0
Sum :=0; 1 1 1
for i:=1 to n do 1 n+1 n+1
Sum:=Sum+A[i]; 1 n n
return Sum; 1 1 1
} 0 - 0
Total 2n+3
Example 2: Subtraction of two matrices
Statements Step count/ Execution Frequency Total Steps
Algorithm Subtract (A,B,C,m,n) 0 - 0
{ 0 - 0
for i:=1 to m do 1 m+1 m+1
for j:=1 to n do 1 m(n+1) mn+m
C[i,j] := A[i,j] – B[i,j]; 1 mn mn
} 0 - 0
Total 2mn+2m+1
8
2. Space Complexity:
• Space Complexity can be defined as amount of memory (or) space required by an Algorithm to
run.
• To compute the space complexity we use 2 factors i. Constant ii. Instance characteristics.
• The space requirement S(p) can be given as S(p) = C+Sp
Where C- Constant, it denotes the space taken for input and output.
Sp – Amount of space taken by an instruction, variable and identifiers.

Example 1: Sum of three numbers

Algorithm Add(a,b,c)
{
//a,b,c are float type variables
return a+b+c;
}
• The space required for this algorithm is: Assume a,b,c are occupies 1 word size each, total size
comes to be 3.
Example 2: Sum of Array values
Algorithm Addition (A,n)
{
//A is an array of size ‘n’
Sum :=0;
for i:=1 to n do
Sum:=Sum+A[i];
return Sum;
}
• The space required for this algorithm is:
One word space for each variable then i,sum,n → 3
For Array A[ ] we require the size → n
Total space complexity for this algorithm is S(p) ≥ (n+3)
What to Analyze in an algorithm:

An Algorithm can require different times to solve different problems of same size
1. Worst case: Maximum amount of time that an algorithm require to solve a problem of size ‘n’.
Normally we can take upper bound as complexity. We try to find worst case behavior.
2. Best case: Minimum amount of time that an algorithm require to solve a problem of size ‘n’.
Normally it is not much useful.
3. Average case: the average amount of time that an algorithm require to solve a problem of size ‘n’.
Some times it is difficult to find. Because we have to check all possible data organizations
9
 SEARCHING:

• Searching means to find whether a particular value is present in an array or not.

• If the value is present in the array, then searching is said to be successful and the searching process
gives the location of that value in the array.
• However, if the value is not present in the array, the searching process displays an appropriate
message and in this case searching is said to be unsuccessful.
• Searching techniques are linear search, binary search and Fibonacci Search
LINEAR SEARCH:

• Linear search is a technique which traverse the array sequentially to locate given item or search
element.
• In Linear search, we access each element of an array one by one sequentially and see weather it
is desired element or not. We traverse the entire list and match each element of the list with the
item whose location is to be found. If the match found then location of the item is returned
otherwise the algorithm return NULL.
• A search is successful then it will return the location of desired element
• If A search will unsuccessful if all the elements are accessed and desired element not found.
• Linear search is mostly used to search an unordered list in which the items are not sorted.
Linear search is implemented using following steps...
Step 1 - Read the search element from the user.
Step 2 - Compare the search element with the first element in the list.
Step 3 - If both are matched, then display "Given element is found!!!" and terminate the function
Step 4 - If both are not matched, then compare search element with the next element in the list.
Step 5 - Repeat steps 3 and 4 until search element is compared with last element in the list.
Step 6 - If last element in the list also doesn't match, then display "Element is not found!!!" and
terminate the function.
Algorithm
Algorithm Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

10
Example
Consider the following list of elements and the element to be searched...

11
 BINARY SEARCH:

• Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to
search an element into some list by using binary search technique, we must ensure that the list is
sorted.
• Binary search follows divide and conquer approach in which, the list is divided into two halves and
the item is compared with the middle element of the list. If the match is found then, the location of
middle element is returned otherwise, we search into either of the halves depending upon the result
produced through the match.
Linear search is implemented using following steps...
Step 1 - Read the search element from the user.
Step 2 - Find the middle element in the sorted list.
Step 3 - Compare the search element with the middle element in the sorted list.
Step 4 - If both are matched, then display "Given element is found!!!" and terminate the function.
Step 5 - If both are not matched, then check whether the search element is smaller or larger than
the middle element.
Step 6 - If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left
sublist of the middle element.
Step 7 - If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right
sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or until sublist
contains only one element.
Step 9 - If that element also doesn't match with the search element, then display "Element is not
found in the list!!!" and terminate the function.
Algoritham
BINARY_SEARCH(A, lower_bound, upper_bound, VAL)
Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = - 1
Step 2: Repeat Steps 3 and 4 while BEG <=END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID - 1
ELSE
SET BEG = MID + 1
12
 [END OF IF]
[END OF LOOP]
Step 5: IF POS = -1
PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
[END OF IF]
Step 6: EXIT
Example 1: Consider the following list of elements and the element to be searched...

Example 2:

13
 FIBONACCI SEARCH:

• Fibonacci search is an efficient search algorithm based on divide and conquer principle that can
find an element in the given sorted array with the help of Fibonacci series in O(log N) time
complexity. This is based on Fibonacci series which is an infinite sequence of numbers denoting
a pattern which is captured by the following equation:
F(n)=n if n<=1
F(n)=F(n-1)+F(n-2) if n>1
o where F(i) is the ith number of the Fibonacci series where F(0) and F(1) are defined as 0
and 1 respectively.
• The first few Fibonacci numbers are: 0,1,1,2,3,5,8,13....
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 1 + 2 = 3 and so continues the series
Algorithm:
Step 1: Firstly, we need to find F(m) which is mth fibonacci number which is greater than or equal to the
size of array (n).
Step 2: If F(m) = 0, then we need to stop here and print the message as element not found.
Step 3: Set variable offset = -1.
Step 4: We need to set i = min( offset + F(m-2), n-1)

14
Step 5: We will check:
• If search element (s) == Array[i] then, return i and stop the search.
• If search element (s) > Array[i] then, m = m-1, offset = i and we need to repeat steps 4,5.
• If search element (s) < Array[i] then, m = m-2 repeat steps 4,5.
Example: The Elements in array & Search key is
Search_Key 85
elements 10 22 35 40 45 50 80 82 85 90 95
Index 0 1 2 3 4 5 6 7 8 9 10
Initially the Fibonacci series is …
0 1 1 2 3 5 8 13 21 34
1 2 3 4 5 6 7 8 9 10
F(m-2) F(m-1) F(m)
To calculate index position i = min(offset+F(m-2), n-1), Initially offset value is -1.
F(m) F(m-1) F(m-2) Offset i(index) a[i] Consequence
13 8 5 -1 (-1+5,10) = 4 45 1 steps down, Reset offset
8 5 3 4 (4+3, 10)=7 82 1 steps down, Reset offset
5 3 2 7 (7+2, 10) =9 90 2 steps down
2 1 1 7 (7+1, 10) = 8 85 Return i
Finally our desired element is found at the location of 8.

SORTINGS:

• Definition: Sorting is a technique to rearrange the list of records(elements) either in ascending

or descending order, Sorting is performed according to some key value of each record.
Categories of Sorting:
The sorting can be divided into two categories. These are:
1. Internal Sorting
2. External Sorting
• Internal Sorting: When all the data that is to be sorted can be accommodated at a time in the
main memory (Usually RAM). Internal sortings has five different classifications: insertion,
selection, exchanging (Bubble sort, quick sort), distribution (radix sort), merging (Merge sort)
• External Sorting: When all the data that is to be sorted can’t be accommodated in the memory
(Usually RAM) at the same time and some have to be kept in auxiliary memory such as hard disk,
floppy disk, magnetic tapes etc.
Ex: Natural, Balanced, and Polyphase.

INSERTION SORT:

• Sorting is the process of arranging a list of elements in a particular order (Ascending or

15
 Descending).
• In Insertion sort the list can be divided into two parts, one is sorted list and other is unsorted list. In
each pass the first element of unsorted list is transfers to sorted list by inserting it in appropriate
position or proper place.

Following are the steps involved in insertion sort:

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.
Step 2 - Pick the next element, and store it separately in a key.
Step 3 - Now, compare the key with all elements in the sorted array.
Step 4 - If the element in the sorted array is smaller than the current element, then move to the next
element. Else, shift greater elements in the array towards the right.
Step 5 - Insert the value.
Step 6 - Repeat until the array is sorted.
Algortham
Algorithm Insertion_Sort(list)
Step 1: Initilise a[ -1 ] = 0.
Step 2: for ( i=0; i< lim; i++)
Step 3: Read an element ‘x’ into the list.
Step 4: Consider j = i - 1
Step 5: repeat (x < a [ j ])
Step 6: a [ j + 1 ] = a [ j ]
Step 7: decrement j--, go to step 6.
Step 8: a [ j + 1 ] = x.
Step 9: end of for i.
Step 10: End of Insertion Sort.
Example 1:

16
Example 2:

Time Complexity
Case Time Complexity

Best Case O(n)

Average Case O(n2)

Worst Case O(n2)

• Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted.
The best-case time complexity of insertion sort is O(n).
• Average Case Complexity - It occurs when the array elements are in jumbled order that is not
properly ascending and not properly descending. The average case time complexity of insertion
sort is O(n2).
• Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse
order. That means suppose you have to sort the array elements in ascending order, but its elements
are in descending order. The worst-case time complexity of insertion sort is O(n2).

SELECTION SORT:

• Selection sort is conceptually the most simplest sorting algorithm. This algorithm will first find
the smallest element in the array and swap it with the element in the first position, then it will
find the second smallest element and swap it with the element in the second position, and it will
keep on doing this until the entire array is sorted.

17
Following are the steps involved in selection sort(for sorting a given array in ascending order):
• Starting from the first element, we search the smallest element in the array, and replace it with the
element in the first position.
• We then move on to the second position, and look for smallest element present in the subarray,
starting from index 1, till the last index.
• We replace the element at the second position in the original array, or we can say at the first position
in the subarray, with the second smallest element.
• This is repeated, until the array is completely sorted.
Algorithm:
SELECTION SORT(arr, n)
Step 1: Repeat Steps 2 and 3 for i = 0 to n-1
Step 2: CALL SMALLEST(arr, i, n, pos)
Step 3: SWAP arr[i] with arr[pos]
[END OF LOOP]
Step 4: EXIT
SMALLEST (arr, i, n, pos)
Step 1: [INITIALIZE] SET SMALL = arr[i]
Step 2: [INITIALIZE] SET pos = i
Step 3: Repeat for j = i+1 to n
if (SMALL > arr[j])
SET SMALL = arr[j]
SET pos = j
[END OF if]
[END OF LOOP]
Step 4: RETURN pos

18
Example 1

Example 2: Consider the elements 23,78,45,88,32,56

Time Complexity:
Number of elements in an array is ‘N’
Number of passes required to sort is ‘N-1’
Number of comparisons in each pass is 1st pass N-1, 2nd Pass N-2 …
Time required for complete sorting is:
T(n) <= (N-1)*(N-1)
T(n) <= (N-1)2
Finally, The time complexity
19
 BUBBLE SORT:

• Bubble Sort is also called as Exchange Sort

• In Bubble Sort, each element is compared with its adjacent element
a) If he first element is larger than the second element then the position of the elements are
interchanged.
b) Otherwise, the position of the elements are not changed.
c) The same procedure is repeated until no more elements are left for comparison.
• After the 1st pass the largest element is placed
at (N-1)th location. Given a list of n elements,
the bubble sort requires up to n – 1 passes to
sort the data.
Following are the steps involved in bubble sort(for sorting a given array in ascending order):
• Starting with the first element(index = 0), compare the current element with the next element of
the array.
• If the current element is greater than the next element of the array, swap them.
• If the current element is less than the next element, move to the next element. Repeat Step 1.
Algorithm:
BUBBLE SORT(ARR, N)
Step 1: Read the array elements
Step 2: i:=0;
Step 3: Repeat step 4 and step 5 until i<n
Step 4: j:=0;
Step 5: Repeat step 6 until j<(n-1)-i
Step 6: if A[j] > A[j+1]
Swap(A[j],A[j+1])
End if
End loop 5
End loop 3
Step 7: EXIT
T(n) <= (N-1)2
Finally, The time complexity is O(n2).
Example 1:
• We take an unsorted array for our example.

20
 • Bubble sort starts with very first two elements, comparing them to check which one is greater.

• In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33
with 27. We find that 27 is smaller than 33 and these two values must be swapped.

• Next we compare 33 and 35. We find that both are in already sorted positions.

• Then we move to the next two values, 35 and 10. We know then that 10 is smaller 35.

• We swap these values. We find that we have reached the end of the array. After one iteration, the
array should look like this −

• To be defined, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this

• Notice that after each iteration, at least one value moves at the end.

• And when there's no swap required, bubble sorts learns that an array is completely sorted.

Time Complexity:
Number of elements in an array is ‘N’
Number of passes required to sort is ‘N-1’
Number of comparisons in each pass is 1st pass N-1, 2nd Pass N-2 …
Time required for complete sorting is:
T(n) <= (N-1)*(N-1)

21
 QUICK SORT:

• Quick sort is a fast sorting algorithm used to sort a list of elements. The quick sort algorithm
attempts to separate the list of elements into two parts and then sort each part recursively. That
means it use divide and conquer strategy.
• In quick sort, the partition of the list is performed based on the element called pivot. Here pivot
element is one of the elements in the list.
• The list is divided into two partitions such that "all elements to the left of pivot are smaller than
the pivot and all elements to the right of pivot are greater than or equal to the pivot".

So, here are the steps how Quick sort works in simple words.
1. First select an element which is to be called as pivot element.
2. Next, compare all array elements with the selected pivot element and arrange them in such a way
that, elements less than the pivot element are to its left and greater than pivot is to it's right.
3. Finally, perform the same operations on left and right side elements to the pivot element.
In Quick sort algorithm, partitioning of the list is performed using following steps...
Step 1 - Consider the first element of the list as pivot (i.e., Element at first position in the list).
Step 2 - Define two variables i and j. Set i and j to first and last elements of the list respectively.
Step 3 - Increment i until list[i] > pivot then stop.
Step 4 - Decrement j until list[j] < pivot then stop.
Step 5 - If i < j then exchange list[i] and list[j].
Step 6 - Repeat steps 3,4 & 5 until i > j.
Step 7 - Exchange the pivot element with list[j] element.
Algorithm:
QUICKSORT (array A, start, end)
{
if (start < end)
{
p = partition(A, start, end)
QUICKSORT (A, start, p - 1)
QUICKSORT (A, p + 1, end)
}
}
Example:
22
23
 RADIX SORT:

• Radix sort is one of the sorting algorithms used to sort a list of integer numbers in order. In radix
sort algorithm, a list of integer numbers will be sorted based on the digits of individual numbers.
Sorting is performed from least significant digit to the most significant digit.
• Radix sort algorithm requires the number of passes which are equal to the number of digits
present in the largest number among the list of numbers. For example, if the largest number is a
3 digit number then that list is sorted with 3 passes.
• 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 (LSD) to the most significant (MSD) 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 digits.
Step by Step Process: - The Radix sort algorithm is performed using the following steps...
• Step 1 - Define 10 queues each representing a bucket for each digit from 0 to 9.
• Step 2 - Consider the least significant digit of each number in the list which is to be sorted.
• Step 3 - Insert each number into their respective queue based on the least significant digit.
• Step 4 - Group all the numbers from queue 0 to queue 9 in the order they have inserted into their
respective queues.
• Step 5 - Repeat from step 3 based on the next least significant digit.
• Step 6 - Repeat from step 2 until all the numbers are grouped based on the most significant digit.
Algorithm:
Step 1: Find the largest number in ARR as LARGE
Step 2: [INITIALIZE] SET NOP = Number of digits in LARGE
Step 3: SET PASS =0
Step 4: Repeat Step 5 while PASS <= NOP-1
Step 5: SET I = 0 and INITIALIZE buckets
Step 6: Repeat Steps 7 to 9 while i<n-1
Step 7: SET DIGIT = digit at PASSth place in A[I]
Step 8: Add A[I] to the bucket numbered DIGIT
Step 9: INCREMENT bucket count for bucket numbered DIGIT
[END OF LOOP]
Step 10: Collect the numbers in the bucket
[END OF LOOP]
Step 11: END

24
Example 1: Sort the numbers given below using radix sort.

Example 2: Sort the numbers given below using radix sort.

345, 654, 924, 123, 567, 472, 555, 808, 911
25
 • In the first pass, the numbers are sorted according to the digit at ones place.

• After this pass, the numbers are collected bucket by bucket. In the second pass, the numbers are
sorted according to the digit at the tens place.

• In the third pass, the numbers are sorted according to the digit at the hundreds place.

• The numbers are collected bucket by bucket. After the third pass, the list can be given as final
sorted list. 123, 345, 472, 555, 567, 654, 808, 911, 924.
Divide and Conquer:
• Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design is to take a
dispute on a huge input, break the input into minor pieces, decide the problem on each of the small
pieces, and then merge the piecewise solutions into a global solution. This mechanism of solving
the problem is called the Divide & Conquer Strategy.
• Divide and Conquer algorithm consists of a dispute using
the following three steps.
1. Divide the original problem into a set of sub-problems.
2. Conquer: Solve every sub-problem individually,
recursively.
3. Combine: Put together the solutions of the sub-problems
to get the solution to the whole problem.
26
 MERGE SORT:

• Merge sort is one of the most efficient sorting algorithms. It works on the principle of Divide
and Conquer. Merge sort repeatedly breaks down a list into several sublists until each sublist
consists of a single element and merging those sublists in a manner that results into a sorted
list.
Step by Step Process: -
1. Divide: In this step, the array/list divides itself recursively into sub-arrays until the base case is reached.
2. Recursively solve: Here, the sub-arrays are sorted using recursion.
3. Combine: This step makes use of the merge( ) function to combine the sub-arrays into the final sorted
array.
Algorithm for Merge Sort
Step 1: Find the middle index of the array.
Middle = 1 + (last – first)/2
Step 2: Divide the array from the middle.
Step 3: Call merge sort for the first half of the array
MergeSort(array, first, middle)
Step 4: Call merge sort for the second half of the array.
MergeSort(array, middle+1, last)
Step 5: Merge the two sorted halves into a single sorted array.
Algorithm Divide (a, low, high)
{
// a is an array, low is the starting index and high is the end index of a
If( low < high) then
{
Mid: = (low + high) /2;
Divide( a, low, mid);
Divide( a, mid +1, high);
Merge(a, low, mid, high);
}
}
Example 1
Let the elements of array are –

According to the merge sort, first divide the given array into two equal halves. Merge sort keeps dividing
the list into equal parts until it cannot be further divided.
As there are eight elements in the given array, so it is divided into two arrays of size 4.

27
Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of
size 2.

Now, again divide these arrays to get the atomic value that cannot be further divided.

Now, combine them in the same manner they were broken.

In combining, first compare the element of each array and then combine them into another array in sorted
order.
So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the list of two
values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17 first followed by 32.
After that, compare 40 and 42, and place them sequentially.

In the next iteration of combining, now compare the arrays with two data values and merge them into an
array of found values in sorted order.

Now, there is a final merging of the arrays. After the final merging of above arrays, the array will look
like -

Now, the array is completely sorted.

Example 2

28
Time Complexities All the Searching & Sorting Techniques:

29