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)

bubble Sort in Python

this is second weeks in algorithm study,

I want learn python and study basic algorithm.

this time I studied Bubble sort.

this time complexity is always O(N^2).

next time I will rewrite optimized Bubble sort  

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

def swap(arr, a, b):
    temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;

def bubblesort(arr):
    for i in range(len(arr)) :
        print( str(i+1) + " 번재 passing");
        for j in range(len(arr)-1):
            if arr[j] > arr[j+1] :
                swap(arr, j, j+1);
                print(arr)


bubblesort( arr);
print("result : ")
print(arr)

This is a selection sort algorithm

This time I attended algorithm study group using geeksforgeeks hompage.
this is just start and review algorithm basic.
I hope to study this steadily .

If you have question about selection sort. reply~!
time complexity O(n2)

arr = [5,2,3,7,1,4]
def selectionSort(arr):
    for i in range(len(arr)-1):
        print(i)
        minimum = arr[i]
        for j in range(i+1, len(arr)):
            if arr[j] < minimum:
                minimum = arr[j]
                swap(arr, i, j)
                print(arr);

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

def selectionSortOnlyOneSwap(arr):
    for i in range(len(arr)-1):
        print(i)

        minimum = arr[i]
        minposition = i
        for j in range(i+1, len(arr)):
            if arr[j] < minimum:
                minimum = arr[j]
                minposition = j

        if minposition != i:
            swap(arr, i, minposition)

        print(arr)

selectionSort(arr)
print(arr)
print("only one time swap")

arr = [5,3,2,7,1,4]
print(arr)
selectionSortOnlyOneSwap(arr)

Problem 539 Odd Elimination~!

1■1

2■■2

3■■2

4■■2

5■■2

6■■■■4

7■■■■4

8■■■■■■6

9■■■■■■6

10■■■■■■■■8

11■■■■■■■■8

12■■■■■■6

13■■■■■■6

14■■■■■■■■8

15■■■■■■■■8

16■■■■■■6

17■■■■■■6

18■■■■■■■■8

19■■■■■■■■8

20■■■■■■6

21■■■■■■6

22■■■■■■■■8

23■■■■■■■■8

24■■■■■■■■■■■■■■14

25■■■■■■■■■■■■■■14

26■■■■■■■■■■■■■■■■16

27■■■■■■■■■■■■■■■■16

28■■■■■■■■■■■■■■14

나는 나만의 계산 방법으로 풀었는데.. 

실제 답을 보니깐 수학 전개식을 이용해서 작성한 사람들이 있었다.

대단한것 같다. 

이번에 이 문제를 풀기위해서 15일을 투자를 했다.

머 하루종일 손을 잡은것은 아니데.. 하루에 1-2시간씩은 생각하고 코딩하고

이런식으로 작업을 했다.

어쨋든 풀고나니 희열도 있고, 자신감도 얻고, 얻는 효과가 많이 있는것 같다.

풀이 방법에 대해서 알고싶은분은 댓글달아주세요.