Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Searching
2.1.
Code
2.2.
Output:
2.3.
Sequential Search
2.3.1.
Time Complexity
2.3.2.
Space Complexity
2.4.
Interval Search
2.4.1.
Time Complexity
2.4.2.
Space Complexity
3.
Sorting
3.1.
Code
3.2.
Output:
3.3.
Bubble Sort
3.3.1.
Time Complexity
3.3.2.
Space Complexity
3.4.
Selection Sort
3.4.1.
Time Complexity
3.4.2.
Space Complexity
3.5.
Merge Sort
3.5.1.
Time Complexity
3.5.2.
Space Complexity
4.
Difference between Searching and Sorting
4.1.
Searching
4.2.
Sorting
5.
Frequently Asked Questions
5.1.
Which is the best Sorting algorithm?
5.2.
What is the condition to apply a binary search on a dataset?
5.3.
Which is the easiest sorting algorithm?
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

Difference between Searching and Sorting

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Hello Ninja, I hope you are doing great. Do you know about Searching and Sorting? If not, don't worry. We are here to enrich your knowledge and clear all your doubts.

Difference between Searching and Sorting

This article will discuss searching and sorting, along with their different algorithms. We will also analyze the time and space complexity of the algorithms. This article will show the significant difference between Searching and Sorting on specific parameters.

Searching

Searching is finding a particular item in a given list of items. It decides whether an element we are searching for is present or not. A search algorithm is an algorithm that accepts an argument "x"’ and tries to find an item in a given list whose value is equal to "x."

Searching for an element in a list can be done using Sequential search and Interval search.

An example of Binary Search

The image above shows searching for an element in a sorted array using binary search.

Code

#include <bits/stdc++.h>
using namespace std;

int Binary_Search(vector <int> &my_List, int element) {
   int start = 0, end = my_List.size() - 1, index = -1;
   while(start <= end) {
       // find a mid
       int mid = (start + end) / 2;
       // check if our element is less than or equal to the element present at the mid index
       if(my_List[mid] >= element) {
           // now element present at mid can be our potential answer
           index = mid;
           // reduce the range because our element can't be at any index > mid
           end = mid - 1;
       }
       else {
           // reduce the range because our element can't be at any index < mid
           start = mid + 1;
       }
   }
   if(index != -1) {
       if(my_List[index] != element) index = -1;
   }
   return index;
}

int main() {
   vector <int> my_List = {1, 4, 15, 18, 22, 25};
   int element = 18;
   // search '18' in a given list and print its index
   cout << Binary_Search(my_List, element);
   return 0;
}

Output:

3

The code above uses a binary search algorithm to search a given element from the list.

Sequential Search

It is also known as Linear Search. It starts at the beginning of the list and compares every value on the list with the target value. If the target value matches the value in a list, then it returns the index of that element; otherwise, it returns -1. 

Time Complexity

In the worst case (when the element we are searching for is present at the end of the list) we have to traverse the whole array. So, its Worst case time complexity will be O(n).

In the Best case, the element will be present at the beginning of the list. So we don’t need to traverse the array. Hence its Best case time complexity will be O(1).

Space Complexity

We don’t need any auxiliary space for this technique. So its space complexity will be O(1);

Interval Search

In this algorithm we only check certain parts of the dataset. Binary search is an example of an interval search algorithm. Binary Search works on sorted lists i.e., the list must be in increasing or decreasing order. It is based on a divide and conquer algorithm in which we compare our target value with the middle element of the list and based on that we reduce our search space by half. We continue this until we find our target element or our search space reduces to 1. 

Time Complexity

The Worst case occurs when the algorithm keeps searching for the target until our search space reduces to 1. Since the number of comparisons are logn. So its Worst case time complexity will be O(logn).

The Best case occurs when the target is present in the middle. So only one comparison will be needed. Hence, its Best case time complexity will be O(1).

Space Complexity

We don’t need any auxiliary space for this technique. So its space complexity will be O(1);

Also Read - Selection Sort in C

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Sorting

Sorting is a process of arranging elements in increasing or decreasing order. Data is more readable in a sorted format. There are a lot of real-life examples in which Sorting is required. For example: the contact list in our phone is arranged in sorted order, in shopping cart apps we can arrange items by sorted order of their prices and words in the dictionary are arranged in sorted order. Sorting can be done by various algorithms: Bubble Sort, Insertion Sort, Selection Sort, Quick Sort and Merge Sort.

An example of Merge Sort

The image above shows an example to sort the array using Merge sort.

Code

#include <bits/stdc++.h>
using namespace std;

void Merge_Sorted_Lists(vector <int> &my_List, int start_index, int middle_index, int end_index) {
   int left_pointer = start_index, right_pointer = middle_index + 1;
   int left_bound = middle_index, right_bound = end_index;
   vector <int> temporary;
   while(left_pointer <= left_bound && right_pointer <= right_bound) {
       // check whether a left element is less than a right element
       if(my_List[left_pointer] <= my_List[right_pointer]) {
           temporary.push_back(my_List[left_pointer]);
           ++ left_pointer;
       }
       else {
           temporary.push_back(my_List[right_pointer]);
           ++ right_pointer;
       }
   }
   // push remaining elements of the left segment
   while(left_pointer <= left_bound) {
       temporary.push_back(my_List[left_pointer]);
       ++ left_pointer;
   }
   // push remaining elements of the right segment
   while(right_pointer <= right_bound) {
       temporary.push_back(my_List[right_pointer]);
       ++ right_pointer;
   }
   // now push elements of the temporary vector into our original vector
   int current_index = end_index;
   while(temporary.size()) {
       my_List[current_index] = temporary.back();
       temporary.pop_back();
       -- current_index ;
   }
}

