B. TECH.

/CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

BCS-301: DATA STRUCTURE

UNIT III:

Searching: Concept of Searching, Sequential search, Index Sequential Search, Binary-search. Concept of
Hashing & Collision resolution Techniques used in Hashing.
Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort.
Introduction to Searching -
Searching is the fundamental process of locating a specific element or item within a collection of data.
This collection of data can take various forms, such as arrays, lists, trees, or other structured
representations.
The primary objective of searching is to determine whether the desired element exists within the data, and
if so, to identify its precise location or retrieve it. It plays an important role in various computational tasks
and real-world applications, including information retrieval, data analysis, decision-making processes, and
more.
Importance of Searching in DSA
 Efficiency: Efficient searching algorithms improve program performance.
 Data Retrieval: Quickly find and retrieve specific data from large datasets.
 Database Systems: Enables fast querying of databases.
 Problem Solving: Used in a wide range of problem-solving tasks.

Characteristics of Searching
Understanding the characteristics of searching in data structures and algorithms is crucial for designing
efficient algorithms and making informed decisions about which searching technique to employ. Here, we
explore key aspects and characteristics associated with searching:
1. Target Element:
In searching, there is always a specific target element or item that you want to find within the data
collection. This target could be a value, a record, a key, or any other data entity of interest.
2. Search Space:
The search space refers to the entire collection of data within which you are looking for the target element.
Depending on the data structure used, the search space may vary in size and organization.
3. Complexity:
Searching can have different levels of complexity depending on the data structure and the algorithm used.
The complexity is often measured in terms of time and space requirements.
4. Deterministic vs Non-deterministic:
Some searching algorithms, like binary search, are deterministic, meaning they follow a clear and
systematic approach. Others, such as linear search, are non-deterministic, as they may need to examine the
entire search space in the worst case.
Applications of Searching:
Searching algorithms have numerous applications across various fields. Here are some common
applications:
 Information Retrieval: Search engines like Google, Bing, and Yahoo use sophisticated searching
algorithms to retrieve relevant information from vast amounts of data on the web.
 Database Systems: Searching is fundamental in database systems for retrieving specific data
records based on user queries, improving efficiency in data retrieval.

Page 1 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

 E-commerce: Searching is crucial in e-commerce platforms for users to find products quickly
based on their preferences, specifications, or keywords.
 Networking: In networking, searching algorithms are used for routing packets efficiently through
networks, finding optimal paths, and managing network resources.
 Artificial Intelligence: Searching algorithms play a vital role in AI applications, such as problem-
solving, game playing (e.g., chess), and decision-making processes
 Pattern Recognition: Searching algorithms are used in pattern matching tasks, such as image
recognition, speech recognition, and handwriting recognition.
Searching Algorithms:
Searching Algorithms are designed to check for an element or retrieve an element from any data structure
where it is stored.
Below are some searching algorithms:
1. Linear Search
2. Binary Search
3. Jump Search
4. Ternary Search
5. Interpolation Search
6. Fibonacci Search
7. Exponential Search
1. Linear Search:
Linear Search, also known as Sequential Search, is one of the simplest and most straightforward searching
algorithms. It works by sequentially examining each element in a collection of data(array or list) until a
match is found or the entire collection has been traversed.

Linear Search

Algorithm of Linear Search:

 The Algorithm examines each element, one by one, in the collection, treating each element as a
potential match for the key you're searching for.
 If it finds any element that is exactly the same as the key you're looking for, the search is
successful, and it returns the index of key.
 If it goes through all the elements and none of them matches the key, then that means "No match is
Found".

Illustration of Linear Search:

Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30

Page 2 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Start from the first element (index 0) and compare key with each element (arr[i]).
Comparing key with first element arr[0]. Since not equal, the iterator moves to the next
element as a potential match.
Comparing key with next element arr[1]. Since not equal, the iterator moves to the next
element as a potential match
.

Now when comparing arr[2] with key, the value matches. So the Linear Search Algorithm
will yield a successful message and return the index of the element when key is found.

Pseudo Code for Linear Search:

LinearSearch(collection, key):
for each element in collection:
if element is equal to key:
return the index of the element
return "Not found"
Complexity Analysis of Linear Search:
 Time Complexity:
o Best Case: In the best case, the key might be present at the first index. So the best case
complexity is O(1)
o Worst Case: In the worst case, the key might be present at the last index i.e., opposite to
the end from which the search has started in the list. So the worst-case complexity is O(N)
where N is the size of the list.
Page 3 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

o Average Case: O(N)

 Auxiliary Space: O(1) as except for the variable to iterate through the list, no other variable is
used.
When to use Linear Search:
 When there is small collection of data.
 When data is unordered.
2. Binary Search:
Binary Search is defined as a searching algorithm used in a sorted array by repeatedly dividing the search
interval in half. The idea of binary search is to use the information that the array is sorted and reduce the
time complexity to O(log N).

Binary Search Algorithm

