Tag: algorithms

Understanding and Implementing Merge Sort In Python

Previously, we’ve covered  binary search and selection sort. This time, we’ll be covering another sorting algorithm – merge sort. Merge sort is a little different from selection sort. While selection sort can’ only be used to sort an unsorted list, merge sort can be utilized to merge two different sorted lists, in addition to sorting an unsorted list. 

The core idea of merge sort is an instance of a divide and conquer approach. First, the entire list/array is split apart into left and right halves. Afterwards, the left half of the array is also divided in half. This recurs until there is only one element in the left and right halves, until the array halves cannot be split further. Afterwards, the values are merged together, being compared and place in sorted order.

This process recurs, gradually sorting and merging groups, until there is only one group with all the elements in their proper order. It is critical to remember that every-time a group is created the sorted order must be maintained.

Here’s an example of the technique, broken into dividing and merging phases.

Dividing Phase:

Assuming we have an array with the following values: [3, 8, 9, 2, 6, 7], the process will look something like this.

Division 1: [3, 8, 9][2, 6, 7]

Division 2: [3] [8, 9] [2] [6,7]

Division 3: [3] [8] [9] [2] [6] [7]

Now comes the merging phase.

Merging Phase:

Merge 1: [3, 8] [2,9] [6,7]

Merge 2: [2, 3, 8, 9][6, 7]

Merge 3: [2, 3, 6, 7, 8, 9]

If two lists are being merged, it is important to compare the elements before they are merged into a single list. Otherwise, the merged list will contain all the sorted elements of one list and then all the sorted elements of the other list.

So let’s make sure we understand the steps to implementing merge sort:

  1. We start with an unsorted list and split it in half.

2. We split the left half of the array into halves.

3. We keep splitting until there is just one element per half.

4. We compare each of the elements

5. The elements are merged into one group, in order.

6. The process continues until the entire array has been sorted and merged.

Now we can try writing merge sort in Python.

This implementation will be  a recursive implementation. When writing a recursive algorithm, remember that the algorithm must have a base-case, or a case where the recursion ends.

In order to implement merge sort in Python, the algorithm can be structured as follows:

def merge_sort(array):
    # Only if there are two or more elements
    if len(array) > 1:
        # get the midpoint in the array
        mid = len(array) // 2
        # left half is everything before the mid
        left = array[:mid]
        # right half is everything after the midpoint
        right = array[mid:]

        # recur the splits on the left and right halves
        merge_sort(left)
        merge_sort(right)

        # we need variables to track the iteration through the arrays
        x = 0
        y = 0

        # Iterator for the main list
        z = 0

        # here we copy the data into temporary arrays that store the left and right halves
        # as long as there are still values within the left and right half of the arrays
        # compare the values and swap positions

        while x < len(left) and y < len(right):
            # if left value is smaller than the right value
            if left[x] <= right[y]:
                # place the left position into the sorted array
                array[z] = left[x]
                # update left position
                x = x + 1
            else:
                array[z] = right[y]
                y = y + 1
            # move to the next portion of the array
            z = z + 1

        # If there are any elements left over in the left half of the array
        # We fill in the primary array with the remaining left values and then move the iterators up
        while x < len(left):
            array[z] = left[x]
            x += 1
            z += 1

        # Do the same thing for the right half of the array
        while y < len(right):
            array[z] = right[y]
            y += 1
            z += 1

listy = [35, 72, 29, 55, 41, 27, 79, 11, 23, 56, 50]
merge_sort(listy)
print(listy)

Here’s the sorted list:

[11, 23, 27, 29, 35, 41, 50, 55, 56, 72, 79]

Understanding and Implementing Quick Sort in Python

Last time I covered the theory and implementation of binary search, but now let’s turn to sort algorithms. Before an array can be searched, it must be sorted. One of the most efficient sorting algorithms is Quick Sort, and we’ll be exploring how to implement Quick Sort in Python below. However, let’s go over the theory behind Quick Sort first. 

Quicksort is an example of applying a divide-and-conquer approach to solving a problem. We can make sorting a large array of unsorted value easy by dividing the problem down into smaller steps and just applying these steps again and again until the array is sorted.

The primary concept employed in Quick Sort is partitioning. As we partition, we divide the array into smaller portions and then sort these small chunks. How do we sort the small portions of the array? We do this by first selecting a pivot, or a point in the array that the rest of the array will be shifted around.

After we select the pivot, we need to put the pivot in its correct position in the array. This means making sure that all values in the array smaller than the pivot are to the left and all values that are larger are to the right. We then recur on the right and left half of the array until everything is sorted.

Essentially, we can describe the algorithm as the following steps:

  1. Choose a value as the pivot
  2. Iterate through the array and  place all values smaller than the pivot the left, while all the values larger are to the right. This is done by comparing every value to the pivot. If a value is found that is out of order, the current value and the last sorted element are swapped.
  3. After the above process is completer, the process is carried out on all the values to the left of the pivot value. 
  4. The process is carried out again on all values to the right of the pivot.

How do you go about selecting a pivot value? There are multiple ways to select a pivot value. You can select the first value in the array, the last value in the array, the median value, or a random value.

The most common way that Quick Sort is implemented is by using the last value in the array as the pivot. The example implementation below will use the method where the final element in the array is chosen as the pivot.

Now we’ll take a look at how to implement QuickSort in Python.

To begin with, we’ll create a function that partitions the array. We’ll then use this function within another function to carry out the actual sorting. 

def partition(arr, low, high):

    # idx is the current index of the smaller array
    idx = (low - 1)
    pivot = arr[high]

    # c is current value in the loop
    for c in range(low, high):
        if arr[c] < pivot:
            idx = idx + 1

            arr[idx], arr[c] = arr[c], arr[idx]

    arr[idx + 1], arr[high] = arr[high], arr[idx + 1]
    return (idx + 1)

def quick_sort(arr, low, high):

    if low < high:
        p_idx = partition(arr, low, high)

        quick_sort(arr, low, p_idx-1)
        quick_sort(arr, p_idx+1, high)

arr = [12, 28, 33, 11, 38, 49, 36, 19, 100, 21, 5, 15, 3]
length = len(arr)
quick_sort(arr, 0, length - 1)
print("Array after sorting:")
for i in range(length):
    print(arr[i])

Here’s the results of running the program:

Array after sorting:
3
5
11
12
15
19
21
28
33
36
38
49
100

I suggest you experiment with different sorting algorithms as well as see how run times can vary when sorting arrays under different conditions.

Design a site like this with WordPress.com
Get started