Counting number of inversion in an array (python)

def count_inversion(array):
    (count,sorted_array) = count_inversion_helper(array)
    return count

def count_inversion_helper(array1):
    """"
    counts the number for inversion in one array we assume the inversions
    are related to sorted array from
     0 to n (pep8 tested with 10.0 score)
    :author name: Tanmay Datta
    :param array1: array to count (list type)
    :return: number of inversoin
    :type array1: List(Num)
    """"
    length = len(array1)
    if length <= 1:
        #Trivial case and no inversion
        return (0, array1)
    if length == 2:
        if array1[0] &amp< array1[1]:
            return (0, array1)
        else:
            return (1, [array1[1], array1[0]]) # sorted array
    else:
        half = length/2
        right_array = array1[half:]
        (left_inversion, left_array) = count_inversion_helper(array1[:half])
        (right_inversion, right_array) = count_inversion_helper(array1[half:])
        sorted_array = []
        left_idx = 0
        right_idx = 0
        left_size = len(left_array)
        right_size = len(right_array)
        total_inversions = left_inversion + right_inversion
        while True:
            if right_array[right_idx] < left_array[left_idx]:
                sorted_array.append(right_array[right_idx])
                total_inversions += left_size - left_idx
                right_idx += 1

            else:
                sorted_array.append(left_array[left_idx])
                left_idx += 1
            if left_idx >= left_size:
                sorted_array += right_array[right_idx:]
                break
            if right_idx >= right_size:
                sorted_array += left_array[left_idx:]
                break
        return (total_inversions, sorted_array)

Another funky implementation which uses a “bisect” function already given by python libraries

import bisect

def ms_funky(arr):

sorted_array = sorted(arr)

r = 0

for n in arr:

    pos = bisect.bisect_left(sorted_array,n)

    r += pos

    sorted_array.pop(pos)

return r

Advertisements

Merge sort in python (implementation,testing,re implementation, style fix)

I am taking one online course on algorithms and thought would write a programming tutorial (or at least my thought process) along with implementation of merge-sort algorithm.

————————— merge-sort rules——————————-

If array size is 1 it’s always sorted

If array size is 2 then sorting is trivial and could be done as (if a[1] < a[2] then good otherwise reverse it)

In all other case divide array in 2 parts and perform sort individually.

Once both sided are sorted the merge them back iteratively by checking each element one by one in  the half array

—————————————-First attempt ————————————————-

def merge_sort(arr):

l = len(arr)

if l <= 1:

    return arr

elif l ==2:

if arr[0] < arr[1]:

    return arr

else:

    return [arr[1], arr[0]]

else:

    half = l // 2

    left = merge_sort(arr[:half])

    right = merge_sort(arr[half:])

    sorted_arr = []

    for idx in xrange(0,half):

    if left[0] <= right[0]:

        v = left.pop(0)

    else:

        v = right.pop(0)

    sorted_arr.append(v)

    sorted_arr = sorted_arr + left + right

    return sorted_arr

Looks ok (hmmm!!!!)

As a programmer the most important thing that you need to check a code for is ____ –>

“Correctness”

let’s write some tests

What are good tests ?

1. Checks for “common” values correctness

2. Checks for “extreme” cases correctness

3. Checks for exceptions and correctness

from back of my mind I can think of following cases

test1 = [1,2,3,4,5,6] (Checks what happens when array is already sorted)

test2 = [4,3,1,7,6,5] (checks for the real sorting problem under normal kind of case (even numbers)

test3 = [4,3,1,7,6,5,2]  (checks similar to test 2 along just odd numbers)

test4 = [] (Extreme case when array is empty)

test5 = [4,4,4,4,4] (Extreme case when all elements are same)

test6 =[2,2,1,1,5,3,6,100] (Not extreme but good case having some duplicates)

———————————————Input————————————————-


test1 = [1,2,3,4,5,6]

test2 = [4,3,1,7,6,5]

test3 = [4,3,1,7,6,5,2]

test4 = []

test5 = [4,4,4,4,4]

test6 =[2,2,1,1,5,3,6,100]

print merge_sort(test1)

print merge_sort(test2)

print merge_sort(test3)

print merge_sort(test4)

print merge_sort(test5)

print merge_sort(test6)

——————————————output at first attempt——————————————


[1, 2, 3, 4, 5, 6]
[1, 4, 3, 5, 7, 6]
[1, 2, 4, 3, 5, 6, 7]
[]
[4, 4, 4, 4, 4]
[1, 1, 2, 2, 3, 5, 6, 100]

Hmm so the code has some bug for test2 and test3 😦

what happend?

The code has a logic flaw (instead of a for there should be a while) posting the code without explaining the logical flaw as I think that is quite trivial

def merge_sort(arr):

l = len(arr)

if l <= 1:

return arr

elif l ==2:

if arr[0] < arr[1]:

return arr

else:

return [arr[1], arr[0]]

else:

half = l // 2

left = merge_sort(arr[:half])

right = merge_sort(arr[half:])

sorted_arr = []

while len(left) != 0 and len(right) != 0:

if left[0] <= right[0]:

v = left.pop(0)

else:

v = right.pop(0)

sorted_arr.append(v)

sorted_arr = sorted_arr + left + right

return sorted_arr

——— So all the test passed after this ——

Next step –>

Fix style

Style depends a lot on programmers taste but there are certain things that everyone (at least every python programmer) would appreciate. So I am going to just touch those points

def merge_sort_withstyle(arr):

"""

The program is a style corrected version written by Tanmay for

mergesort

"""

length = len(arr)

sorted_arr = arr if length

return arr if length <= 1

if length <= 1:

return arr

elif length == 2:

return arr if arr[0] < arr[1] else [arr[1], arr[0]]

else:

half = length//2

left = merge_sort_withstyle(arr[:half])

right = merge_sort_withstyle(arr[half:])

while len(left) != 0 and len(right) != 0:

value = left.pop(0) if left[0] < right[0] else right.pop(0)

sorted_arr.append(value)

sorted_arr += left + right

return sorted_arr

Next step (as a mathematician and a really good programmer)

Optimize 

(have fun !! )

c++ 11 features with practical examples (for each or range based loop)

I am going to use a famous example of factory design pattern which creates two stooges.

Stooge class implementation along with factory method is here

#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
class Stooge {
public:
	static Stooge *make_stooge(int);
	virtual void tell_a_joke()=0;
};

class Jerry : public Stooge{
public:
	void tell_a_joke(){
		std::cout << "I am jerry the stooge \n";
	}
};

class Moe : public Stooge{
public:
	void tell_a_joke(){
		std::cout << "I am Moe the stooge \n";
	}
};
Stooge *Stooge::make_stooge(int choice)
{
	if (choice == 1)
	{
		return new Jerry;
	}
	else
		return new Moe;
}

In summary a factory pattern takes out burden from “main” function (class consumer normally) to write all the “new” and stuff.

now the main

int main()
	std::vector<Stooge*> circus;
	int choice;
	cin >> choice;
	while (choice != 0)
	{
		cin >> choice;
		circus.push_back(Stooge::make_stooge(choice));
	}

	for each (Stooge* st in circus) st->tell_a_joke();
	cout << " \n Previous to that you have to use mem_fun... see implementation in source code\n";
	for_each(circus.begin(), circus.end(), mem_fun(&Stooge::tell_a_joke));
	cin >> choice;
}

So you can see how using for each looks somewhat comparable to other languages (like python)
The older way (“for_each”) has to provide the address of the static function which requires using “mem_fun” function which in my opinion is ok but error prone