Sorting Algorithms: QuickSort and MergeSort

Sorting algorithms are fundamental for efficiently organizing data. Two commonly used sorting algorithms are QuickSort and MergeSort.

QuickSort

QuickSort is a comparison-based algorithm that follows the divide-and-conquer approach. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Here is an example implementation of QuickSort in Python:

1{code}

MergeSort

MergeSort is also a comparison-based algorithm that follows the divide-and-conquer approach. It works by recursively dividing the array into two halves, sorting each half separately, and then merging the two sorted halves.

Here is an example implementation of MergeSort in Python:

1def mergeSort(arr):
2    if len(arr) > 1:
3        mid = len(arr) // 2
4        left_half = arr[:mid]
5        right_half = arr[mid:]
6
7        mergeSort(left_half)
8        mergeSort(right_half)
9
10        # Merge the sorted halves
11        i = j = k = 0
12
13        while i < len(left_half) and j < len(right_half):
14            if left_half[i] < right_half[j]:
15                arr[k] = left_half[i]
16                i += 1
17            else:
18                arr[k] = right_half[j]
19                j += 1
20            k += 1
21
22        while i < len(left_half):
23            arr[k] = left_half[i]
24            i += 1
25            k += 1
26
27        while j < len(right_half):
28            arr[k] = right_half[j]
29            j += 1
30            k += 1
31
32
33# Example usage
34arr = [64, 34, 25, 12, 22, 11, 90]
35mergeSort(arr)
36print(arr)

These sorting algorithms have different time complexities and can be used depending on the specific requirements of the application.

xxxxxxxxxx

print(arr)

# Quicksort implementation

​

def partition(arr, low, high):

    # Select the pivot element

    pivot = arr[high]

​

    # Initialize the partition index

    i = low - 1

​

    for j in range(low, high):

        # If the current element is smaller than the pivot

        if arr[j] < pivot:

            i += 1

            arr[i], arr[j] = arr[j], arr[i]

​

    # Swap the pivot element with the element at the partition index

    arr[i+1], arr[high] = arr[high], arr[i+1]

​

    return i + 1

​

​

def quicksort(arr, low, high):

    if low < high:

        # Find the partition index

        pi = partition(arr, low, high)

​

        # Recursively sort the two halves

        quicksort(arr, low, pi-1)

        quicksort(arr, pi+1, high)