Sorting Algorithms using Python

 

Code:

def selection_sort(arr):

    n = len(arr)

    for i in range(n):

        min_idx = i

        for j in range(i+1, n):

            if arr[j] < arr[min_idx]:

                min_idx = j

        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr

# Example usage:

arr = [64, 34, 25, 12, 22, 11, 90]

print("Original array:", arr)

sorted_arr = selection_sort(arr)

print("Sorted array:", sorted_arr)

#clcoding.com

Explanation: 

The selection_sort function sorts a given array arr in ascending order using the selection sort algorithm. Here's how it works:

Initialization:

Get the length of the array arr and store it in the variable n.

Outer Loop:

Iterate over each element of the array from index 0 to n-1.

For each iteration, consider the current element as the minimum (min_idx).

Inner Loop:

Within each outer loop iteration, iterate over the unsorted part of the array from index i+1 to n-1.

Find the index of the minimum element (min_idx) among the unsorted elements.

Swap:

After finding the minimum element in the unsorted part, swap it with the element at index i, which is the first element of the unsorted part.

Repeat:

Repeat steps 2-4 until the entire array is sorted.

Return Sorted Array:

Return the sorted array arr.

Now, let's walk through the provided example:

arr = [64, 34, 25, 12, 22, 11, 90]

We start with the original array [64, 34, 25, 12, 22, 11, 90].

sorted_arr = selection_sort(arr)

We call the selection_sort function with the array arr and store the sorted array in sorted_arr.

print("Sorted array:", sorted_arr)

We print the sorted array.

Output:

Original array: [64, 34, 25, 12, 22, 11, 90]

Sorted array: [11, 12, 22, 25, 34, 64, 90]

The original array is [64, 34, 25, 12, 22, 11, 90].

After sorting, the array becomes [11, 12, 22, 25, 34, 64, 90], which is printed as the sorted array.

Code:

def quick_sort(arr):

    if len(arr) <= 1:

        return arr

    pivot = arr[len(arr) // 2]

    left = [x for x in arr if x < pivot]

    middle = [x for x in arr if x == pivot]

    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

# Example usage:

arr = [64, 34, 25, 12, 22, 11, 90]

print("Original array:", arr)

sorted_arr = quick_sort(arr)

print("Sorted array:", sorted_arr)

#clcoding.com

Explanation: 

The quick_sort function implements the quicksort algorithm, a popular sorting algorithm known for its efficiency. Here's how it works:

Base Case:

If the length of the input array arr is 0 or 1, it is already sorted, so we return the array as is.

Pivot Selection:

Choose a pivot element from the array. In this implementation, the pivot is selected as the element at the middle index (len(arr) // 2).

Partitioning:

Partition the array into three sub-arrays:

left: Contains elements less than the pivot.

middle: Contains elements equal to the pivot.

right: Contains elements greater than the pivot.

Recursion:

Recursively apply the quicksort algorithm to the left and right sub-arrays.

Combine:

Concatenate the sorted left, middle, and right sub-arrays to form the sorted array.

Now, let's walk through the provided example:

arr = [64, 34, 25, 12, 22, 11, 90]

We start with the original array [64, 34, 25, 12, 22, 11, 90].

sorted_arr = quick_sort(arr)

We call the quick_sort function with the array arr and store the sorted array in sorted_arr.

print("Sorted array:", sorted_arr)

We print the sorted array.

Output:

Original array: [64, 34, 25, 12, 22, 11, 90]

Sorted array: [11, 12, 22, 25, 34, 64, 90]

The original array is [64, 34, 25, 12, 22, 11, 90].

After sorting, the array becomes [11, 12, 22, 25, 34, 64, 90], which is printed as the sorted array.

Code:

def bubble_sort(arr):

    n = len(arr)

    for i in range(n):

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

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

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

    return arr

# Example usage:

arr = [64, 34, 25, 12, 22, 11, 90]

print("Original array:", arr)

sorted_arr = bubble_sort(arr)

print("Sorted array:", sorted_arr)

#clcoding.com

Explanation:

The bubble_sort function implements the bubble sort algorithm, which repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Here's how it works:

Iteration:

The outer loop iterates through the entire array arr.

Each iteration (i) represents one pass through the array.

Comparison and Swapping:

The inner loop iterates from index 0 to n - i - 1.

Within each inner loop iteration (j), adjacent elements arr[j] and arr[j+1] are compared.

If arr[j] is greater than arr[j+1], they are swapped.

Largest Element Bubbles Up:

With each pass of the outer loop, the largest element in the unsorted part of the array "bubbles up" to its correct position at the end of the array.

Repeat Until Sorted:

Repeat steps 1-3 until the entire array is sorted.

Now, let's walk through the provided example:

arr = [64, 34, 25, 12, 22, 11, 90]

We start with the original array [64, 34, 25, 12, 22, 11, 90].

sorted_arr = bubble_sort(arr)

We call the bubble_sort function with the array arr and store the sorted array in sorted_arr.

print("Sorted array:", sorted_arr)

We print the sorted array.

Output:

Original array: [64, 34, 25, 12, 22, 11, 90]

Sorted array: [11, 12, 22, 25, 34, 64, 90]

The original array is [64, 34, 25, 12, 22, 11, 90].

After sorting, the array becomes [11, 12, 22, 25, 34, 64, 90], which is printed as the sorted array.

Code:

def insertion_sort(arr):

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

        key = arr[i]

        j = i - 1

        while j >= 0 and key < arr[j]:

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = key

    return arr

# Example usage:

arr = [64, 34, 25, 12, 22, 11, 90]

print("Original array:", arr)

sorted_arr = insertion_sort(arr)

print("Sorted array:", sorted_arr)

#clcoding.com

Explanation:

The insertion_sort function implements the insertion sort algorithm, which builds the final sorted array one element at a time by repeatedly moving elements that are out of order. Here's how it works:

Iteration:

The outer loop iterates over the array arr, starting from index 1.

Each iteration (i) considers one element at a time, starting from the second element.

Key Selection:

Within each iteration, the current element (arr[i]) is selected as the key to be inserted into the sorted sub-array.

Comparison and Shifting:

The inner loop (while loop) compares the key with the elements in the sorted sub-array (elements before arr[i]).

Elements greater than the key are shifted one position to the right to make space for the key.

This shifting continues until an element less than or equal to the key is found, or until the beginning of the array is reached (j < 0).

Insertion:

Once the correct position for the key is found, it is inserted into the sorted sub-array at index j + 1.

Repeat Until Sorted:

Repeat steps 1-4 until the entire array is sorted.

Now, let's walk through the provided example:

arr = [64, 34, 25, 12, 22, 11, 90]

We start with the original array [64, 34, 25, 12, 22, 11, 90].

sorted_arr = insertion_sort(arr)

We call the insertion_sort function with the array arr and store the sorted array in sorted_arr.

print("Sorted array:", sorted_arr)

We print the sorted array.

Output:

Original array: [64, 34, 25, 12, 22, 11, 90]

Sorted array: [11, 12, 22, 25, 34, 64, 90]

The original array is [64, 34, 25, 12, 22, 11, 90].

After sorting, the array becomes [11, 12, 22, 25, 34, 64, 90], which is printed as the sorted array.