Data Structures

Searching & Sorting

Data Structures 1/32

Content
s
Searching 3
Linear 4
Search 7
Binary 1
Search 1
Indexed Sequential 1
Search Hashing 3

Sorting 1
9
Insertion
2
Sort Bubble 0
Sort 2
Selection 2
Sort Quick 2
Sort Merge 4
Searching & Sorting Data Structures 2/32
Searchin
g Searching algorithms are essential tools in computer
science used to locate specific items within a collection
of data. These algorithms are designed to efficiently
navigate through data structures to find the desired
information, making them fundamental in various
applications such as databases, web search engines, and
more.
Different searching algorithms are:
► Linear Search
► Binary Search
► Indexed Sequential Search
► Hashing

Searching & Sorting Data Structures 3/32

Linear
Search
Linear search is a method for searching for an element in
a collection of elements. Each element of the collection
is visited one by one in a sequential fashion to find the
desired element. Linear search is also known as
sequential search.
Linear Search Algorithm:
► Every element is considered as a potential match
for the key and checked for the same.
► If any element is equal to the key, the search is
successful and the index of that element is returned.
► If no element is found equal to the key, the search
yields “No match found”.

Searching & Sorting Data Structures 4/32

 Figure: Linear Search using
Iteration
Searching & Sorting Data Structures 5/32
 Figure: Linear Search using
Recursion

Searching & Sorting Data Structures 6/32

Binary
Search
Binary search is a search algorithm used to find the
position of a target value within a sorted array. It works
by repeatedly dividing the search interval in half until
the target value is found or the interval is empty. The
search interval is halved by comparing the target
element with the middle value of the search space.
Conditions to apply Binary Search
► The data structure must be sorted.
► Access to any element of the data structure
should take constant time.
Binary Search Algorithm:
► Divide the search space into two halves by finding
the middle index “mid”.
► Compare the middle element of the search space
with the key.
Searching & Sorting Data Structures 7/32
 ► If the key is found at middle element, the
process is terminated.
► If the key is not found at middle element, choose
which half will be used as the next search space.
► If the key is smaller than the middle element, then the
left side is used for next search.
► If the key is larger than the middle element, then the
right side is used for next search.
► This process is continued until the key is found or
the total search space is exhausted.

Searching & Sorting Data Structures 8/32

 Figure: Binary Search using
Iteration

Searching & Sorting Data Structures 9/32

 Figure: Binary Search using
Recursion

Searching & Sorting Data Structures 10/32

Indexed Sequential
Search
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
because 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.
Characteristics:
► 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.
Searching & Sorting Data Structures 11/32
 Indexed Sequential Search actually does the indexing
multiple time, like creating the index of an index.

Figure: Indexed Sequential

Search

Searching & Sorting Data Structures 12/32

Hashin
g Hashing is a technique used in data structures that
efficiently stores and retrieves data in a way that
allows for quick access.
-Hashing refers to the process of generating a fixed-
size output from an input of variable size using the
mathematical formulas known as hash functions.
-This technique determines an index or location for the
storage of an item in a data structure. - It involves
mapping data to a specific index in a hash table using a
hash function that enables fast retrieval of information
based on its key.
-This method is commonly used in databases,
caching systems, and various programming
applications to optimize search and retrieval
operations.
Searching-The great thing about hashing is, Data
& Sorting weStructures
can achieve
13/32
 Components of Hashing: There are majorly three
components of hashing:
1. Key: A Key can be anything string or integer which
is fed as input in the hash function the technique
that determines an index or location for storage of
an item in a data structure.
2. Hash Function: The hash function receives the input
key and returns the index of an element in an array
called a hash table. The index is known as the hash
index.
3. Hash Table: Hash table is a data structure that
maps keys to values using a special function called a
hash function. Hash stores the data in an
associative manner in an array where each data
value has its own unique index.

Searching & Sorting Data Structures 14/32

 Collision: in Hashing occurs when two different keys
map to the same hash value.
- The hashing process generates a small number for a
big key, so there is a possibility that two keys could
-The situation
produce the same
where
value.
the newly inserted key maps to
an already occupied key value then it must be handled
using some collision handling technology.
Causes of Hash Collisions:
► Poor Hash Function: A hash function that does not
distribute keys evenly across the hash table can lead
to more collisions.
► High Load Factor: A high load factor (ratio of keys
to hash table size) increases the probability of
collisions.
► Similar Keys: Keys that are similar in value or
structure are more likely to collide.
- & Sorting
Searching Data Structures 21/32
 ► Open Addressing:
Linear Probing: Search for an empty slot sequentially
Quadratic Probing: Search for an empty slot using a
quadratic function
► Closed Addressing:
Chaining: Store colliding keys in a linked list or
binary search tree at each index
Applications of Hashing: Hash tables are used wherever
we have a combinations of search, insert and/or delete
operations.
► Dictionaries: To implement a dictionary so that
we can quickly search a word.

Searching & Sorting Data Structures 23/32

a) Linear Probing
In linear probing, the hash table is searched sequentially that starts from the original location of the
hash. If in case the location that we get is already occupied, then we check for the next location.
 ► Databases: Hashing is used in database indexing.
There are two popular ways to implement indexing,
search trees (B or B+ Tree) and hashing.
► Cryptography: When we create a password on a
website, they typically store it after applying a hash
function rather than plain text.
► Caching: Storing frequently accessed data for faster
retrieval. For example browser caches, we can use
URL as keys and find the local storage of the URL.
► Symbol Tables: Mapping identifiers to their
values in programming languages
► Network Routing: Determining the best path
for data packets

Searching & Sorting Data Structures 30/32

 ► Associative Arrays: Associative arrays are nothing
but hash tables only. Commonly SQL library functions
allow you retrieve data as associative arrays so that
the retrieved data in RAM can be quickly searched
for a key.

Searching & Sorting Data Structures 31/32

Sorting
A Sorting Algorithm is used to rearrange a given array or
list of elements according to a comparison operator on
the elements. The comparison operator is used to decide
the new order of elements in the respective data
structure. For example arranging students acoording to
hight in morning assembly, seating roll no wise in exams,
arranging names marks wise in merit list etc. There are
different algorithms for sorting:
► Insertion Sort
► Bubble Sort
► Selection Sort
► Quick Sort
► Merge Sort

Searching & Sorting Data Structures 36/32

Insertion
Sort►
Insertion sort is a simple sorting algorithm that
works by iteratively inserting each element of an
unsorted list into its correct position in a sorted
portion of the list.
► It is a stable sorting algorithm, meaning that
elements with equal values maintain their relative
order in the sorted output.
► Insertion sort is like sorting playing cards in your
hands.
► You split the cards into two groups: the sorted cards
and the unsorted cards.
► Then, you pick a card from the unsorted group and
put it in the right place in the sorted group.

Searching & Sorting Data Structures 37/32

 Figure: Insertion
Sort

Searching & Sorting Data Structures 38/32

Bubble
Sort
Bubble Sort is the simplest sorting algorithm that works
by repeatedly swapping the adjacent elements if they are
in the wrong order. This algorithm is not suitable for
large data sets as its average and worst-case time
complexity is quite high.
Algorithm:
► traverse from left and compare adjacent elements
and the higher one is placed at right side.
► In this way, the largest element is moved to the
rightmost end at first.
► This process is then continued to find the second
largest and place it and so on until the data is
sorted.

Searching & Sorting Data Structures 39/32

 Figure: Bubble
Sort

Searching & Sorting Data Structures 40/32

Selection
Sort►
Selection sort is a simple and efficient sorting
algorithm that works by repeatedly selecting the
smallest (or largest) element from the unsorted
portion of the list and moving it to the sorted portion
of the list.
► The algorithm repeatedly selects the smallest (or
largest) element from the unsorted portion of the
list and swaps it with the first element of the
unsorted part.
► This process is repeated for the remaining
unsorted portion until the entire list is sorted.

Searching & Sorting Data Structures 41/32

 Figure: Selection
Sort
Searching & Sorting Data Structures 42/32
Quick
Sort►
QuickSort is a sorting algorithm based on the Divide
and Conquer that picks an element as a pivot and
partitions the given array around the picked pivot by
placing the pivot in its correct position in the sorted
array.
► There are mainly three steps in the algorithm.
► 1. Choose a pivot
► 2. Partition the array around pivot. After partition, it
is ensured that all elements are smaller than all right
and we get index of the end point of smaller
elements. The left and right may not be sorted
individually.
► 3. Recursively call for the two partitioned left and
right subarrays. We stop recursion when there is
only one element is left.
Searching & Sorting Data Structures 43/32
Searching & Sorting Data Structures 44/32
 Figure: Quick
Sort

Searching & Sorting Data Structures 45/32

Merge
Sort►
Merge sort is a sorting algorithm that
follows the divide-and-conquer approach.
► It works by recursively dividing the input array into
smaller subarrays and sorting those subarrays then
merging them back together to obtain the sorted
array.
► In simple terms, the process of merge sort is to
divide the array into two halves, sort each half,
and then merge the sorted halves back together.
► This process is repeated until the entire array is
sorted.

Searching & Sorting Data Structures 46/32

Data Structures 49/32
Figure: Merge
Sort

Data Structures 50/32

Thank
you

Data Structures 54/32