코딩테스트 연습/Python

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

슈퍼짱짱 2019. 11. 5. 08:00
반응형

파이썬으로 정렬하기


1. bubble sort in python


1
2
3
4
5
6
7
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
cs


2. insertion sort in python


1
2
3
4
5
6
7
8
9
# 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
cs


3. merge sort in python


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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)
cs


4. heap sort in python


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 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(1len(self.li)-1)
 
cs


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

heap = Heap()

for i in v :

heap.insert(i)


for i in range(len(v)) :

heap.remove()


반응형