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 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 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])
Sorted array is: 1 2 3 5 6 45 74
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
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= arr,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