Combsort in python

this is combsort in python 

if you want to see detail of combsort 

refer this sites

https://en.wikipedia.org/wiki/Comb_sort

http://www.geeksforgeeks.org/comb-sort/

below is my python code

arr = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]

def combsort(arr):

    gap = len(arr)
    swapped = True
    while gap !=1 or swapped:
        gap= int(gap//1.3)
        if gap==0:
            gap =1
        swapped = False        for i in range(0, len(arr)-gap):
            if arr[i] > arr[i+gap]:
                swap(arr, i , i+gap)
                swapped = True                print(arr)

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

combsort(arr)

print(arr)

shell sort in python

arr = [12, 34, 54, 2, 3]

def shellsort(arr):
    n = len(arr)
    gap = int(n/2)


    while gap > 0 :
        for i in range(gap, n):

            temp = arr[i]

            j = i
            while j>=gap and arr[j-gap] >temp:
                arr[j] = arr[j-gap]
                j-= gap

            arr[j] = temp
        gap//=2
shellsort(arr)
print(arr)

Problem 321

You can get hint from this image

M(n) = k(k+1)/2

this is triangle numbers k(k+1)/2
and you will finally get X^2 - 8Y^ - 7 = 0

Bucket Sort in python

I make buckets as many as size of arr

and put data.

arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]
def bucketSort(arr, size):
    buckets = [[] for i in range(size)]

    # put arr in bucket        

    for i in range(len(arr)):
        num = size*arr[i]
        buckets[int(num)].append(arr[i])

    output = []
    # use insertion sort        

    for i in range(len(buckets)):
        insertionSort(buckets[i])

    # concat all data        

    for i in range(len(buckets)):
        while len(buckets[i]) > 0:
            output.append(buckets[i].pop(0))

    return output


def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def insertionSort(arr):
    for i in range(1, len(arr)):
        index= i
        print("index : " + str(i))
        while index!=0:
            if arr[index] < arr[index-1]:
                temp = arr[index]
                arr[index]= arr[index-1]
                arr[index-1] = temp
                index = index-1                print(arr)
            else :
                break
print(bucketSort(arr, len(arr)))

Count sort in Python

this is my python code for count sort

you can run

arr = [1, 4, 1, 2, 9, 5, 2]


def countSort(arr):
    #find max range    

    mval =0;
    for i in range(len(arr)):
        mval = max(mval, arr[i])

    # 배열 초기화    

    temp = [0]*(mval+1)
    output = [0]*(len(arr))

    # counting    

    for i in range(len(arr)):
        temp[arr[i]] =temp[arr[i]] + 1
    print(temp)
    

    # recounting    

    for i in range(1, len(temp)):
        temp[i]= temp[i-1] + temp[i]



    # counting sort    

    for i in range(len(arr)):
        output[temp[arr[i]] -1] =  arr[i]
        temp[arr[i]] = temp[arr[i]] -1
    print(temp)
    print(output)

countSort(arr)

Problem 346 in project euler

This problem was easy to me that make my brain to take a rest.

the steps to solve
1. I had to find range of base that number can cover 10^2
  It was sqrt of 10^2 include itself.
2. generater all possible base numbers
 ex) in 2 base
    11, 111, 1111 ...
    3    7     15
3. exclude 2 digit number.
4. put set to real number
5. sum of set

this is my solution.

Insertion Sort in Python.

Insertion sort is somehow difficult when I wrote code from only logic images

this is not optimized Insertion sort 

I will optimize and update sort code

arr = [5,2,3,7,1,4]

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

def insertionSort(arr):
    for i in range(1, len(arr)):
        index= i
        print("index : " + str(i))
        while index!=0:
            if arr[index] < arr[index-1]:
                temp = arr[index]
                arr[index]= arr[index-1]
                arr[index-1] = temp
                index = index-1                print(arr)
            else :
                break
insertionSort(arr)
print(arr)