UNIT III SORTING AND SEARCHING
Bubble sort – selection sort – insertion sort – merge sort – quick sort – analysis of sorting
algorithms – linear search – binary search – hashing – hash functions – collision handling –
load factors, rehashing, and efficiency
SORTING:
The arrangement of data in a preferred order is called sorting in the data structure.
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.
By sorting data, it is easier to search through it quickly and easily.
The simplest example of sorting is a dictionary.
CATEGORIES OF SORTING:
The techniques of sorting can be divided into two categories. These are:
Internal Sorting
External Sorting
Internal sorting: If the input data is such that it can be adjusted in the main memory at once, it
is called internal sorting.
,External sorting: If the input data is such that it cannot be adjusted in the memory entirely at
once, it needs to be stored in a hard disk, floppy disk, or any other storage device. This is called
external sorting.
Different Sorting Algorithms
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quicksort
Counting Sort
Radix Sort
Bucket Sort
Heap Sort
Shell Sort
Complexity of Sorting Algorithms
The efficiency of any sorting algorithm is determined by the time complexity and space
complexity of the algorithm.
1. Time Complexity: Time complexity refers to the time taken by an algorithm to complete its
execution with respect to the size of the input. It can be represented in different forms:
Big-O notation (O)
Omega notation (Ω)
Theta notation (Θ)
2. Space Complexity: Space complexity refers to the total amount of memory used by the
algorithm for a complete execution. It includes both the auxiliary memory and the input.
BUBBLE SORT
Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them
until they are in the intended order.
The bubble sort uses a straightforward logic that works by repeating swapping the
adjacent elements if they are not in the right order. It compares one pair at a time and swaps if
the first element is greater than the second element; otherwise, move further to the next pair of
elements for comparison.
,Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
First Iteration (Compare and Swap)
1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element
Remaining Iteration
1. The same process goes on for the remaining iterations.
2. After each iteration, the largest element among the unsorted elements is placed at the end.
Example We are creating a list of element, which stores the integer numbers
list1 = [5, 3, 8, 6, 7, 2]
Here the algorithm sort the elements
First iteration
[5, 3, 8, 6, 7, 2] here 5>3 then swap with each other.
[3, 5, 8, 6, 7, 2] 5 < 8 then no swap taken place.
[3, 5, 8, 6, 7, 2] 8>6 then swap with each other
[3, 5, 6, 8, 7, 2] 8>7 then swap with each other
[3, 5, 6, 7, 8, 2] 8>2 then swap with each other
[3, 5, 6, 7, 2, 8]
Here the first iteration is complete and we get the largest element at the end. Now we need to the
len(list1) - 1
Second Iteration
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 6<7 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 2, 7, 8] here 7>2 then swap their position. Now
, [3, 5, 6, 2, 7, 8] - > [3, 5, 6, 2, 7, 8] here 7<8 then no swap taken place.
Third Iteration
[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place
[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place
[3, 5, 6, 2, 7, 8] - > [3, 5, 2, 6, 7, 8] here, 6>2 then swap their positions
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 6<7 then no swap taken place. Now
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 7<8 then swap their position.
Fourth Iteration
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here, 3<5 then no swap taken place
[3, 5, 2, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 5>2 then swap their position.
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 5<6 then no swap taken place
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 6<7 then no swap taken place
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 7<8 then no swap taken place
Fifth Iteration
[3, 2, 5, 6, 7, 8] - > [2, 3, 5, 6, 7, 8]here 3>2 then swap their position.
Bubble sort Example:
def bubblesort(list1):
fori in range(0,len(list1)-1):
for j in range(0,len(list1)-1):
if(list1[j]>list1[j+1]):
temp=list1[j]
list1[j]=list1[j+1]
list1[j+1]=temp
Bubble sort – selection sort – insertion sort – merge sort – quick sort – analysis of sorting
algorithms – linear search – binary search – hashing – hash functions – collision handling –
load factors, rehashing, and efficiency
SORTING:
The arrangement of data in a preferred order is called sorting in the data structure.
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.
By sorting data, it is easier to search through it quickly and easily.
The simplest example of sorting is a dictionary.
CATEGORIES OF SORTING:
The techniques of sorting can be divided into two categories. These are:
Internal Sorting
External Sorting
Internal sorting: If the input data is such that it can be adjusted in the main memory at once, it
is called internal sorting.
,External sorting: If the input data is such that it cannot be adjusted in the memory entirely at
once, it needs to be stored in a hard disk, floppy disk, or any other storage device. This is called
external sorting.
Different Sorting Algorithms
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quicksort
Counting Sort
Radix Sort
Bucket Sort
Heap Sort
Shell Sort
Complexity of Sorting Algorithms
The efficiency of any sorting algorithm is determined by the time complexity and space
complexity of the algorithm.
1. Time Complexity: Time complexity refers to the time taken by an algorithm to complete its
execution with respect to the size of the input. It can be represented in different forms:
Big-O notation (O)
Omega notation (Ω)
Theta notation (Θ)
2. Space Complexity: Space complexity refers to the total amount of memory used by the
algorithm for a complete execution. It includes both the auxiliary memory and the input.
BUBBLE SORT
Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them
until they are in the intended order.
The bubble sort uses a straightforward logic that works by repeating swapping the
adjacent elements if they are not in the right order. It compares one pair at a time and swaps if
the first element is greater than the second element; otherwise, move further to the next pair of
elements for comparison.
,Working of Bubble Sort
Suppose we are trying to sort the elements in ascending order.
First Iteration (Compare and Swap)
1. Starting from the first index, compare the first and the second elements.
2. If the first element is greater than the second element, they are swapped.
3. Now, compare the second and the third elements. Swap them if they are not in order.
4. The above process goes on until the last element
Remaining Iteration
1. The same process goes on for the remaining iterations.
2. After each iteration, the largest element among the unsorted elements is placed at the end.
Example We are creating a list of element, which stores the integer numbers
list1 = [5, 3, 8, 6, 7, 2]
Here the algorithm sort the elements
First iteration
[5, 3, 8, 6, 7, 2] here 5>3 then swap with each other.
[3, 5, 8, 6, 7, 2] 5 < 8 then no swap taken place.
[3, 5, 8, 6, 7, 2] 8>6 then swap with each other
[3, 5, 6, 8, 7, 2] 8>7 then swap with each other
[3, 5, 6, 7, 8, 2] 8>2 then swap with each other
[3, 5, 6, 7, 2, 8]
Here the first iteration is complete and we get the largest element at the end. Now we need to the
len(list1) - 1
Second Iteration
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 7, 2, 8] here, 6<7 then no swap taken place
[3, 5, 6, 7, 2, 8] - > [3, 5, 6, 2, 7, 8] here 7>2 then swap their position. Now
, [3, 5, 6, 2, 7, 8] - > [3, 5, 6, 2, 7, 8] here 7<8 then no swap taken place.
Third Iteration
[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 3<5 then no swap taken place
[3, 5, 6, 2, 7, 8] - > [3, 5, 6, 7, 2, 8] here, 5<6 then no swap taken place
[3, 5, 6, 2, 7, 8] - > [3, 5, 2, 6, 7, 8] here, 6>2 then swap their positions
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 6<7 then no swap taken place. Now
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here 7<8 then swap their position.
Fourth Iteration
[3, 5, 2, 6, 7, 8] - > [3, 5, 2, 6, 7, 8] here, 3<5 then no swap taken place
[3, 5, 2, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 5>2 then swap their position.
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 5<6 then no swap taken place
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 6<7 then no swap taken place
[3, 2, 5, 6, 7, 8] - > [3, 2, 5, 6, 7, 8] here 7<8 then no swap taken place
Fifth Iteration
[3, 2, 5, 6, 7, 8] - > [2, 3, 5, 6, 7, 8]here 3>2 then swap their position.
Bubble sort Example:
def bubblesort(list1):
fori in range(0,len(list1)-1):
for j in range(0,len(list1)-1):
if(list1[j]>list1[j+1]):
temp=list1[j]
list1[j]=list1[j+1]
list1[j+1]=temp
