Sorting algorithms in python with examples

Sorting algorithms in python with examples

Here's a comprehensive guide to sorting algorithms in Python, along with examples:

1. Bubble Sort

Bubble sort is the simplest sorting algorithm that works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order.

Python Code:

def bubble_sort(lst):
n = len(lst)
for i in range(n-1):
for j in range(0, n-i-1):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

2. Selection Sort

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from unsorted part and putting it at the beginning.

Python Code:

def selection_sort(lst):
n = len(lst)
for i in range(n-1):
min_index = i
for j in range(i+1, n):
if lst[j] < lst[min_index]:
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
return lst
print(selection_sort([64, 34, 25, 12, 22, 11, 90]))

3. Insertion Sort

Insertion sort is a simple sorting algorithm that works by building the final sorted array one item at a time.

Python Code:

def insertion_sort(lst):
for i in range(1, len(lst)):
key = lst[i]
j = i-1
while j >= 0 and key < lst[j]:
lst[j+1] = lst[j]
j -= 1
lst[j+1] = key
return lst
print(insertion_sort([64, 34, 25, 12, 22, 11, 90]))

4. Quick Sort

Quick sort is a popular sorting algorithm that uses the divide-and-conquer strategy.

Python Code:

def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[len(lst) // 2]
left = [x for x in lst if x < pivot]
middle = [x for x in lst if x == pivot]
right = [x for x in lst if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([64, 34, 25, 12, 22, 11, 90]))

5. Merge Sort

Merge sort is a stable sorting algorithm that works by dividing the input into two halves and merging them in sorted order.

Python Code:

def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([64, 34, 25, 12, 22, 11, 90]))

6. Heap Sort

Heap sort is a comparison-based sorting algorithm that uses the heap data structure.

Python Code:

def heap_sort(lst):
def heapify(lst, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and lst[i] < lst[l]:
largest = l
if r < n and lst[largest] < lst[r]:
largest = r
if largest != i:
lst[i], lst[largest] = lst[largest], lst[i]
heapify(lst, n, largest)
def build_heap(lst):
n = len(lst)
for i in range(n//2-1, -1, -1):
heapify(lst, n, i)
build_heap(lst)
for i in range(len(lst)-1, 0, -1):
lst[0], lst[i] = lst[i], lst[0]
heapify(lst, i, 0)
return lst
print(heap_sort([64, 34, 25, 12, 22, 11, 90]))

7. Radix Sort

Radix sort is a non-comparison sorting algorithm that works by sorting the elements based on their digits.

Python Code:

def radix_sort(lst):
max_length = max(len(str(x)) for x in lst)
buckets = [[] for _ in range(10)]
for length in range(max_length-1, -1, -1):
for num in lst:
digit = (num // 10 ** length) % 10
buckets[digit].append(num)
lst = [num for bucket in buckets for num in bucket]
buckets = [[] for _ in range(10)]
return lst
print(radix_sort([64, 34, 25, 12, 22, 11, 90]))

These are some of the most common sorting algorithms implemented in Python. Each algorithm has its own strengths and weaknesses, and the choice of which one to use depends on the specific requirements of your project.

Types of sorting in Python

I'd be happy to respond in English and provide a detailed explanation of the types of sorting algorithms available in Python.

Python offers several built-in sorting functions, including sort() and sorted(), as well as various third-party libraries that can enhance your data manipulation capabilities. Here's an overview of the main sorting techniques:

Python's built-in sort() function uses a variation of the quicksort algorithm called "timsort" (a hybrid of merge sort and insertion sort) for stability and efficiency. You can also implement quicksort manually using Python's recursive functions and conditional statements.

Python's built-in sorted() function uses a variant of merge sort called "timsort" (again!) for stability and efficiency. You can also implement merge sort manually using Python's recursive functions and conditional statements.

You can implement heapsort manually using Python's built-in heapq module or by using a priority queue. Python doesn't have a built-in heapsort function, but you can use the sorted() function in combination with heapq.nlargest() to achieve similar results.

Python's built-in insert() function for lists is essentially an implementation of insertion sort. You can also implement insertion sort manually using Python's loop and conditional statements.

You can implement selection sort manually using Python's loop and conditional statements. Python doesn't have a built-in selection sort function, but you can use the sorted() function in combination with min() or max() to achieve similar results.

You can implement radix sort manually using Python's loop and conditional statements or use a third-party library like numba. Python doesn't have a built-in radix sort function, but you can use the sorted() function in combination with custom sorting functions to achieve similar results.

You can implement bucket sort manually using Python's loop and conditional statements or use a third-party library like numba. Python doesn't have a built-in bucket sort function, but you can use the sorted() function in combination with custom sorting functions to achieve similar results.

You can implement shell sort manually using Python's loop and conditional statements or use a third-party library like numba. Python doesn't have a built-in shell sort function, but you can use the sorted() function in combination with custom sorting functions to achieve similar results.

Python's built-in sort() function uses timsort as its default sorting algorithm, providing efficient and stable sorting capabilities.

In summary, Python offers various built-in and third-party libraries that support different sorting algorithms. By understanding the characteristics of each sorting technique, you can choose the most suitable one for your specific use case or even implement a custom sorting algorithm to optimize performance.