Searching and Sorting Techniques in Python

By Akshat Kumar

This project shows the working of Searching algorithms- Linear search and Binary search and sorting algorithm- Selection sort and Bubble sort

Searching Algorithms are designed to find and retrieve a particular element stored in a Data Structure, depending on how the Array is Organised, we can use different search techniques, if the Array is unsorted or random the most commonly used technique is:

1) LINEAR SEARCH

Linear Search is a sequential search algorithm that starts from the beginning of an array and compares each and every element in the array against the required element/key until the condition is satisfied.

Example of an Array:

Let's define our key to be 30 i.e the element we have to find in the array

Linear Search works by

1) Comparing the Element at the first index against the key, in this case, 10 is not equal to 30 thus

2) Comparing the second element against the key, in this case, 200 is not equal to 30

3) This continues until the condition is satisfied, here we can determine that the element 30 is at the 3rd Index.

 

Linear Search had a space complexity of O(1) and its best time complexity is O(1) if the key is located at the 0th index and its worse time complexity is O(n) if the key is located at the nth index

If the given array is not random and is sorted then we can use more efficient search techniques like:

 

2) BINARY SEARCH

Binary search works by repeatedly dividing the array into two parts and selecting the half in which the key element lies. let's use the Example array shown above Bubble sort works only if the Array is sorted.

Sorted Array = 1 2 3 10 30 40 200

let's set the key element to be 40, i.e., we have to determine the index of the element 40

Binary Search works by:

1) First Dividing the given array at its middle index value, Since this array has 7 elements its middle index will be 3, thus we have

    1 2 3 10       30 40 200

2) Comparing the key element 40 against the middle element 10, since 40>10 we will consider the second half of the array moving on, thus

    30 40 200

3) Repeating Step 1, this time the middle index is 5th and the 5th index value corresponds with 40

thus, the key element 40 is at the 5th index 

Binary Search has a time complexity of O(log n) and is more efficient than linear search, however as mentioned previously it requires the array to be sorted

Let us now look at some techniques to sort a Data Structure

 

1) SELECTION SORT

Selection sort works by finding the smallest element in the array and moving it to the front of the array in each iteration, it moves the smallest element of the array from the unsorted part to the sorted part. let's use the Example of the array given above

 

Selection sort works by

1) Going through the whole array and moving the smallest element to the front, thus

    1 200 2 30 10 40 3

2) Second iteration 1 2 200 30 10 40 3

3) third iteration 1 2 3 30 10 40 200

4) Fourth iteration 1 2 3 10 30 40 200

In each iteration, the smallest element is identified and moved in the front, shown by the underlined elements

The time complexity of Selection sort is O(N²)

 

2) BUBBLE SORT

Bubble sort works by comparing the two adjacent elements and switching places if the elements are not sorted, let’s how it works with our example

Unsorted array: 1 200 2 30 10 40 3

Bubble sort works by

• Starting from 0^th index and comparing it against the 1^st index, if they are in order it moves to the next iteration, if not in order it switches their positions.

1 200 2 30 10 40 3

• 2^nd iteration:  1 2 200 30 10 40 3
• 3^rd iteration: 1 2 30 200 10 40 3
• 4^th iteration: 1 2 30 10 200 40 3
• 5^th iteration: 1 2 30 10 40 200 3
• 6^th iteration: 1 2 30 10 40 3 200
• 7^th iteration: 1 2 10 30 40 3 200
• 8^th iteration: 1 2 10 30 3 40 200
• 9^th iteration:  1 2 10 3 30 40 200
• 10^th iteration: 1 2 3 10 30 40 200

A quick glance at the number of iterations shows that bubble sort is a less efficient algorithm for sorting arrays compared to selection sort, having a time complexity of O(N^2).