This is my 41th day of 100 days of code and python. Today I learned basic of some sorting algorithms. As I know that algorithm are the step by step description of problem, also it is systematic thinking of solving problem.
“Algorithm” is a general term that has an overblown weight to it in software development, in my opinion.
The simple truth is that algorithms are just ways to do things. They’re processes to solve a type of problem.
Bubble sort
Bubble sort is the simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in wrong order. The pass through the list is repeated until the list is sort.
list = [ 4,5,2,3,6]
for num in range(len(list)-1,0,-1):
for i in range(num):
if list[i]>list[i + 1]:
temp = list[i]
list[ i + 1] = list[i]
list[i + 1] = temp
print(list)
Out put is,
[4, 5, 5, 5, 6]
Insertion Sort
Insertion sort is a simple sorting algorithms that builds the final sorted array(or list) one item at a time. It is more efficent in practice than most other simple quardatic algorithms like selection sort or bubble sort.
arr = [1,3,2,45,6,74,5]
for i in range(len(arr)):
key = arr[i]
j = i - 1
while j >=0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
print('Sorted array is:')
for i in range(len(arr)):
print('%d'%arr[i])
Output is,
Sorted array is:
1
2
3
5
6
45
74
Selection Sort
It is an in place sorting algorithm. It is inefficent on largest list and generally performs worse than the similar insertion sort.
A = [5,4,3,2,1]
for i in range(len(A)):
min_idx = i
for j in range(i + 1,len(A)):
A[min_idx] > A[j]
min_idx = j
A[i],A[min_idx] = A[min_idx],A[i]
print('sorted array:')
for i in range(len(A)):
print('%d'%A[i])
sorted array:
1
5
4
3
2
Heap Sort
Heapsort is a comparison based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining element
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2* i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i]
heapify(arr,n,largest)
def heapSort(arr):
n = len(arr)
for i in range(n//2 -1,-1,-1):
heapify(arr,n,i)
for i in range(n-1,0,-1):
arr[i],arr[0]= arr[0],arr[i]
heapify(arr,i,0)
arr = [4,2,1,3,5,6]
heapSort(arr)
n = len(arr)
print('Sorted array is:')
for i in range(n):
print('%d'%arr[i]),
Out put is,
Sorted array is:
1
2
3
4
5
6
Day 41 Of #100DaysOfCode and #pythonlearning
— Durga Pokharel (@mathdurga) February 3, 2021
* Bubble Sort
* Insertion Sort
* Selection Sort
* Heap Sort#100DaysOfCode ,#womenintech ,#CodeNewbies ,#pythonlearning pic.twitter.com/gUDw7DG4v6
Top comments (2)
awesome
Thank you