Algorithm of Binary Search:
 Divide the search space into two halves by finding the middle index “mid”.
 Compare the middle element of the search space with the key.
 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.
o If the key is smaller than the middle element, then the left side is used for next search.
o 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.
Illustration of Binary Search:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.
 Calculate the mid and compare the mid element with the key. If the key is less than mid
element, move to left and if it is greater than the mid then move search space to the
right.
 Key (i.e., 23) is greater than current mid element (i.e., 16). The search space moves to
the right.
Page 4 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

 Key is less than the current mid 56. The search space moves to the left.

 If the key matches the value of the mid element, the element is found and stop search.

Pseudo Code for Binary Search:

Below is the pseudo code for implementing binary search:
binarySearch(collection, key):
left = 0
right = length(collection) - 1
while left <= right:
mid = (left + right) // 2
if collection[mid] == key:
return mid
elif collection[mid] < key:
left = mid + 1
else:
right = mid - 1

Page 5 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

return "Not found"

Complexity Analysis of Binary Search:
 Time Complexity:
o Best Case: O(1) - When the key is found at the middle element.
o Worst Case: O(log N) - When the key is not present, and the search space is continuously halved.
o Average Case: O(log N)
 Auxiliary Space: O(1)
When to use Binary Search:
 When the data collection is monotonic (essential condition) in nature.
 When efficiency is required, specially in case of large datasets.

3.Jump Search/Index Sequential Search:

Jump Search is another searching algorithm that can be used on sorted collections (arrays
or lists). The idea is to reduce the number of comparisons by jumping ahead by fixed steps
or skipping some elements in place of searching all elements.
Illustration of Jump Search:
Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
610).
The length of the array is 16. The Jump search will find the value of 55 with the following
steps assuming that the block size to be jumped is 4.
 Jump from index 0 to index 4;
 Jump from index 4 to index 8;
 Jump from index 8 to index 12;
 Since the element at index 12 is greater than 55, we will jump back a step to come to
index 8.
 Perform a linear search from index 8 to get the element 55.
Time Complexity of Jump Search:
 Time Complexity: O(√n), where "n" is the number of elements in the collection. This makes it
more efficient than Linear Search but generally less efficient than Binary Search for large datasets.
 Auxiliary Space: O(1), as it uses a constant amount of additional space for variables.

Performance Comparison based on Complexity:

linear search < jump search < binary search

Collision Resolution Techniques

In Hashing, hash functions were used to generate hash values. The hash value is used to create an index
for the keys in the hash table. The hash function may return the same hash value for two or more keys.
When two or more keys have the same hash value, a collision happens. To handle this collision, we
use Collision Resolution Techniques.

Page 6 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Collision Resolution Techniques

There are mainly two methods to handle collision:
1. Separate Chaining
2. Open Addressing

Page 7 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

1) Separate Chaining

The idea behind Separate Chaining is to make each cell of the hash table point to a linked list of records
that have the same hash function value. Chaining is simple but requires additional memory outside the
table.
Example: We have given a hash function and we have to insert some elements in the hash table using a
separate chaining method for collision resolution technique.
Hash function = key % 5,
Elements = 12, 15, 22, 25 and 37.
Let’s see step by step approach to how to solve the above problem:

1/5
Hence In this way, the separate chaining method is used as the collision resolution technique.
2) Open Addressing

In open addressing, all elements are stored in the hash table itself. Each table entry contains either a record

Page 8 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

or NIL. When searching for an element, we examine the table slots one by one until the desired element is
found or it is clear that the element is not in the table.
2.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.
Algorithm:
1. Calculate the hash key. i.e. key = data % size
2. Check, if hashTable[key] is empty
 store the value directly by hashTable[key] = data
3. If the hash index already has some value then
 check for next index using key = (key+1) % size
4. Check, if the next index is available hashTable[key] then store the value. Otherwise try
for next index.
5. Do the above process till we find the space.
Example: Let us consider a simple hash function as “key mod 5” and a sequence of keys that are to be
inserted are 50, 70, 76, 85, 93.

1/6

Page 9 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

2.b) Quadratic Probing

Quadratic probing is an open addressing scheme in computer programming for resolving hash collisions in
hash tables. Quadratic probing operates by taking the original hash index and adding successive values of
an arbitrary quadratic polynomial until an open slot is found.
An example sequence using quadratic probing is:
H + 1 2 , H + 2 2 , H + 3 2 , H + 4 2 …………………. H + k 2
This method is also known as the mid-square method because in this method we look for i2-th probe (slot)
in i-th iteration and the value of i = 0, 1, . . . n – 1. We always start from the original hash location. If only
the location is occupied then we check the other slots.
Let hash(x) be the slot index computed using the hash function and n be the size of the hash table.
If the slot hash(x) % n is full, then we try (hash(x) + 1 2 ) % n.
If (hash(x) + 1 2 ) % n is also full, then we try (hash(x) + 2 2 ) % n.
If (hash(x) + 2 2 ) % n is also full, then we try (hash(x) + 3 2 ) % n.
This process will be repeated for all the values of i until an empty slot is found
Example: Let us consider table Size = 7, hash function as Hash(x) = x % 7 and collision resolution
strategy to be f(i) = i 2 . Insert = 22, 30, and 50

