My Blog List

Sunday, February 28, 2016

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)

Sunday, February 21, 2016

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)

Wednesday, February 17, 2016

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시간씩은 생각하고 코딩하고
이런식으로 작업을 했다.

어쨋든 풀고나니 희열도 있고, 자신감도 얻고, 얻는 효과가 많이 있는것 같다.
풀이 방법에 대해서 알고싶은분은 댓글달아주세요.