Python Sorting Algorithms Tutorial

Sorting refers to the process of arranging data in a specific sequence. This data, often numerical, is organized by employing sorting algorithms that can either sort in ascending or descending order. It serves to present data in a more understandable manner and is a fundamental aspect of computer science. If the sorting techniques employed are not efficient, sorting a large dataset may consume significant computational resources. The efficiency of the algorithm is directly proportional to the quantity of items being processed. A complex sorting method may prove to be more laborious than advantageous for smaller datasets. Conversely, our goal is to enhance efficiency and speed when dealing with larger volumes of data. Various sorting techniques will be explored, along with an analysis of their time complexity.

The following are a few actual-world instances of sorting:

• ✅ Telephone Directory: This book lists people's names, phone numbers, and addresses.
• ✅ Dictionary: It is a sizable database of words and their definitions organized alphabetically.
• ✅ Contact List: A contact list is an alphabetical list of each person's contact information on a mobile phone.

It is essential to examine the activities that can be employed for evaluating a planning process before discussing the various techniques for sorting the information provided to us. A systematic approach will be necessary to compare values and ascertain whether they are in harmony. Initially, we need to compare the attributes to identify which is lesser and which is greater, so that they can be organized in a sequential order.

The various varieties of the order include:

• ✅ Increasing Order: When each element after the first is bigger than before, a set of values is said to be in ascending order. as in 1, 2, 3, 4, and 5. The series is listed here in ascending order.
• ✅ Decreasing Order: When an element in a collection of values is always smaller than the one before it, the values are said to be in descending order. Examples include: 5, 4, 3, 2, 1. Here, the order of the list is decreasing.
• ✅ Non-Increasing Order: If every ith element in a series of values is greater than or equal to its (i-1) th element, the values are said to be in non-increasing order. When there are repeated numerals, they appear in this sequence, like 1, 2, 2, 3, 4, and 5. Here, 2 was repeated twice.
• ✅ Non-Decreasing Order: If every ith member in a series of values is less than or equal to its (i-1) th element, the set of values is said to be in non-decreasing order. When there are repeated numerals, they appear in this sequence. Example: 5, 4, 3, 2, 1, etc. Here, 2 was repeated twice.

Sorting Techniques

The many sorting methods that Python implements include:

• ✅ Bubble Sort
• ✅ Selection Sort
• ✅ Insertion Sort

Bubble Sort

Bubble sort is a straightforward sorting algorithm. This sorting method continuously examines the positions of two adjacent elements, swapping them when necessary. It is also referred to as sinking sort. Its time complexity is O(n²) in both average and worst-case scenarios, while in the best-case scenario, it achieves O(n). In a bubble sort, participants can rearrange themselves by exchanging positions in such a way that they can all alternate in ascending order of their heights.

In other terms, we assess two adjacent elements to ascertain if their arrangement is not correct; if that is the case, we exchange their positions. For an array to be organized in ascending order, it follows that arr[i] > arr[j] and the opposite holds true, where s represents the size of the array.

Bubble Sort Example

In this instance, we will apply bubble sort to arrange the subsequent list.

Sequence: 5,18,3,14

First Iteration

(5,18,3,14) -> (5,18,3,14), in this instance, the initial two elements are evaluated, yet they remain unchanged as they are already arranged in ascending order.

(5,18,3,14) -> (5,3,18,14). In this instance, the second and third elements are evaluated and rearranged in increasing order (10 is less than 23).

(5,18,3,14) -> (5,3,14,18). In this instance, the third and fourth elements are evaluated and rearranged in increasing order (1 is less than 23).

After the initial iteration, the largest element that has been correctly sorted occupies the rightmost position.

Second Iteration

(5,3,14,18) -> (5,3,14,18). Once more, because they are already arranged in increasing order, the initial two elements are evaluated and remain unchanged.

The leftover elements are sorted during the initial pass. By the conclusion of the second pass, the array is arranged in ascending order. Therefore, the ultimate outcome is 3, 5, 14, 18.

Third Iteration

(3,5,14,18) -> (3,5,14,19). Here, the leading two elements are evaluated and exchanged to arrange them in ascending order.

The leftover elements have been organized during the initial two iterations. Following the third iteration, the designated array is arranged in ascending order. The result is 3, 5, 14, 18.

Implementation of Bubble Sort in Python

Let's consider an example to illustrate the implementation of bubble sort in Python.

# Implementing the Bubble Sort Algorithm in Python 3