1/4
Page 10 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

2.c) Double Hashing

Double hashing is a collision resolving technique in Open Addressed Hash tables. Double hashing make
use of two hash function,
 The first hash function is h1(k) which takes the key and gives out a location on the hash table. But
if the new location is not occupied or empty then we can easily place our key.
 But in case the location is occupied (collision) we will use secondary hash-function h2(k) in
combination with the first hash-function h1(k) to find the new location on the hash table.
This combination of hash functions is of the form
h(k, i) = (h1(k) + i * h2(k)) % n
where
 i is a non-negative integer that indicates a collision number,
 k = element/key which is being hashed
 n = hash table size.
Complexity of the Double hashing algorithm:
Time complexity: O(n)
Example: Insert the keys 27, 43, 692, 72 into the Hash Table of size 7. where first hash-function
is h1​ (k) = k mod 7 and second hash-function is h2(k) = 1 + (k mod 5)

4/5
Page 11 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Join GfG 160, a 160-day journey of coding challenges aimed at sharpening your skills. Each day, solve a
handpicked problem, dive into detailed solutions through articles and videos, and enhance your
preparation for any interview—all for free! Plus, win exciting GfG goodies along the way! - Explore Now

Open Addressing Collision Handling technique in Hashing

Open Addressing is a method for handling collisions. In Open Addressing, all elements are stored in
the hash table itself. So at any point, the size of the table must be greater than or equal to the total number
of keys (Note that we can increase table size by copying old data if needed). This approach is also known
as closed hashing. This entire procedure is based upon probing. We will understand the types of probing
ahead:
 Insert(k): Keep probing until an empty slot is found. Once an empty slot is found, insert
k.
 Search(k): Keep probing until the slot’s key doesn’t become equal to k or an empty slot
is reached.
 Delete(k): Delete operation is interesting. If we simply delete a key, then the search
may fail. So slots of deleted keys are marked specially as “deleted”.
The insert can insert an item in a deleted slot, but the search doesn’t stop at a deleted
slot.
Different ways of Open Addressing:

1. 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.
The function used for rehashing is as follows: rehash(key) = (n+1)%table-size.
For example, The typical gap between two probes is 1 as seen in the example below:
Let hash(x) be the slot index computed using a hash function and S be the table size
If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S
Example: Let us consider a simple hash function as “key mod 5” and a sequence of keys that are to be
inserted are 50, 70, 76, 85, 93.

Page 12 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

1/6
Implementation : Please refer Program to implement Hash Table using Open Addressing
2. Quadratic Probing
If you observe carefully, then you will understand that the interval between probes will increase
proportionally to the hash value. Quadratic probing is a method with the help of which we can solve the
problem of clustering that was discussed above. This method is also known as the mid-square method. In
this method, we look for the i2‘th slot in the ith iteration. We always start from the original hash location.
If only the location is occupied then we check the other slots.
let hash(x) be the slot index computed using hash function.
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S
Example: Let us consider table Size = 7, hash function as Hash(x) = x % 7 and collision resolution
strategy to be f(i) = i2 . Insert = 22, 30, and 50.
Page 13 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

1/4
Implementation : Please refer Program for Quadratic Probing in Hashing

3. Double Hashing

The intervals that lie between probes are computed by another hash function. Double hashing is a
technique that reduces clustering in an optimized way. In this technique, the increments for the probing
sequence are computed by using another hash function. We use another hash function hash2(x) and look
for the i*hash2(x) slot in the ith rotation.
let hash(x) be the slot index computed using hash function.
If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S
If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S
If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S
Example: Insert the keys 27, 43, 692, 72 into the Hash Table of size 7. where first hash-function
is h1​ (k) = k mod 7 and second hash-function is h2(k) = 1 + (k mod 5)

Page 14 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

2/5
Comparison of the above three:
Open addressing is a collision handling technique used in hashing where, when a collision occurs (i.e.,
when two or more keys map to the same slot), the algorithm looks for another empty slot in the hash table
to store the collided key.
 In linear probing, the algorithm simply looks for the next available slot in the hash table and
places the collided key there. If that slot is also occupied, the algorithm continues searching for the
next available slot until an empty slot is found. This process is repeated until all collided keys have
been stored. Linear probing has the best cache performance but suffers from clustering. One more
advantage of Linear probing is easy to compute.
 In quadratic probing, the algorithm searches for slots in a more spaced-out manner. When a
collision occurs, the algorithm looks for the next slot using an equation that involves the original hash
value and a quadratic function. If that slot is also occupied, the algorithm increments the value of the
quadratic function and tries again. This process is repeated until an empty slot is found. Quadratic
probing lies between the two in terms of cache performance and clustering.

Page 15 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

 In double hashing, the algorithm uses a second hash function to determine the next slot to check