void Merge_Sort(vector <int> &my_List, int start_index, int end_index) {
   // base case
   if(start_index >= end_index) {
       return;
   }
   int middle_index = (start_index + end_index) >> 1;
   // divide the current segment into 2 segments
   Merge_Sort(my_List, start_index, middle_index);
   Merge_Sort(my_List, middle_index + 1, end_index);
   // merge these 2 segments
   Merge_Sorted_Lists(my_List, start_index, middle_index, end_index);
}

int main() {
   vector <int> my_List = {3, 11, 4, 18, 6, 12, 4, 8, 20};
   // call Meerge_sort to sort a given array
   Merge_Sort(my_List, 0, 8);
   for(auto &x : my_List) cout << x << ' ';
   return 0;
}

Output:

3 4 4 6 8 11 12 18 20

The code given above uses the Merge Sort algorithm to sort the given array. 

Bubble Sort

It is the most basic sorting algorithm. In this, we repeatedly iterate through the list, compare the adjacent elements, and swap according to the condition passed to them. It is a brute-force solution to sort a list. This algorithm uses two nested loops, the first to iterate over the whole array and the second to check the condition to swap the adjacent elements.

Time Complexity

The Worst case occurs when a list is sorted in decreasing order and we have to sort it in increasing order. So its Worst case time complexity will be O(n2.).

The Best case occurs when a given list is already sorted. Then there will be no need to swap adjacent elements. Only the outer loop will run ‘n’ times. So its Best case time complexity will be O(n).

Space Complexity

We don’t need any extra space for this algorithm. So its space complexity will be O(1).

Selection Sort

It is a simple algorithm in which we move the minimum element to the array’s starting point and make the prefix part of the array sorted. We continuously choose the minimum element from the unsorted suffix part and move to its front until our prefix sorted part becomes the whole sorted array. It also uses two nested loops, one to increase the sorted prefix range or to update the start of the unsorted suffix part and another to find the minimum element among the unsorted suffix part.

Time Complexity

Its worst case and Best case time complexity is the same because there is no break point in the nested loop we are using. 

Hence, its overall time complexity is O(n2).

Space Complexity

No extra space is used in this algorithm. So its space complexity will be O(1).

Merge Sort

Merge sort is the most efficient sorting algorithm. It is based on the concept of divide and conquer. It works by dividing the whole array into two halves, sorting each half, and then merging these two sorted arrays back together to form a fully sorted array. This is done recursively. It can efficiently sort large datasets because of its optimal time complexity.

Time Complexity

Its Worst case and Best case time complexity is the same as it requires O(n) time to merge the sorted subarrays and its divide and conquer part will take O(logn) time. 

So its overall complexity will be O(nlogn).

Space Complexity

For merging the sorted subarrays, we need a temporary array to store the data. So it will take O(n) auxiliary space.

Read More - Time Complexity of Sorting Algorithms

Difference between Searching and Sorting

Searching

Sorting

It is used to find a specific element in the dataset.

It is a way to organize data in increasing or decreasing order.

It does not update the original dataset.

It updates the original dataset.

It can be done by linear search, binary search and ternary search.

It can be done by bubble sort, selection sort, quick sort and merge sort.

It can be done with a single pass through the data.

It requires multiple passes through the data.

The worst case time complexity of the best searching algorithm is O(logn).

The worst case time complexity of the best sorting algorithm is O(nlogn).

The best case time complexity of the best searching algorithm is O(1).

The best case time complexity of the best sorting algorithm is O(n).

Search engines like Google use searching algorithms to find relevant web pages.

E-commerce websites use sorting algorithms to sort products based on price.

A search algorithm can be used for criterias like searching for multiple occurrences of a specific element and finding the closest match for an element.

A sorting algorithm can be used for criterias like sorting based on date, sorting based on alphabetical order and sorting based on numeric value.

Must Read Algorithm Types

Frequently Asked Questions

Which is the best Sorting algorithm?

Merge sort is the best Sorting algorithm. It is based on the divide and conquer algorithm and requires O(nlogn) time complexity in the worst case to sort an array which is the most optimal time complexity.

What is the condition to apply a binary search on a dataset?

If a dataset is sorted or we can say if there is a monotonicity between the elements (so that we can reduce our dataset by half) then we can apply binary search on a dataset.

Which is the easiest sorting algorithm?

The easiest sorting algorithm to understand and implement is generally considered to be Bubble Sort. It has a simple concept and code structure, but its time complexity of O(n2) makes it inefficient for large datasets.

Conclusion

In this article, you’ve learned about what searching and sorting means and the different types of searching and sorting algorithms along with their fundamental differences. 

We hope that this blog has helped you enhance your knowledge regarding the various searching and sorting algorithms.

Recommended Reading:

IEnumerable vs IQueryable

You can refer to Time and Space Complexity of Searching AlgorithmsSorting in Data Structure and 6 Sorting Algorithms, features and functions to learn more about searching and sorting.

Head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!!

Happy Learning Ninja!

Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass