DATA STRUCTURE

(CS201B)

Searching & Sorting

Course Instructor:
Mr Deepak Vishwakarma
(Assistant Professor, IT Department, KIET, Ghaziabad)
 Unit-1: Introduction (Syllabus)
 Introduction: Basic Terminology, Types and application of Data
Structures, Algorithm, Efficiency of an algorithm, Time space trade
off and complexity, asymptotic notations.
 Array: Single and Multidimensional Arrays, Representation of
Arrays: Row Major Order, and Column Major Order, Derivation of
Index Formulae for 1-D,2-D,3-D and n-D Array Application of
arrays, Sparse Matrices, and their representations, arithmetic
operations on matrices.
 Searching: Linear search, Binary Search, Indexed Sequential
search
 Sorting: Insertion Sort, Bubble sort, Selection sort, Quick Sort,
Merge Sort.

DATA STRUCTURE (CS201B)

(Mr Deepak Vishwakarma, Assistant Professor, IT, KIET)
 Searching and Sorting Algorithms
 Searching is the process of finding some particular element in the
list.
 We will discuss following searching algoritms:
 Linear search (Sequential Search)
 Binary search
 Indexed Sequential Search

 Sorting means to put numbers into right places, according to their

type.
 We will discuss following sorting algoritms:
 Bubble sort
 Insertion sort
 Selection sort
Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT
Department, KIET Ghaziabad)
 Linear Search
 Linear search is the simplest search algorithm and often called sequential search.
 In this type of searching, we simply traverse the list completely 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.
 Linear search is mostly used to search an unordered list in which the items are not
sorted. The algorithm of linear search is given as follows.
 Worst case complexity of linear serach is O(n).

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Linear Search

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 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.
 Worst case complexity of linear serach is O(log n).

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Binary Search (Algorithm)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Binary Search (Recursive Source Code)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Binary Search (Non-Recursive Source Code)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Indexed Sequential Search
 In this searching method, first of all, an index file is created, that contains some specific
group or division of required record when the index is obtained, then the partial indexing
takes less time cause it is located in a specified group.
 When the user makes a request for specific records it will find that index group first where
that specific record is recorded.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Characteristics of Indexed Sequential Search
 In Indexed Sequential Search a sorted index is set aside in
addition to the array.
 Each element in the index points to a block of elements in the
array or another expanded index.
 The index is searched 1st then the array and guides the search in
the array.

Note: Indexed Sequential Search actually does the indexing

multiple time (if required), like creating the index of an index.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
C code for Indexed Sequential Search

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
C code for Indexed Sequential Search

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Indexed Sequential Search
 Advantages of Indexed Sequential Search
 Faster than pure Sequential Search (Index reduces
search space)
 Efficient for large datasets
 Good for disk-based searching (e.g., database records)
 Disadvantages of Indexed Sequential Search
 Needs extra space for the index table
 Slower than Binary Search for sorted arrays
 Does not work well for frequently changing data

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Bubble Sort
 Bubble sort is a sorting algorithm that compares two adjacent elements
and swaps them if they are not in the intended order.
 Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
1. First Iteration (Compare and Swap)
 Starting from the first index, compare the first and the second elements.
 If the first element is greater than the second element, they are swapped.
 Now, compare the second and the third elements. Swap them if they are
not in order.
 The above process goes on until the last element.
2. Remaining Iteration
 The same process goes on for the remaining iterations.
 After each iteration, the largest element among the unsorted elements is
placed at the end.
Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT
Department, KIET Ghaziabad)
 Bubble Sort
• In each iteration, the comparison takes place up to the last unsorted
element.
• The array is sorted when all the unsorted elements are placed at
their correct positions.
• Worst case complexity of Bubble sort is O(n2).

• ALGORITHM

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Bubble Sort (Source Code)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Insertion Sort
• Insertion sort is a sorting algorithm that places an
unsorted element at its suitable place in each iteration.
• Insertion sort works similarly as we sort cards in our hand
in a card game.
 We assume that the first card is already sorted then, we