when a collision occurs. The algorithm calculates a hash value using the original hash function, then
uses the second hash function to calculate an offset. The algorithm then checks the slot that is the sum
of the original hash value and the offset. If that slot is occupied, the algorithm increments the offset
and tries again. This process is repeated until an empty slot is found. Double hashing has poor cache
performance but no clustering. Double hashing requires more computation time as two hash functions
need to be computed.
The choice of collision handling technique can have a significant impact on the performance of a hash
table. Linear probing is simple and fast, but it can lead to clustering (i.e., a situation where keys are stored
in long contiguous runs) and can degrade performance. Quadratic probing is more spaced out, but it can
also lead to clustering and can result in a situation where some slots are never checked. Double hashing is
more complex, but it can lead to more even distribution of keys and can provide better performance in
some cases.

S.No. Separate Chaining Open Addressing

Open Addressing requires more

1. Chaining is Simpler to implement.
computation.

In chaining, Hash table never fills up, we can

2. In open addressing, table may become full.
always add more elements to chain.

Chaining is Less sensitive to the hash function or Open addressing requires extra care to avoid
3.
load factors. clustering and load factor.

Chaining is mostly used when it is unknown how

Open addressing is used when the frequency
4. many and how frequently keys may be inserted or
and number of keys is known.
deleted.

Open addressing provides better cache

Cache performance of chaining is not good as
5. performance as everything is stored in the
keys are stored using linked list.
same table.

Wastage of Space (Some Parts of hash table in In Open addressing, a slot can be used even
6.
chaining are never used). if an input doesn’t map to it.

7. Chaining uses extra space for links. No links in Open addressing

Note: Cache performance of chaining is not good because when we traverse a Linked List, we are
basically jumping from one node to another, all across the computer’s memory. For this reason, the CPU
cannot cache the nodes which aren’t visited yet, this doesn’t help us. But with Open Addressing, data isn’t
spread, so if the CPU detects that a segment of memory is constantly being accessed, it gets cached for
quick access.
Performance of Open Addressing:

Page 16 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Like Chaining, the performance of hashing can be evaluated under the assumption that each key is equally
likely to be hashed to any slot of the table (simple uniform hashing)
m = Number of slots in the hash table
n = Number of keys to be inserted in the hash table
Load factor α = n/m ( < 1 )
Expected time to search/insert/delete < 1/(1 – α)
So Search, Insert and Delete take (1/(1 – α)) time

Insertion Sort Algorithm

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 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.
Algorithm
The simple steps of achieving the insertion sort are listed as follows -

Step 1 - If the element is the first element, assume that it is already sorted. Return 1.

Step2 - Pick the next element, and store it separately in a key.

Step3 - 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.

Advertisement
Step 5 - Insert the value.

Step 6 - Repeat until the array is sorted.

Page 17 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

To deepen your understanding of sorting algorithms like insertion sort and other essential data
structures
Although it is simple to use, it is not appropriate for large data sets as the time complexity of insertion sort
in the average case and worst case is O(n2), where n is the number of items. Insertion sort is less efficient
than the other sorting algorithms like heap sort, quick sort, merge sort, etc.

Selection Sort Algorithm

Selection sort is a simple sorting algorithm. This sorting algorithm, like insertion sort, is an in-place
comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and
the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with the leftmost element, and that
element becomes a part of the sorted array. This process continues moving unsorted array boundaries by
one element to the right.

This algorithm is not suitable for large data sets as its average and worst case complexities are of O(n2),
where n is the number of items.

Selection Sort Algorithm

This type of sorting is called Selection Sort as it works by repeatedly sorting elements. That is: we first
find the smallest value in the array and exchange it with the element in the first position, then find the
second smallest element and exchange it with the element in the second position, and we continue the
process in this way until the entire array is sorted.

Page 18 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

1. Set MIN to location 0.

2. Search the minimum element in the list.
3. Swap with value at location MIN.
4. Increment MIN to point to next element.
5. Repeat until the list is sorted.

Pseudocode

Algorithm: Selection-Sort (A)

fori← 1 to n-1 do
min j ←i;
min x ← A[i]
for j ←i + 1 to n do
if A[j] < min x then
min j ← j
min x ← A[j]
A[min j] ← A [i]
A[i] ← min x

In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies
that the running time of Selection sort is quite insensitive to the input.

Example

Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially. The first position where 14 is
stored presently, we search the whole list and find that 10 is the lowest value.

Page 19 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list,
appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner.

We find that 14 is the second lowest value in the list and it should appear at the second place. We swap
these values.

After two iterations, two least values are positioned at the beginning in a sorted manner.

The same process is applied to the rest of the items in the array −

Page 20 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Page 21 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Bubble Sort Algorithm

Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging adjacent elements,
if necessary. When no exchanges are required, the file is sorted.

We assume list is an array of n elements. We further assume that swap function swaps the values of the
given array elements.

Step 1 − Check if the first element in the input array is greater than the next element in the array.

Step 2 − If it is greater, swap the two elements; otherwise move the pointer forward in the array.

