정렬 알고리즘 ( 버블 / 선택 / 삽입 / 퀵)

파이썬을 간단하게 짠 정렬들... 원리만 알면 구하기 쉬움.

def bubble(list):
    for i in range(len(list)):
        for j in range(len(list)):
            if list[i] < list[j]:
                list[i], list[j] = list[j], list[i]

    return list


def selection(list):
    for i in range(len(list)):
        min_temp = i
        for j in range(i, len(list)):
            if list[min_temp] > list[j]:
                min_temp = j
        list[i], list[min_temp] = list[min_temp], list[i]

    return list


def insertion(list):
    for i in range(len(list)):
        if i+1 < len(list):
            pin = i+1
            for j in reversed(range(0, pin)):
                if list[j] > list[pin]:
                    list[pin], list[j] = list[j], list[pin]
                    pin = j
                else:
                    break
    return list


def quicksort(list):
    if len(list) <= 1:
        return list

    pivot = list[len(list)//2]
    small = []
    many = []
    equal = []
    for x in list:
        if x < pivot:
            small.append(x)
        elif x > pivot:
            many.append(x)
        else:
            equal.append(x)

    return quicksort(small)+equal+quicksort(many)


def mergesort(list):
    if len(list) <= 1:
        return list

    helf = len(list)/2
    left = mergesort(list[:helf])
    right = mergesort(list[helf:])

    return_list = []
    left_x = 0
    right_x = 0
    while left_x < len(left) and right_x < len(right):
        if left[left_x] < right[right_x]:
            return_list.append(left[left_x])
            left_x += 1
        else:
            return_list.append(right[right_x])
            right_x += 1

    return_list += left[left_x:]
    return_list += right[right_x:]

    return return_list


temp_list = [33, 11, 99, 1, 22, 88, 55, 44, 66, 77]


print(bubble(temp_list))
print(selection(temp_list))
print(insertion(temp_list))
print(quicksort(temp_list))
print(mergesort(temp_list))

버블   O(n^2)

선택   O(n^2)

삽입  O(n^2) but 버블/선택 보단 빠르고 메모리를 적게 먹음

퀵     최적 O(nlogn)     최악 O(n^2)

머지  O(nlogn)