Random Sort

Below I will give my implementation of random sort that you may find interesting :D

import random

def is_sorted(l):
    length = len(l)
    for i in range(length):
        if i == length-1:
            return True
        elif (l[i] < l[i+1] or l[i] == l[i+1]):
            continue
        else:
            return False
   
def rand(l):
    length = len(l)
    if is_sorted(l):
        return l
    else:
        dic = {key:True for key in l}
        count = 0
        l2 = []
        while True:
            if count == length:
                break
            else:
                ran = random.randint(0,length-1)
                if dic[l[ran]]:
                    l2.append(l[ran-1])
                    count += 1
                    dic[l[ran]] = False            
        return rand(l2)

It is kind of exciting when you think that the best case runtime of this algorithm is better than any other, while the worst case is probably the worst.
         
     

Closest Pair of Points

The aim of this algorithm will be finding two points with the smallest distance between them. Notice that we will be considering that the points are on a 2D plane. The algorithm I have developed is a divide and conquer algorithm.

0. Append the vectors to a list
1. Sort the list by the x-axis (presumably with mergesort) )  O(nlogn) only once

1. Divide the list into two from the midpoint according to the x-axis values
2. Recursively divide the list into halves logn times
3. In each division into half, check the relationship between 3 closest pairs in each side

The distance between two points is checked with the use Pythagorean theorem.
The runtime of this algorithm turns out to be O(nlogn) if we use the Master Theorem that was introduced in the previous blog entry.

The obvious bruteforce method takes O(n^2).

Now I will compare the runtime of my algorithm with the bruteforce approach below:
10000 pairs
Bruteforce: 0:00:08.874909
Divide and Conquer: 0:00:00.581441
50000 pairs
Bruteforce: 0:00:09.365906
Divide and Conquer: 0:00:04.014672

You might notice the leap in the runtime of the divide and conquer algorithm. That is caused mostly by the runtime of the mergesort that sorts our list before our actual pair finding algorithm starts working.