Python Sort: Sorting Methods And Algorithms In Python

Learn how to use the Python Sort function for sorting lists, arrays, dictionaries, etc using various sorting methods and algorithms in Python:

Sorting is a technique that is used for sorting the data in a sequence order either in ascending or descending order.

Most of the time the data of the large projects is not arranged in the correct order and this creates problems while accessing and fetching the required data efficiently.

Sorting techniques are used to resolve this problem. Python provides various sorting techniques for example, Bubble sort, Insertion sort, Merge sort, Quicksort, etc.

In this tutorial, we will understand how sorting works in Python by using various algorithms.

=> Take A Look At The Python Beginners Guide Here

Python Sort

Syntax of Python Sort

To perform sorting, Python provides the built-in function i.e. the “ sort() ” function. It is used to sort the data elements of a list in ascending order or in descending order.

Let’s understand this concept with an example.

Example 1:

```
a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ]
a.sort()
print( “ List in ascending order: ”, a )

```

Output:

In this example, the given unordered list is sorted into ascending order by using the “ sort( ) ” function.

Example 2:

```
a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ]
a.sort( reverse = True )
print( “ List in descending order: ”, a )

```

Output

In the above example, the given unordered list is sorted in the reverse order using the function “ sort( reverse = True ) ”.

Time Complexity of Sorting Algorithms

Time Complexity is the amount of time taken by the computer to run a particular algorithm. It has three types of time complexity cases.

• Worst Case: Maximum time taken by the computer to run the program.
• Average Case: Time taken between the minimum and maximum by the computer to run the program.
• Best Case: Minimum time taken by the computer to run the program. It is the best case of time complexity.

Complexity Notations

Big Oh Notation, O: Big oh notation is the official way to convey the upper bound of running time of the algorithms. It is used to measure the worst-case time complexity or we say the largest amount of time taken by the algorithm to complete.

Big omega Notation, : Big omega notation is the official way to convey the lowest bound of the running time of the algorithms. It is used to measure best-case time complexity or we say the excellent amount of time taken by the algorithm.

Theta Notation, : Theta notation is the official way to convey both bounds i.e. lower and upper of the time taken by the algorithm to complete.

Sorting Methods in Python

Bubble Sort

Bubble sort is the simplest way to sort the data which uses the brute force technique. It will iterate to each data element and compare it with other elements to provide the user with the sorted data.

Let us take an example to understand this technique:

• We are provided with an array having the elements “ 10, 40, 7, 3, 15 ”. Now, we need to arrange this array in an ascending order using the Bubble sort technique in Python.
  • The very first step is to arrange the array in the given order.
  • In the “ Iteration 1 ”, we are comparing the first element of an array with the other elements one by one.
  • The red arrows are describing the comparison of the first elements with the other elements of an array.
  • If you notice “ 10 ” is smaller than “ 40 ” so, it remains at the same place but the next element “ 7 ” is smaller than “ 10 ”. Hence it gets replaced and comes to the first place.
  • The above process will be performed again and again to sort the elements.

• • In the “ Iteration 2 ” the second element is getting compared with the other elements of an array.
  • If the compared element is small then, it will get replaced, otherwise it will remain at the same place.

• • In “ Iteration 3 “ the third element is getting compared with the other elements of an array.

• • In the last “ Iteration 4 “ the second last element is getting compared with the other elements of an array.
  • In this step the array is sorted in the ascending order.

Program for Bubble sort

```
def Bubble_Sort(unsorted_list):   
	for i in range(0,len(unsorted_list)-1):  
    	for j in range(len(unsorted_list)-1):  
        	if(unsorted_list[j]>unsorted_list[j+1]):  
            	temp_storage = unsorted_list[j]  
            	unsorted_list[j] = unsorted_list[j+1]  
            	unsorted_list[j+1] = temp_storage  
	return unsorted_list  
 	 
unsorted_list = [5, 3, 8, 6, 7, 2]  
print("Unsorted List: ", unsorted_list)  
print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) 

```

Output

Time Complexity of Bubble sort

• Worst Case: The worst time complexity for bubble sort is O(n²).
• Average Case: The average time complexity for bubble sort is O(n²).
• Best Case: The best time complexity for bubble sort is O(n).

Advantages

• It is mostly used and is easy to implement.
• We can swap the data elements without consumption of short-term storage.
• It requires less space.

Disadvantages

• It did not perform well while dealing with a large number of large data elements.
• It needs n² steps for each “n” number of data elements to get sorted.
• It is not really good for real-world applications.

Insertion Sort

Insertion sort is an easy and simple sorting technique that works similar to sorting the playing cards. Insertion sort sorts the elements by comparing each element one by one with the other. The elements are picked and swapped with the other element if the element is greater or smaller than the other.

Let’s take an example

