Sorting Algorithms in Python

siddhartha280601 — Fri, 23 Apr 2021 05:52:16 +0000

What do you mean by Sorting?
Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order.
What is the importance of Sorting?
The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Below we see five such implementations of sorting in python.
1.Bubble Sort
2.Merge Sort
3.Insertion Sort
4.Selection Sort
5.Quick Sort

Bubble Sort : Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. In bubble sort, we compare each element with its adjacent neighbor or and swap if it bigger.

Time Complexity:

The time complexity of best-case of bubble sort is O(n). Bubble sort has a worst-case and average complexity of O(n2), where n is the number of items being sorted.

PROGRAM:

def bubbleSort(nlist):
for passnum in range(len(nlist)-1,0,-1):
for i in range(passnum):
if nlist[i]>nlist[i+1]:
temp = nlist[i]
nlist[i] = nlist[i+1]
nlist[i+1] = temp

nlist = [14,46,43,27,57,41,45,21,70]
bubbleSort(nlist)
print(nlist)

Merge Sort : Merge sort is based upon divide and conquer technique. In merge sort, we divide recursively divide each sub-lists into element level, and then start merging them.Merge sort is a divide and conquer algorithm.

Time Complexity :

Time complexity of Merge Sort is O(nlogn) in all the three cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves. It requires equal amount of additional space as the unsorted array. def

PROGRAM:

def mergesort(unsorted_list):
if len(unsorted_list) <= 1:
return unsorted_list

Find the middle point and divide it

middle = len(unsorted_list) // 2
left_list = unsorted_list[:middle]
right_list = unsorted_list[middle:]

left_list = mergesort(left_list)
right_list = mergesort(right_list)
return list(merge(left_list, right_list))

Merge the sorted halves

def merge(left_half,right_half):

res = []
while len(left_half) != 0 and len(right_half) != 0:
    if left_half[0] < right_half[0]:
        res.append(left_half[0])
        left_half.remove(left_half[0])
    else:
        res.append(right_half[0])
        right_half.remove(right_half[0])
if len(left_half) == 0:
    res = res + right_half
else:
    res = res + left_half
return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(mergesort(unsorted_list))

3.Insertion Sort:

Insertion sort is in place comparison algorithm. Here we are creating a sub-list of sorted elements from our given list, and iteratively keep on adding new elements and sort them.

Time Complexity:

The best case input is an array that is already sorted. In this case insertion sort has a linear running time i.e., O(n).The simplest worst case input is an array sorted in reverse order,this gives insertion sort a quadratic running time i.e., O(n2).

PROGRAM:

def insertionsort(inputList):
for i in range(1, len(inputList)):
j = i-1
nxt_element = inputList[i]

Compare the current element with next one

    while (inputList[j] > nxt_element) and (j >= 0):
         inputList[j+1] = inputList[j]
         j=j-1
    inputList[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertionsort(list)
print(list)

Selection Sort:

Selection sort is simplest of sorting algorithm. Selection sort is an in place comparison where we will keep iterating and building sorted new list from our given data. The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right. Selection sort is not an efficient sorting method and is not used for larger data set.

Time Complexity:

In the worst case,outer loop executes N-1 time and inner loop executes N-i-1 comparisons. (n-1)+(n-2)+…+2+1=n*(n-1)/2 = O(n2) The worst case occurs if the array is already sorted in descending order.The Best Case is O(n2).The Average Case is O(n2).

PROGRAM:

def selectionsort(input_list):

for idx in range(len(input_list)):

    min_idx = idx
    for j in range( idx +1, len(input_list)):
        if input_list[min_idx] > input_list[j]:
            min_idx = j

Swap the minimum value with the compared value

    input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]

l = [19,2,31,45,30,11,121,27]
selectionsort(l)
print(l)

5.Quick Sort:

Quick sort is highly efficient sorting algorithm which is often used for large data sets. Quick sort is based upon partitioning list into smaller lists (based on pivot point). Elements are arranged on basis of whether they are smaller or larger than pivot.

Time Complexity:

Worst Case Time Complexity of Quick sort is O(n2).Best Case and Average Time Complexity is O(nlogn).

PROGRAM:

divide function

def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high] # pivot element
for j in range(low , high):
# If current element is smaller
if arr[j] <= pivot:
# increment
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )

sort

def quickSort(arr,low,high):
if low < high:
# index
pi = partition(arr,low,high)
# sort the partitions
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)

main

arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSort(arr,0,n-1)
for i in range(n):
print (arr[i],end=" ")

DEV Community: siddhartha280601

Sorting Algorithms in Python

Find the middle point and divide it

Merge the sorted halves

Compare the current element with next one

Swap the minimum value with the compared value

divide function

sort

main