Sorting Algorithms

That has a paragraph about a main subject and is set when the ‘=’ is at least the same length of the title itself.

Merge Sort

This is the basic method i should master, the top-down merge_sort implementation:

def merge_sort(nums):
    def merge(leftnums, rightnums):
        i,j = 0,0
        res = []
        while(i<len(leftnums) and j <len(rightnums)):
            if leftnums[i]<rightnums[j]:
                res.append(leftnums[i])
                i += 1
            else:
                res.append(rightnums[j])
                j += 1
        while(i<len(leftnums)):
            res.append(leftnums[i])
            i += 1
        while (j < len(rightnums)):
            res.append(rightnums[j])
            j += 1
        return res
    if len(nums)==1:
        return nums

    mid = len(nums)/2
    leftnums = merge_sort(nums[:mid])
    rightnums = merge_sort(nums[mid:])
    return merge(leftnums, rightnums)

    i write megersort, buble sort, insertion sort and selection sort today.

    however, computer crashes!!! damn!

Quick Sort

This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot.

Implementation:

def partition(arr,low,high):
    i = ( low-1 )         # index of smaller element
    pivot = arr[high]     # pivot

    for j in range(low , high):

        # If current element is smaller than or
        # equal to pivot
        if   arr[j] <= pivot:

            # increment index of smaller element
            i = i+1
            arr[i],arr[j] = arr[j],arr[i]

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

# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low  --> Starting index,
# high  --> Ending index

# Function to do Quick sort
def quickSort(arr,low,high):
    if low < high:

        # pi is partitioning index, arr[p] is now
        # at right place
        pi = partition(arr,low,high)

        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)