Step 3 − Repeat Step 2 until we reach the end of the array.

Step 4 − Check if the elements are sorted; if not, repeat the same process (Step 1 to Step 3) from the last
element of the array to the first.

Step 5 − The final output achieved is the sorted array.

Algorithm: Sequential-Bubble-Sort (A)

fori ← 1 to length [A] do
for j ← length [A] down-to i +1 do
if A[A] < A[j-1] then
Exchange A[j] ⟷A[j-1]

Pseudocode

We observe in algorithm that Bubble Sort compares each pair of array element unless the whole array is
completely sorted in an ascending order. This may cause a few complexity issues like what if the array
needs no more swapping as all the elements are already ascending.

Page 22 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

To ease-out the issue, we use one flag variable swapped which will help us see if any swap has happened
or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of
the loop.

Pseudocode of bubble sort algorithm can be written as follows −

voidbubbleSort(int numbers[], intarray_size){

inti, j, temp;
for (i = (array_size - 1); i>= 0; i--)
for (j = 1; j <= i; j++)
if (numbers[j-1] > numbers[j]){
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}

Analysis

Here, the number of comparisons are

1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)

Clearly, the graph shows the n2 nature of the bubble sort.

In this algorithm, the number of comparison is irrespective of the data set, i.e. whether the provided input
elements are in sorted order or in reverse order or at random.

Memory Requirement

From the algorithm stated above, it is clear that bubble sort does not require extra memory.

Example

We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're keeping it short and
precise.

Bubble sort starts with very first two elements, comparing them to check which one is greater.
Page 23 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

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. Hence they are not sorted. We swap these values. We find that we
have reached the end of the array. After one iteration, the array should look like this −

Page 24 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

To be precise, 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 sort learns that an array is completely sorted.

Now we should look into some practical aspects of bubble sort.

Page 25 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Quick Sort Algorithm

In this article, we will discuss the Quicksort Algorithm. The working procedure of Quicksort is also
simple. This article will be very helpful and interesting to students as they might face quicksort as a
question in their examinations. So, it is important to discuss the topic.

Sorting is a way of arranging items in a systematic manner. Quicksort is the widely used sorting algorithm
that makes n log n comparisons in average case for sorting an array of n elements. It is a faster and highly
efficient sorting algorithm. This algorithm follows the divide and conquer approach. Divide and conquer is
a technique of breaking down the algorithms into subproblems, then solving the subproblems, and
combining the results back together to solve the original problem.

Divide: In Divide, first pick a pivot element. After that, partition or rearrange the array into two sub-arrays
such that each element in the left sub-array is less than or equal to the pivot element and each element in
the right sub-array is larger than the pivot element.

Conquer: Recursively, sort two subarrays with Quicksort.

Combine: Combine the already sorted array.

Quicksort picks an element as pivot, and then it partitions the given array around the picked pivot element.
In quick sort, a large array is divided into two arrays in which one holds values that are smaller than the
specified value (Pivot), and another array holds the values that are greater than the pivot.

After that, left and right sub-arrays are also partitioned using the same approach. It will continue until the
single element remains in the sub-array.

Choosing the pivot

Picking a good pivot is necessary for the fast implementation of quicksort. However, it is typical to
determine a good pivot. Some of the ways of choosing a pivot are as follows -

o Pivot can be random, i.e. select the random pivot from the given array.
o Pivot can either be the rightmost element of the leftmost element of the given array.
o Select median as the pivot element.

Page 26 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Algorithm:

. QUICKSORT (array A, start, end)

. {
. 1 if (start < end)
. 2{
. 3 p = partition(A, start, end)
. 4 QUICKSORT (A, start, p - 1)
. 5 QUICKSORT (A, p + 1, end)
. 6}
. }
Partition Algorithm:

The partition algorithm rearranges the sub-arrays in a place.

. PARTITION (array A, start, end)

. {
. 1 pivot ? A[end]
. 2 i ? start-1
. 3 for j ? start to end -1 {
. 4 do if (A[j] < pivot) {
. 5 then i ? i + 1
. 6 swap A[i] with A[j]
. 7 }}
. 8 swap A[i+1] with A[end]
. 9 return i+1
. }

Working of Quick Sort Algorithm

Now, let's see the working of the Quicksort Algorithm.

To understand the working of quick sort, let's take an unsorted array. It will make the concept more clear
and understandable.

Let the elements of array are -

In the given array, we consider the leftmost element as pivot. So, in this case, a[left] = 24, a[right] = 27
and a[pivot] = 24.

Since, pivot is at left, so algorithm starts from right and move towards left.
Page 27 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -

Advertisement

Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to right, as -

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm starts from left and
moves to right.

As a[pivot] > a[left], so algorithm moves one position to right as -

Page 28 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm moves one position to
right as -

Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap a[pivot] and a[left], now
pivot is at left, i.e. -

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] = 24, a[right] = 29, and
a[pivot] = 24. As a[pivot] < a[right], so algorithm moves one position to left, as -