• We are provided with an array having the elements “ 100, 50, 30, 40, 10 ”.
• First, we arrange the array and start comparing it.
• In the first step “ 100 ” is compared with the second element “ 50 ”. “ 50 ” is swapped with “ 100 ” as it is greater.
• In the second step, again the second element “ 100 ” is compared with the third element “ 30 ” and gets swapped.
• Now, if you notice “ 30 ” comes to the first place because it is again smaller than “ 50 ”.
• The comparison will occur till the last element of an array and at the end, we will get the sorted data.

Program for Insertion sort

```
def InsertionSort(array):
	for i in range(1, len(array)):
 
    	key_value = array[i]
    	j = i-1
    	while j >= 0 and key_value < array[j] :
            	array[j + 1] = array[j]
            	j -= 1
    	array[j + 1] = key_value

array = [11, 10, 12, 4, 5]
print("The unsorted array: ", array)
InsertionSort(array)
print ("The sorted array using the Insertion Sort: ")
for i in range(len(array)):
	print (array[i])

```

Output

Time Complexity of Insertion sort

• Worst Case: The worst time complexity for Insertion sort is O(n²).
• Average Case: The average time complexity for Insertion sort is O(n²).
• Best Case: The best time complexity for Insertion sort is O(n).

Advantages

• It is simple and easy to implement.
• It performs well while dealing with a small number of data elements.
• It does not need more space for its implementation.

Disadvantages

• It is not helpful to sort a huge number of data elements.
• When compared to other sorting techniques it does not perform well.

Merge sort

This sorting method uses the divide and conquer method to sort the elements in a specific order. While sorting with the help of merge sort, the elements are divided into halves and then, they get sorted. After sorting all the halves, again the elements get joined to form a perfect order.

Let’s take an example to understand this technique

• We are provided with an array “ 7, 3, 40, 10, 20, 15, 6, 5 ”. The array contains 7 elements. If we divide it into half ( 0 + 7 / 2 = 3 ).
• In the second step, you will see that the elements are divided into two parts. Each having 4 elements in it.
• Further, the elements are again divided and have 2 elements each.
• This process will continue until only one element is present in an array. Refer to step no. 4 in the picture.
• Now, we will sort the elements and start joining them as we were divided.
• In step no. 5 if you notice 7 is greater than 3, so we will exchange them and join it in the next step and vice versa.
• At the end, you will notice that our array is getting sorted in ascending order.

Program for Merge sort

```
def MergeSort(arr):
	if len(arr) > 1:

    	middle = len(arr)//2

    	L = arr[:middle]
    	R = arr[middle:]
    	MergeSort(L)
    	MergeSort(R)

    	i = j = k = 0
    	while i < len(L) and j < len(R):
        if L[i] < R[j]:
            	arr[k] = L[i]
            	i += 1
        else:
            	arr[k] = R[j]
            	j += 1
        k += 1

    	while i < len(L):
        	arr[k] = L[i]
        	i += 1
        	k += 1

    	while j < len(R):
        	arr[k] = R[j]
        	j += 1
        	k += 1

def PrintSortedList(arr):
	for i in range(len(arr)):
    	print(arr[i], end=" ")
	print()

arr = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
PrintSortedList(arr)
MergeSort(arr)
print("Sorted array is: ", end="\n")
PrintSortedList(arr)

```

Output

Time Complexity of Merge sort

• Worst Case: The worst time complexity for merge sort is O(n log(n)).
• Average Case: The average time complexity for merge sort is O(n log(n)).
• Best Case: The best time complexity for merge sort is O(n log(n)).

Advantages

• The file size does not matter for this sorting technique.
• This technique is good for the data which are generally accessed in a sequence order. For example, linked lists, tape drive, etc.

Disadvantages

• It requires more space when compared to other sorting techniques.
• It is comparatively less efficient than others.

Quick sort

Quick sort again uses the divide and conquer method to sort the elements of a List or an array. It targets the pivot elements and sorts the elements according to the selected pivot element.

For example

• We are provided with an array having the elements “ 1,8,3,9,4,5,7 ”.
• Let us assume “ 7 ” to be a pilot element.
• Now we will divide the array in such a manner that the left side contains the elements which are smaller than the pivot element “ 7 ” and the right side contains the elements greater than the pivot element “ 7 ”.
• We now have two arrays “ 1,3,4,5 ” and “ 8, 9 ”.
• Again, we have to divide both arrays just as the same as we did above. The only difference is that the pivot elements get changed.
• We need to divide the arrays till we get the single element in the array.
• At the end, collect all the pivot elements in a sequence from left to right and you will get the sorted array.

Program for Quick sort