def bubbleSort(arr):

    n = len(arr)

    # For loop to iterate through all

    # components of an array

    for i in range(n):

        for j in range(0, n - i - 1):

            # The array's range is 0 to n-i-1.

            # If an element is discovered, swap the elements.

            #is larger than the element in front of it.

            if arr[j] > arr[j + 1]:

                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# Driver code

# Example to test the above code

arr = [ 3,5,14,18 ]

bubbleSort(arr)

print("Sorted array is:")

for i in range(len(arr)):

    print("%d" % arr[i])

Output:

Sorted array is:

3

5

14

18

• ✅ Time Complexity: O(n^2)
• ✅ Auxiliary Space: O(1)

Selection Sort

This sorting technique continuously identifies the smallest element and organizes it in increasing order. Bubble Sort requires no additional RAM. During the operation of this technique, two subarrays are kept: one that is sorted and another that remains unsorted. In each iteration of Selection Sort, the least element from the unsorted subarray is moved into the sorted subarray. Selection Sort is considered more efficient than Bubble Sort. The Time Complexity for average, worst, and best-case scenarios of this sorting method is O(n^2).

Selection Sort Example

In this instance, we will apply the selection sort algorithm to arrange the subsequent sequence.

Sequence: 9, 4, 3, 8

(9, 4, 3, 8) -> (3, 9, 4, 8), The smallest element, which is 3, is identified during the initial pass and occupies the leading position.

(3, 9, 4, 8) -> (3, 4, 9, 8), It identifies the second smallest element, which is 4, during the second pass and places it in the second position.

(3, 4, 9, 8) -> (3, 4, 8, 9). In the subsequent traversal, the next smallest element, 8, is identified and placed in the third position.

The concluding array is arranged in a sorted sequence following the aforementioned iterations, specifically: 3, 4, 8, 9.

Implementation of Selection Sort in Python

Let's consider an example to demonstrate the implementation of selection sort in Python.

# Selection Sort algorithm in Python

def selectionSort(array, size):

    for s in range(size):

        min_idx = s

        for i in range(s + 1, size):

            #for minimum element in each loop when sorting in descending order

            if array[i] < array[min_idx]:

                min_idx = i

        # Placing min at the appropriate location

        (array[s], array[min_idx]) = (array[min_idx], array[s])

# Driver code

data = [ 9, 4, 3, 8]

size = len(data)

selectionSort(data, size)

print('Sorted Array in Ascending Order is :')

print(data)

Output:

Sorted Array in Ascending Order is :

[3, 4, 8, 9]

• ✅ Time Complexity: O(n^2)
• ✅ Auxiliary Space: O(1)

Insertion Sort

This sorting technique ensures that a sub-array remains consistently sorted. Elements from the unsorted segment of the array are accurately placed within the sorted segment. In comparison to methods such as bubble sort or selection sort, this approach demonstrates greater efficiency in real-world applications. The average and worst-case Time Complexity of Insertion Sort is O(n^2), while the best-case Time Complexity is O(n).

Insertion Sort Example

In this instance, we will apply the insertion sort algorithm to arrange the subsequent sequence.

Sequence: 7, 2, 1, 6

(7, 2, 1, 6) -> (2, 7, 1, 6). In the initial iteration, the first two elements are compared; since 2 is less than 7, it is positioned before 7.

(2, 7, 1, 6) -> (2, 1, 7, 6). During the second iteration, the second and third elements are evaluated; here, 1 is smaller than 7, which results in 1 being positioned before 7.

(2, 1, 7, 6) -> (1, 2, 7, 6). Due to the fact that the elements (1, 7) are not arranged in ascending order following the second occurrence, 1 is positioned ahead of 2.

(1, 2, 7, 6) -> (1, 2, 6, 7). Following the exchange of each prior element within this cycle, the final two elements are evaluated and modified.

Implementation of Insertion Sort in Python

Let us illustrate an example of how to execute the insertion sort algorithm using Python.

# The development of an insertion sort function

def insertion_sort(list1):

        # Len(list1) outer loop to traverse

        for i in range(1, len(list1)):

            a = list1[i]

            # List1[0 to i-1],

           # Bigger elements should be moved one position

           # forward of where they are now at.

            j = i - 1

            while j >= 0 and a < list1[j]:

                list1[j + 1] = list1[j]

                j -= 1

            list1[j + 1] = a

        return list1

# Driver code

list1 = [ 7, 2, 1, 6 ]

print("The unsorted list is:", list1)

print("The sorted new list is:", insertion_sort(list1))

Output:

The unsorted list is: [7, 2, 1, 6]

The sorted new list is: [1, 2, 6, 7]

• ✅ Time Complexity: O(n^2)
• ✅ Auxiliary Space: O(1)