Searching and

Sorting Techniques
 Searching
Searching Algorithms are a family of algorithms
used for the purpose of searching. The searching
of an element in the given array may be carried
out in the following two ways-
1.Linear Search
2.Binary Search
 Linear Search
➢ Linear Search is the simplest searching algorithm.
➢ It traverses the array sequentially to search the element.
➢ It searches for an element by comparing it with each element of
the array one by one.
➢ So, it is also called as Sequential Search.
Linear Search Algorithm is applied when
• No information is given about the array.
• The given array is unsorted or the elements are unordered.
• The list of data items is smaller.
Linear
Search:
Search
20
20 is found at index 5
 Binary Search
➢ Binary Search is one of the fastest searching algorithms.
➢ It is used for finding the location of an element in a linear sorted
array.
➢ It works on the principle of divide and conquer technique.
➢ Binary Search Algorithm can be applied only on Sorted arrays.
➢ To apply binary search on an unsorted array,
➢ • First, sort the array using some sorting technique.
➢ • Then, use binary search algorithm.
 Binary Search
➢ Case 1: If the element being searched is found to be the middle
most element, its index is returned.
➢ Case 2: If the element being searched is found to be greater than
the middle most element, then its search is continued in the right
sub array of the middle most element.
➢ Case 3: If the element being searched is found to be smaller than
the middle most element, then its search is continued in the left
sub array of the middle most element.
➢ Repeat until the desired element is found or size of the sub array
reduces to zero.
Binary Search Middle = (First + Last)/2

23 is found at index 5
 Sorting
➢ Sorting is a technique to rearrange the elements
of a list in ascending or descending order,
which can be numerical, lexicographical, or any
user-defined order.
➢ Sorting can be classified into two types
• Internal Sorting
• External Sorting
 Internal Sorting
➢ Internal Sorting method uses only the primary memory
during sorting process. All data items are held in main
memory and no secondary memory is required for sorting
process.
Limitation
➢ whole data must be sorted in internal memory during
internal sorting.
Examples
➢ (i) Selection Sort : Ex:- Selection and Heap Sort algorithm
➢ (ii) Insertion Sort :Ex:- Insertion and Shell Sort algorithm
➢ (iii) Exchange Sort : Ex:- Bubble and Quick sort algorithm
 External Sorting
➢ External Sorting sorts large amount of data which does
not fit in main memory. This process requires external or
secondary memory, such as HDD, to store the data.
➢ So, primary memory holds the data that is currently being
sorted only.
➢ All external sorts are based on process of merging.
Different parts of data are sorted separately and merged
together.
Example:
➢ Merge Sort
Bubble sort
• Bubble sort is a very simple sorting method that sorts the array
elements by repeatedly moving the largest element to the highest
index position of the array segment.
• In general, it takes (n-1) iterations in order to sort a given array using
the bubble sort algorithm, where n is the number of elements in the
array.
Bubble sort
• 1. Compare pair of adjacent items from an array of given “n” items
• 2. Swap if the items are out of order
• 3. Reduce n by 1 and repeat Steps 1 to 3.
• 4. Repeat until the end of array - The largest item will be at the last
position
Single
pass in
Bubble
Sort
Bubble sort
• Example:
• Let us consider an array A[ ] that has the following elements:
• A[ ] = { 3, 6, 4, 7, 2 }. Perform Bubble sort.
Bubble sort

Iteration 1
Bubble sort

Iteration 2
Bubble sort

Iteration 3
Bubble sort

Iteration 4 The sorted

list is
2, 3, 4, 6, 7
Selection sort
• The name, Selection Sort, comes from the idea of selecting the smallest
element from those elements not yet sorted. The smallest element is
then swapped with the first unsorted element.
• In general, it takes (n-1) iterations in order to sort a given array using
the bubble sort algorithm, where n is the number of elements in the
array.
Selection sort
• 1.The list is divided into sorted and unsorted list.
• 2.Find the smallest element from the unsorted list and swap it with the
first element of the unsorted list.
• 3. Increase the number of sorted elements and decrease the number of
unsorted elements.
• 4. Repeat steps 2 to 4, n-1 number of times.
Selection
Sort

The sorted list

is
4, 5, 9, 31, 51
Selection sort Example 2:
• Example:
• Let us consider an array A[ ] that has the following elements:
• A[ ] = { 5, 1, 4, 2, 8 }. Perform Selection sort.
 Selection sort
Example 2:
The sorted
list is
1, 2, 4, 5, 8
Insertion sort
• Insertion sort inserts each item into its proper place in each iteration.
• The sorted array (or list) is built one element at a time.
• We all are familiar with this technique of sorting, as we usually use it
for ordering a deck of cards while playing cards.
• In general, it takes (n-1) iterations in order to sort a given array using
the bubble sort algorithm, where n is the number of elements in the
array.
Insertion sort
• 1. The list is divided into sorted and unsorted list.
• 2. The first element in the unsorted list is picked up and inserted into
the correct position in the sorted set.
• 3. Increase the number of sorted elements and decrease the number of
unsorted elements.
• 4. Repeat Steps 2 to 4, n-1 number of times.
Insertion sort