```
def Array_Partition( arr, lowest, highest ):
	i = ( lowest-1 )
	pivot_element = arr[ highest ]
 
	for j in range( lowest, highest ):
    	if arr[ j ] <= pivot_element:
 
        	i = i+1
        	arr[ i ], arr[ j ] = arr[ j ], arr[ i ]
 
	arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ]
	return ( i+1 )

def QuickSort( arr, lowest, highest ):
	if len( arr ) == 1:
    	return arr
	if lowest < highest:
    	pi = Array_Partition( arr, lowest, highest )
 
    	QuickSort( arr, lowest, pi-1 )
    	QuickSort( arr, pi+1, highest )
 
arr = [ 9, 6, 7, 8, 0, 4 ]
n = len( arr )
print( " Unsorted array: ", arr )
QuickSort( arr, 0, n-1 )
print( " Sorted array using Quick Sort: " )
for i in range( n ):
	print( " %d " % arr[ i ] )

```

Output

Time Complexity of Quick sort

• Worst Case: The worst time complexity for Quick sort is O(n²).
• Average Case: The average time complexity for Quick sort is O(n log(n)).
• Best Case: The best time complexity for Quick sort is O(n log(n)).

Advantages

• It is known as the best sorting algorithm in Python.
• It is useful while handling large amount of data.
• It does not require additional space.

Disadvantages

• Its worst-case complexity is similar to the complexities of bubble sort and insertion sort.
• This sorting method is not useful when we already have the sorted list.

Heap sort

Heap sort is the advanced version of Binary search tree. In heap sort, the greatest element of an array is placed on the root of the tree always and then, compared with the root with the leaf nodes.

For example:

• We are provided with an array having the elements “ 40, 100, 30, 50, 10 ”.
• In “ step 1 ” we made a tree according to the presence of the elements in the array.

• In “ step 2 ” we are making a maximum heap i.e. to arrange the elements in the descending order. The greatest element will reside at the top (root) and the smallest element resides at the bottom (leaf nodes). The given array becomes “ 100, 50, 30, 40, 10 ”.

• In “ step 3 ”, we are making the minimum heap so that we can find the minimum elements of an array. By doing this, we get the maximum and the minimum elements.

• In “ step 4 ” by performing the same steps we get the sorted array.

Program for Heap sort

```
def HeapSortify( arr, n, i ):
	larger_element = i
	left = 2 * i + 1
	right = 2 * i + 2

	if left < n and arr[ larger_element ] < arr[ left ]:
    	larger_element = left
	if right < n and arr[ larger_element ] < arr[ right ]:
    	larger_element = right
	if larger_element != i:
    	arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ]
    	HeapSortify( arr, n, larger_element )

def HeapSort( arr ):
	n = len( arr )

	for i in range( n//2 - 1, -1, -1 ):
    	HeapSortify( arr, n, i )

	for i in range( n-1, 0, -1 ):
    	arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ]
    	HeapSortify( arr, i, 0 )
 
arr = [ 11, 10, 12, 4, 5, 6 ]
print( " The unsorted array is: ", arr )
HeapSort( arr )
n = len( arr )
print( " The sorted array sorted by the Heap Sort: " )
for i in range( n ):
	print( arr[ i ] )

```

Output

Time Complexity of Heap sort

• Worst Case: The worst time complexity for Heap sort is O(n log(n)).
• Average Case: The average time complexity for Heap sort is O(n log(n)).
• Best Case: The best time complexity for Heap sort isO(n log(n)).

Advantages

• It is mostly used because of its productivity.
• It can be implemented as an in-place algorithm.
• It does not require large storage.

Disadvantages

• Needs space for sorting the elements.
• It makes the tree for sorting the elements.

Comparison Between the Sorting Techniques

In the above comparison table “ O “ is the Big Oh notation explained above whereas “ n ” and “ N ” means the size of the input.

Frequently Asked Questions

Q #1) What is sort () in Python?

Answer: In Python sort() is a function that is used to sort the lists or arrays in a specific order. This function eases the process of sorting while working on the large projects. It is very helpful for the developers.

Q #2) How do you sort in Python?

Answer: Python provides various sorting techniques that are used to sort the element. For example, Quick sort, Merge sort, Bubble sort, Insertion sort, etc. All the sorting techniques are efficient and easy to understand.

Q #3) How does Python sort () work?

Answer: The sort() function takes the given array as an input from the user and sorts it in a specific order using the sorting algorithm. The selection of the algorithm depends upon the user choice. Users can use Quick sort, Merge sort, Bubble sort, Insertion sort, etc depending upon the user’s needs.

Conclusion

In the above tutorial, we discussed the sort technique in Python along with the general sorting techniques.

• Bubble Sort
• Insertion Sort
• Quick Sort

We learned about their time complexities and advantages & disadvantages. We also compared all the above techniques.

=> Visit Here To Learn Python From Scratch