Page 29 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot] and a[right],
now pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm starts from left and
move to right.

Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are pointing the same element.
It represents the termination of procedure.

Element 24, which is the pivot element is placed at its exact position.

Elements that are right side of element 24 are greater than it, and the elements that are left side of element
24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and right sub-arrays. After
sorting gets done, the array will be -

Page 30 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Quicksort complexity
Now, let's see the time complexity of quicksort in best case, average case, and in worst case. We will also
see the space complexity of quicksort.

Best Case O(n*logn)

Average Case O(n*logn)

Worst Case O(n2)

1. Time Complexity

o Best Case Complexity - In Quicksort, the best-case occurs when the pivot element is the middle
element or near to the middle element. The best-case time complexity of quicksort is O(n*logn).
o 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 quicksort
is O(n*logn).
o Worst Case Complexity - In quick sort, worst case occurs when the pivot element is either
greatest or smallest element. Suppose, if the pivot element is always the last element of the array,
the worst case would occur when the given array is sorted already in ascending or descending
order. The worst-case time complexity of quicksort is O(n2).
Though the worst-case complexity of quicksort is more than other sorting algorithms such as Merge
sort and Heap sort, still it is faster in practice. Worst case in quick sort rarely occurs because by changing
the choice of pivot, it can be implemented in different ways. Worst case in quicksort can be avoided by
choosing the right pivot element.

2. Space Complexity

Space Complexity O(n*logn)

Stable NO

o The space complexity of quicksort is O(n*logn).

Page 31 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Merge Sort
The Merge Sort algorithm is a divide-and-conquer algorithm that sorts an array by first breaking
it down into smaller arrays, and then building the array back together the correct way so that it is
sorted.
Merge Sort
Divide: The algorithm starts with breaking up the array into smaller and smaller pieces until one
such sub-array only consists of one element.
Conquer: The algorithm merges the small pieces of the array back together by putting the lowest
values first, resulting in a sorted array.
The breaking down and building up of the array to sort the array is done recursively.
In the animation above, each time the bars are pushed down represents a recursive call, splitting
the array into smaller pieces. When the bars are lifted up, it means that two sub-arrays have been
merged together.
The Merge Sort algorithm can be described like this:

How it works:
Divide the unsorted array into two sub-arrays, half the size of the original.
Continue to divide the sub-arrays as long as the current piece of the array has more than one
element.
Merge two sub-arrays together by always putting the lowest value first.
Keep merging until there are no sub-arrays left.
Take a look at the drawing below to see how Merge Sort works from a different perspective. As
you can see, the array is split into smaller and smaller pieces until it is merged back together. And
as the merging happens, values from each sub-array are compared so that the lowest value comes
first.

Merge Sort
Step 1: We start with an unsorted array, and we know that it splits in half until the sub-arrays only
consist of one element. The Merge Sort function calls itself two times, once for each half of the
array. That means that the first sub-array will split into the smallest pieces first.

[ 12, 8, 9, 3, 11, 5, 4]
[ 12, 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8, 9] [ 3, 11, 5, 4]
[ 12] [ 8] [ 9] [ 3, 11, 5, 4]
Step 2: The splitting of the first sub-array is finished, and now it is time to merge. 8 and 9 are the
first two elements to be merged. 8 is the lowest value, so that comes before 9 in the first merged
sub-array.
Page 32 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

[ 12] [ 8, 9] [ 3, 11, 5, 4]
Step 3: The next sub-arrays to be merged is [ 12] and [ 8, 9]. Values in both arrays are compared
from the start. 8 is lower than 12, so 8 comes first, and 9 is also lower than 12.
[ 8, 9, 12] [ 3, 11, 5, 4]
Step 4: Now the second big sub-array is split recursively.
[ 8, 9, 12] [ 3, 11, 5, 4]
[ 8, 9, 12] [ 3, 11] [ 5, 4]
[ 8, 9, 12] [ 3] [ 11] [ 5, 4]
Step 5: 3 and 11 are merged back together in the same order as they are shown because 3 is lower
than 11.
[ 8, 9, 12] [ 3, 11] [ 5, 4]
Step 6: Sub-array with values 5 and 4 is split, then merged so that 4 comes before 5.
[ 8, 9, 12] [ 3, 11] [ 5] [ 4]
[ 8, 9, 12] [ 3, 11] [ 4, 5]
Step 7: The two sub-arrays on the right are merged. Comparisons are done to create elements in
the new merged array:
3 is lower than 4
4 is lower than 11
5 is lower than 11
11 is the last remaining value
[ 8, 9, 12] [ 3, 4, 5, 11]
Step 8: The two last remaining sub-arrays are merged. Let's look at how the comparisons are done
in more detail to create the new merged and finished sorted array:

3 is lower than 8:

Before [ 8, 9, 12] [ 3, 4, 5, 11]

After: [ 3, 8, 9, 12] [ 4, 5, 11]
Step 9: 4 is lower than 8:

Before [ 3, 8, 9, 12] [ 4, 5, 11]

After: [ 3, 4, 8, 9, 12] [ 5, 11]
Step 10: 5 is lower than 8:
Page 33 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Before [ 3, 4, 8, 9, 12] [ 5, 11]

After: [ 3, 4, 5, 8, 9, 12] [ 11]
Step 11: 8 and 9 are lower than 11:

Before [ 3, 4, 5, 8, 9, 12] [ 11]

After: [ 3, 4, 5, 8, 9, 12] [ 11]
Step 12: 11 is lower than 12:

Before [ 3, 4, 5, 8, 9, 12] [ 11]

After: [ 3, 4, 5, 8, 9, 11, 12]
The sorting is finished!
Run the simulation below to see the steps above animated:
Merge Sort
[ 12, 8, 9,3, 11,5,4]
Merge sort is a sorting technique based on divide and conquer technique. With worst-case time
complexity being Ο(n log n), it is one of the most used and approached algorithms.

Heap Sort Algorithm

In this article, we will discuss the Heapsort Algorithm. Heap sort processes the elements by creating the
min-heap or max-heap using the elements of the given array. Min-heap or max-heap represents the
ordering of array in which the root element represents the minimum or maximum element of the array.

Heap sort basically recursively performs two main operations -

o Build a heap H, using the elements of array.

o Repeatedly delete the root element of the heap formed in 1st phase.
Before knowing more about the heap sort, let's first see a brief description of Heap.

What is a heap?

A heap is a complete binary tree, and the binary tree is a tree in which the node can have the utmost two
children. A complete binary tree is a binary tree in which all the levels except the last level, i.e., leaf node,
should be completely filled, and all the nodes should be left-justified.

What is heap sort?

Heapsort is a popular and efficient sorting algorithm. The concept of heap sort is to eliminate the elements
one by one from the heap part of the list, and then insert them into the sorted part of the list.
Page 34 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Heapsort is the in-place sorting algorithm.

Now, let's see the algorithm of heap sort.

Algorithm

. HeapSort(arr)
. BuildMaxHeap(arr)
. for i = length(arr) to 2
. swap arr[1] with arr[i]
. heap_size[arr] = heap_size[arr] ? 1
. MaxHeapify(arr,1)
. End
BuildMaxHeap(arr)

. BuildMaxHeap(arr)
. heap_size(arr) = length(arr)
. for i = length(arr)/2 to 1
. MaxHeapify(arr,i)
. End
MaxHeapify(arr,i)
. MaxHeapify(arr,i)
. L = left(i)
. R = right(i)
. if L ? heap_size[arr] and arr[L] > arr[i]
. largest = L
. else
. largest = i
. if R ? heap_size[arr] and arr[R] > arr[largest]
. largest = R
. if largest != i
. swap arr[i] with arr[largest]
. MaxHeapify(arr,largest)
. End

Working of Heap sort Algorithm

Now, let's see the working of the Heapsort Algorithm.

Advertisement
In heap sort, basically, there are two phases involved in the sorting of elements. By using the heap sort
algorithm, they are as follows -

o The first step includes the creation of a heap by adjusting the elements of the array.
o After the creation of heap, now remove the root element of the heap repeatedly by shifting it to the
end of the array, and then store the heap structure with the remaining elements.
Page 35 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Now let's see the working of heap sort in detail by using an example. To understand it more clearly, let's
take an unsorted array and try to sort it using heap sort. It will make the explanation clearer and easier.

First, we have to construct a heap from the given array and convert it into max heap.

After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete this node, we have to swap it
with the last node, i.e. (11). After deleting the root element, we again have to heapify it to convert it into
max heap.

After swapping the array element 89 with 11, and converting the heap into max-heap, the elements of
array are -

In the next step, again, we have to delete the root element (81) from the max heap. To delete this node, we
have to swap it with the last node, i.e. (54). After deleting the root element, we again have to heapify it to
convert it into max heap.

Page 36 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

After swapping the array element 81 with 54 and converting the heap into max-heap, the elements of array
are -

In the next step, we have to delete the root element (76) from the max heap again. To delete this node, we
have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 76 with 9 and converting the heap into max-heap, the elements of array
are -

In the next step, again we have to delete the root element (54) from the max heap. To delete this node, we
have to swap it with the last node, i.e. (14). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 54 with 14 and converting the heap into max-heap, the elements of array
are -

Page 37 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

In the next step, again we have to delete the root element (22) from the max heap. To delete this node, we
have to swap it with the last node, i.e. (11). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 22 with 11 and converting the heap into max-heap, the elements of array
are -

In the next step, again we have to delete the root element (14) from the max heap. To delete this node, we
have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 14 with 9 and converting the heap into max-heap, the elements of array
are -

In the next step, again we have to delete the root element (11) from the max heap. To delete this node, we
have to swap it with the last node, i.e. (9). After deleting the root element, we again have to heapify it to
convert it into max heap.

After swapping the array element 11 with 9, the elements of array are -

