[알고리즘] 파이썬으로 sort하기 :: bubble sort(버블정렬), insert sort(삽입정렬), merge sort(병합정렬), heap sort(힙정렬)

파이썬으로 정렬하기

1. bubble sort in python

def bubble(v) :
    l = len(v)
    for i in range(l-1):
        for j in range(l-i-1) :
            if  v[j]>v[j+1] :
                v[j+1], v[j] = v[j], v[j+1]
    return v

2. insertion sort in python

# insertion sort
def insert(v) :
    for i in range(1,len(v)) :
        j=i-1
        while(j>=0 and v[i]<v[j]):
            j-=1
        v.insert((j + 1), v[i])
        del v[i+1]
    return v

3. merge sort in python

# merge sort
def merge(left, right) :
    v=list()
    i=0;j=0
    while(i<len(left) and j<len(right)) :
        if left[i]<=right[j] :
            v.append(left[i])
            i+=1
        else :
            v.append(right[j])
            j+=1
    if i==len(left) : v = v + right[j:len(right)]
    if j == len(right): v = v + left[i:len(left)]
    return v
 
def merge_sort(v) :
    if len(v) <= 1 : return v
    m = len(v)//2
    left = merge_sort(v[0:m])
    right = merge_sort(v[m:len(v)])
    return merge(left, right)

4. heap sort in python

# heap sort
class Heap:
    def __init__(self):
        self.li = [0]
 
    def insert(self, e):
        self.li = self.li+[e]
        idx = len(self.li)-1; p_idx = idx//2
        while(p_idx > 0 and self.li[idx]<self.li[p_idx]) :
            self.li[idx] , self.li[p_idx] = self.li[p_idx], self.li[idx]
            idx = idx//2; p_idx = idx//2
        return self.li
 
    def heapify(self, index, heap_size):
        left_idx = index * 2;
        right_idx = index * 2 + 1
        small_idx = index
        if (left_idx <= heap_size and self.li[small_idx] > self.li[left_idx]):
            small_idx = left_idx
        if (right_idx <= heap_size and self.li[small_idx] > self.li[right_idx]):
            small_idx = right_idx
        if small_idx != index:
            self.li[index], self.li[small_idx] = self.li[small_idx], self.li[index]
            return self.heapify(small_idx, heap_size)
 
    def remove(self):
        print(self.li[1]);del self.li[1]
        self.li.insert(1, self.li[len(self.li)-1]); del self.li[len(self.li)-1]
        return self.heapify(1, len(self.li)-1)
 

v = [5,4,3,2,1]

heap = Heap()

for i in v :

heap.insert(i)

for i in range(len(v)) :

heap.remove()