Sorting Algorithms in Python

What is Sorting?

Sorting refers to the process of arranging data in a specific order, typically in ascending or descending order, based on a linear relationship among the data items.

Why Do We Need Sorting?

Sorting is crucial when working with structured data because it allows for efficient data retrieval, simplifies data analysis, and enhances overall data management.

Sorting Algorithms

This post covers the following sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort.

Bubble Sort

Bubble Sort repeatedly steps through the array, comparing adjacent elements and swapping them if they are in the wrong order. This process continues until the array is sorted, with larger elements "bubbling" to the end.

Algorithm

Step 1: Begin
Step 2: i = 0
Step 3: if i Step 4: j = 0
Step 5: if j Step 6: if array[j] > array[j + 1], goto Step 7; else goto Step 8
Step 7: Swap array[j] and array[j + 1]
Step 8: increment j; goto Step 5
Step 9: increment i; goto Step 3
Step 10: End

Code

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

Time Complexity

Best Case : O(n)
Average Case : O(n^2)
Worst Case : O(n^2)

Selection Sort

Selection Sort finds the smallest value in the unsorted portion of the array and places it at the beginning of that portion.

Algorithm

Step 1 : Begin
Step 2 : i = 0
Step 3 : if i Step 4 : minimum_value = i; j = i + 1
Step 5 : if j Step 6 : if array[minimum_value] > array[j], goto Step 7; else goto Step 8
Step 7 : minimum_value = j
Step 8 : increment j; goto Step 5
Step 9 : swap array[minimum_value] and array[i]
Step 10 : increment i; goto Step 3
Step 11 : End

Code

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i + 1, len(arr)):
            if arr[j] 



<h4>
  
  
  Time Complexity
</h4>

<p>Best Case : O(n^2)<br>
Average Case : O(n^2)<br>
Worst Case : O(n^2)  </p>

<h3>
  
  
  Insertion Sort
</h3>

<p>Insertion Sort builds the sorted array one element at a time by taking each element from the unsorted portion and inserting it into the correct position in the sorted portion.</p>

<h4>
  
  
  Algorithm
</h4>

<p>Step 1: Begin<br>
Step 2: i = 1<br>
Step 3: if i 
Step 4: key = arr[i]<br>
Step 5: j = i - 1<br>
Step 6: if j >= 0 and arr[j] > key, goto Step 7; else goto Step 10<br>
Step 7: arr[j + 1] = arr[j]<br>
Step 8: decrement j by 1<br>
Step 9: goto Step 6<br>
Step 10: arr[j + 1] = key<br>
Step 11: increment i by 1; goto Step 3<br>
Step 12: End</p>

<h4>
  
  
  Code
</h4>



<pre class="brush:php;toolbar:false">def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)

Time Complexity

Best Case : O(n)
Average Case : O(n^2)
Worst Case : O(n^2)

Merge Sort

Merge Sort is a divide-and-conquer algorithm that recursively divides the array into smaller sub-arrays, sorts them, and then merges them back together.

Algorithm

Merge Sort Algorithm

Step 1: Begin
Step 2: If length(array) Step 3: mid_point = length(array) // 2
Step 4: left_half = array[:mid_point]
Step 5: right_half = array[mid_point:]
Step 6: sorted_left = merge_sort(left_half)
Step 7: sorted_right = merge_sort(right_half)
Step 8: return merge(sorted_left, sorted_right)
Step 9: End

Merge Function

Step 1: Begin
Step 2: sorted_merge = []
Step 3: l = 0, r = 0
Step 4: if l Step 5: if left[l] Step 6: add left[l] to sorted_merge; increment l by 1
Step 7: add right[r] to sorted_merge; increment r by 1
Step 8: goto Step 4
Step 9: if l Step 10: add left[l] to sorted_merge; increment l by 1
Step 11: goto Step 9
Step 12: if r Step 13: add right[r] to sorted_merge; increment r by 1
Step 14: goto Step 12
Step 15: Return sorted_merge
Step 16: End

Code

def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l 



<h4>
  
  
  Time Complexity
</h4>

<p>Best Case : O(n log n)<br>
Average Case : O(n log n)<br>
Worst Case : O(n log n)  </p>

<h3>
  
  
  Quick Sort
</h3>

<p>Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.</p>

<h4>
  
  
  Algorithm
</h4>

<p><strong>Quick Sort</strong><br><br>
Step 1: Begin<br>
Step 2: If low 
Step 3: pivot_index = partition(arr, low, high)<br>
Step 4: quicksort(arr, low, pivot_index - 1)<br>
Step 5: quicksort(arr, pivot_index + 1, high)<br>
Step 6: End  </p>

<p><strong>Partition Function</strong><br><br>
Step 1: Begin<br>
Step 2: pivot = arr[high]<br>
Step 3: left = low, right = high - 1<br>
Step 4: if left 
Step 5: if arr[left] > pivot and arr[right] 
Step 6: if arr[left] 
Step 7: if arr[right] >= pivot, decrement right<br>
Step 8: goto Step 4<br>
Step 9: swap arr[left] and arr[high]<br>
Step 10: return left<br>
Step 11: End  </p>

<h4>
  
  
  Code
</h4>



<pre class="brush:php;toolbar:false">def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left  pivot and arr[right] = pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low 



<h4>
  
  
  Time Complexity
</h4>

<p>Best Case : O(n log n)<br>
Average Case : O(n log n)<br>
Worst Case : O(n^2)</p>


          

            
        

The above is the detailed content of Sorting Algorithms in Python. For more information, please follow other related articles on the PHP Chinese website!