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.
- 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.
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.
for passnum in range(len(nlist)-1,0,-1):
for i in range(passnum):
temp = nlist[i]
nlist[i] = nlist[i+1]
nlist[i+1] = temp
nlist = [14,46,43,27,57,41,45,21,70]
- 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
if len(unsorted_list) <= 1:
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))
res =  while len(left_half) != 0 and len(right_half) != 0: if left_half < right_half: res.append(left_half) left_half.remove(left_half) else: res.append(right_half) right_half.remove(right_half) 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]
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.
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).
for i in range(1, len(inputList)):
j = i-1
nxt_element = inputList[i]
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]
- 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.
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).
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
input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]
l = [19,2,31,45,30,11,121,27]
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.
Worst Case Time Complexity of Quick sort is O(n2).Best Case and Average Time Complexity is O(nlogn).
i = ( low-1 )
pivot = arr[high] # pivot element
for j in range(low , high):
# If current element is smaller
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
if low < high:
pi = partition(arr,low,high)
# sort the partitions
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
for i in range(n):
print (arr[i],end=" ")