The sorted
list is
8, 23, 32, 45, 56, 78
Insertion sort Example 2:
• Example:
• Let us consider an array A[ ] that has the following elements:
• A[ ] = { 8, 2, 15, 32, 22 }. Perform Insertion sort.
Insertion sort
Example 2:
The sorted
list is
2, 8, 15, 32, 22
 Merge Sort
• Merge Sort is a Divide and Conquer algorithm.
Divide and Conquer Strategy
• Divide a problem into subproblems.
• Find the solution of each subproblem.
• When the solution to each subproblem is ready,
'combine' the results from the subproblems to solve the
main problem.
 Merge Sort
➢ Divide - If q is the half-way point between p and r,
then we can split the subarray A[p..r] into two arrays
A[p..q] and A[q+1, r].
➢ Conquer - In the conquer step, we try to sort both the
subarrays A[p..q] and A[q+1, r]. If we haven't yet reached
the base case, again divide and try to sort them.
➢ Combine - When the conquer step reaches the base
step, combine the results by creating a sorted array
A[p..r] from two sorted subarrays A[p..q] and A[q+1, r]
Merge sort

The sorted
list is
1, 1, 2, 3, 4, 5, 6
 Quick Sort
➢ Quicksort is a divide-and-conquer algorithm.
➢ It works by selecting a 'pivot' element from the
array and partitioning the other elements into two
sub-arrays, according to whether they are less than
or greater than the pivot.
➢ It is sometimes called partition-exchange sort
➢ The sub-arrays are then sorted recursively.
 Quick Sort
➢ Pivot selection: Pick an element, called pivot, from the
array (usually the leftmost or the rightmost element of the
list).
➢ Partitioning: Reorder the array such that all elements with
values less than the pivot come before the pivot and all
elements with values greater than the pivot come after it.
After this partitioning, the pivot is in its final position.
➢ Recursion: Recursively apply the above steps to the sub
arrays.
Single
pass in
Quick
Sort
 51, 98, 23, 84, 29, 68, 44, 16, 84

Single
Pivot i j

pass in 51, 98, 23, 84, 29, 68, 44, 16, 84

Pivot i j [ swap i and j ]

Quick
51, 16, 23, 84, 29, 68, 44, 98, 84
Sort Pivot i j [ swap i and j ]
Single 51, 16, 23, 44, 29, 68, 84, 98, 84

pass in Pivot j i [ i and j crossed

swap Pivot and j ]

Quick
29, 16, 23, 44, 51, 68, 84, 98, 84
Sort Now numbers smaller than Pivot are before Pivot 51
and numbers greater than Pivot are after 51.
 Quick Sort
➢ Pivot selection: Pick an element, called a pivot,
from the array (usually the leftmost or the
rightmost element of the partition).
➢ Partitioning: Reorder the array such that all
elements with values less than the pivot come
before the pivot. In contrast, all elements with
values greater than the pivot come after it. After
this partitioning, the pivot is in its final position.
➢ Recursion: Recursively apply the above steps to
the smaller values sub array and greater values
sub array.
Quick Sort
51, 98, 23, 84, 29, 68, 44, 16, 84 Pass 1

Pivot

29, 16, 23, 44, 51, 68, 84, 98, 84 Pass 2

Pivot

23, 16, 29, 44, 51, 68, 84, 98, 84 Pass 3

Pivot
Quick Sort
23, 16, 29, 44, 51, 68, 84, 98, 84 Pass 4
Pivot

23, 16, 29, 44, 51, 68, 84, 98, 84 Pass 5

Pivot

23, 16, 29, 44, 51, 68, 84, 84, 98

The sorted list is

23, 16, 29, 44, 51, 68, 84, 84, 98
 Shell Sort
➢ Shell Sort Algorithm introduces a gap in the
sorting process which quickly reduces the
amount of disorder in the array compared to
the insertion sort algorithm.
➢ In Insertion sort, the value of the gap is one.
That’s why in insertion sort we compare an
array element with its adjacent element of 1
index far way.
 Shell Sort
➢ But in shell sort instead of comparing the values
one index away, we compare values with the
index difference of gap=length/2 and decrease
the gap value successively.
➢ Beginning with a large gap value leaves less
work for smaller gap values to finish the sorting
process.
➢ When the gap reduces to 1, the shell sort
behaves as insertion sort.
 Gap = no of elts / 2
Shell Sort =8/2.
Gap = 4

12 17 25 33 31 40
 Gap = Gap / 2
Shell Sort =4/2.
Gap = 2

8 17
Shell Sort

Gap = Gap / 2
=2/2.
Gap = 1
Perform Insertion Sort
 Shell Sort

The sorted list is

8, 12, 17, 25, 31, 33, 40, 42
 Complexity Analysis
Shell
Bubble Selection Insertion Merge Quick
Complexity Sort
Sort Sort Sort Sort Sort

Time O(n log n 2)

O(n2) O(n2) O(n) O(n log n) O(n log n)
Complexity
Space O(1) O(1) O(1) O(n) O(1) O(1)
Complexity
For doubts contact
me at
9578784476
Happy X-mas and
Happy New Year