DEV Community

loading...

Day 41 Of 100DaysOfCode: Basic About Some Algorithms

iamdurga profile image Durga Pokharel ・3 min read

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)
Enter fullscreen mode Exit fullscreen mode

Out put is,

[4, 5, 5, 5, 6]
Enter fullscreen mode Exit fullscreen mode

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])
Enter fullscreen mode Exit fullscreen mode

Output is,

Sorted array is:
1
2
3
5
6
45
74
Enter fullscreen mode Exit fullscreen mode

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])
Enter fullscreen mode Exit fullscreen mode
sorted array:
1
5
4
3
2
Enter fullscreen mode Exit fullscreen mode

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]),


Enter fullscreen mode Exit fullscreen mode

Out put is,

Sorted array is:
1
2
3
4
5
6
Enter fullscreen mode Exit fullscreen mode

Discussion (2)

pic
Editor guide
Collapse
otumianempire profile image
Otu Michael

awesome

Collapse
iamdurga profile image