select an unsorted card. If the unsorted card is greater than
the card in hand, it is placed on the right otherwise, to the
left. In the same way, other unsorted cards are taken and
put in their right place.
 A similar approach is used by insertion sort.
 Worst case complexity of insertion sort is O(n2).

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Working of Insertion Sort
1. The first element in the array is assumed to be sorted. Take the
second element and store it separately in key.
Compare key with the first element. If the first element is
greater than key, then key is placed in front of the first
element.
2. Now, the first two elements are sorted.
3. Take the third element and compare it with the elements on
the left of it. Placed it just behind the element smaller than it.
If there is no element smaller than it, then place it at the
beginning of the array.
4. Similarly, place every unsorted element at its correct position.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Insertion Sort Algorithm

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Insertion Sort (Source Code)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Selection Sort
 Selection sort is a sorting algorithm that selects the smallest element from
an unsorted list in each iteration and places that element at the beginning
of the unsorted list.
 Worst case complexity of selection sort is O(n2).
 Working of Selection Sort
1. Set the first element as minimum.
2. Compare minimum with the second element. If the second element is
smaller than minimum, assign the second element
as minimum.Compare minimum with the third element. Again, if the
third element is smaller, then assign minimum to the third element
otherwise do nothing. The process goes on until the last element.
3. After each iteration, minimum is placed in the front of the unsorted list.
4. For each iteration, indexing starts from the first unsorted element. Step
1 to 3 are repeated until all the elements are placed at their correct
positions.
Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT
Department, KIET Ghaziabad)
Selection Sort Algorithm

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Selection Sort (Source Code)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 QUICK SORT (partition exchange sort)
 It makes O(n log n) comparisons in the average case and
O(n2) comparisons in worst case.
 Its efficient implementation can minimize the
probability of requiring quadratic time.
 It uses divide-and-conquer strategy to divide a single
unsorted array into two smaller sub-arrays.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 QUICK SORT Working
1. Select an element pivot from the array elements.
2. Rearrange the elements in the array in such a way that
all elements that are less than the pivot appear before
the pivot and all elements greater than the pivot
element come after it. After such a partitioning, the
pivot is placed in its final position. This is called the
partition operation.
3. Recursively sort the two sub-arrays thus obtained.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 QUICK SORT Variations
 There are multiple implementations of QuickSort in C,
depending on how the pivot is chosen and how
partitioning is done.
 Here are some common variations:
1. Hoare Partition Scheme (Implementation-1)
 Uses two pointers moving toward each other.
 Usually faster than Lomuto because it does fewer
swaps.
 More efficient and handles sorted input better.
2. Lomuto Partition Scheme (Implementation-2)
 Always picks the last element as the pivot.
Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT
Department, KIET Ghaziabad)
Quick Sort Example (Implementation-1)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-1)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-1)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-1)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-1)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-1)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Quick Sort Example (Implementation-2)

 In first round, we have to rearrange this array as

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-2)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-2)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-2)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-2)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-2)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example (Implementation-2)

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Complexity of Quick Sort
 In the average case, the running time of quick sort can be given as
O(n log n).
 Practically, the efficiency of quick sort depends on the element
which is chosen as the pivot. Its worst-case efficiency is given as
O(n2).
 The worst case occurs when the array is already sorted (either
in ascending or descending order) and the left most element is
chosen as the pivot.
 However, many implementations randomly choose the pivot
element. The randomized version of the quick sort algorithm
always has an algorithmic complexity of O(n log n).

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Quick Sort Example

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Merge Sort
 Based on the principle of Divide and Conquer Algorithm.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 Merge Sort
 For ease of understanding, we have taken two sub-lists each containing
four elements.

 Compare ARR[I] and ARR[J], the smaller of the two is placed in TEMP at
the location specified by INDEX and subsequently the value I or J is
incremented.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
Merge Sort

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 It uses a function merge
which combines the sub-
arrays to form a sorted array.
While the merge sort
algorithm recursively divides
the list into smaller lists, the
merge algorithm conquers
the list to sort the elements
in individual lists. Finally, the
smaller lists are merged to
form one list.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
 The running time of merge sort in the average case and the worst
case can be given as O(n log n). Although merge sort has an
optimal time complexity, it needs an additional space of O(n) for
the temporary array TEMP.

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)
C Code for Merge Sort

Data Structures using C (Mr Deepak Vishwakarma, Assistant Professor, IT

Department, KIET Ghaziabad)