Now, heap has only one element left. After deleting it, heap will be empty.
Page 38 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

After completion of sorting, the array elements are -

Now, the array is completely sorted.

Heap sort complexity

Now, let's see the time complexity of Heap sort in the best case, average case, and worst case. We will
also see the space complexity of Heapsort.

Case Time Complexity

Best Case O(n logn)

Average Case O(n log n)

Worst Case O(n log n)

1. Time Complexity

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted.
The best-case time complexity of heap sort is O(n logn).
o 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 heap sort
is O(n log n).
o 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 heap sort is O(n log n).
The time complexity of heap sort is O(n logn) in all three cases (best case, average case, and worst case).

Space Complexity O(1)

Stable N0
The height of a complete binary tree having n elements is logn.

2. Space Complexity

o The space complexity of Heap sort is O(1).

Page 39 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Radix Sort Algorithm

In this article, we will discuss the Radix sort Algorithm. Radix sort is the linear sorting algorithm that is
used for integers. In Radix sort, there is digit by digit sorting is performed that is started from the least
significant digit to the most significant digit.

The process of radix sort works similar to the sorting of students names, according to the alphabetical
order. In this case, there are 26 radix formed due to the 26 alphabets in English. In the first pass, the names
of students are grouped according to the ascending order of the first letter of their names. After that, in the
second pass, their names are grouped according to the ascending order of the second letter of their name.
And the process continues until we find the sorted list.

Now, let's see the algorithm of Radix sort.

Algorithm
. radixSort(arr)
. max = largest element in the given array
. d = number of digits in the largest element (or, max)
. Now, create d buckets of size 0 - 9
. for i -> 0 to d
. sort the array elements using counting sort (or any stable sort) according to the digits at
. the ith place

Working of Radix sort Algorithm

Now, let's see the working of Radix sort Algorithm.

The steps used in the sorting of radix sort are listed as follows -

o First, we have to find the largest element (suppose max) from the given array. Suppose 'x' be the
number of digits in max. The 'x' is calculated because we need to go through the significant places
of all elements.
o After that, go through one by one each significant place. Here, we have to use any stable sorting
algorithm to sort the digits of each significant place.
Now let's see the working of radix sort in detail by using an example. To understand it more clearly, let's
take an unsorted array and try to sort it using radix sort. It will make the explanation clearer and easier.

In the given array, the largest element is 736 that have 3 digits in it. So, the loop will run up to three times
(i.e., to the hundreds place). That means three passes are required to sort the array.

Now, first sort the elements on the basis of unit place digits (i.e., x = 0). Here, we are using the counting
sort algorithm to sort the elements.

Pass 1:

In the first pass, the list is sorted on the basis of the digits at 0's place.
Page 40 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

After the first pass, the array elements are -

Pass 2:

In this pass, the list is sorted on the basis of the next significant digits (i.e., digits at 10th place).

After the second pass, the array elements are -

Page 41 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

Pass 3:

In this pass, the list is sorted on the basis of the next significant digits (i.e., digits at 100th place).

After the third pass, the array elements are -

Now, the array is sorted in ascending order.

Radix sort complexity

Now, let's see the time complexity of Radix sort in best case, average case, and worst case. We will also
see the space complexity of Radix sort.

1. Time Complexity

o Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted.

Case Time Complexity

Best Case Ω(n+k)

Average Case θ(nk)

Worst Case O(nk)

The best-case time complexity of Radix sort is Ω(n+k).
o 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 Radix sort
is θ(nk).

Page 42 of 43
B. TECH. /CSE-IIInd SEM / BCS-301: DATA STRUCTURE / UNIT-III / Introduction, Searching & Sorting
Amit Kumar Jaiswal / Assistant Professor /Department of CSE /JMS Institute of Technology-Ghaziabad

o 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 Radix sort is O(nk).
Radix sort is a non-comparative sorting algorithm that is better than the comparative sorting algorithms. It
has linear time complexity that is better than the comparative algorithms with complexity O(n logn).

2. Space Complexity

Space Complexity O(n + k)

Stable YES
o The space complexity of Radix sort is O(n + k).
Following is a quick revision sheet that you may refer to at the last minute:

Algorithm Time Complexity Space Complexity

Best Average Worst Worst

Selection Sort O(n2) O(n2) O(n2) O(1)

Bubble Sort O(n) O(n2) O(n2) O(1)

Insertion Sort O(n) O(n2) O(n2) O(1)

Heap Sort O(n log(n)) O(n log(n)) O(n log(n)) O(1)

Quick Sort O(n log(n)) O(n log(n)) O(n2) O(n)

Merge Sort O(n log(n)) O(n log(n)) O(n log(n)) O(n)

Bucket Sort O(n +k) O(n +k) O(n2) O(n)

Radix Sort O(nk) O(nk) O(nk) O(n + k)

Count Sort O(n +k) O(n +k) O(n +k) O(k)

Shell Sort O(n log(n)) O(n log(n)) O(n2) O(1)

Page 43 of 43