[1028알고리즘 18]정렬

정렬

데이터를 순서대로 나열하는 방법을 의미합니다.

 

버블정렬

앞뒤 숫자 비교해서 정렬: 1st 와 2nd, 2nd와 3nd, 3nd와4th 와 비교

input = [10, 4,2]
def bubble_sort(input):
    n = len(input)
    for loop1 in range(n - 1):
        for loop2 in range(n - 1 - loop1):
            print(loop2, loop2 + 1, input)
            if input[loop2] > input[loop2 + 1]:
                input[loop2], input[loop2 + 1] = input[loop2 + 1], input[loop2]

    return input
print(bubble_sort(input))

선택정렬

선택해서 정렬. : 가장 작은 숫자를 맨앞자리 를 교체 해서 인덱스를 늘림.

input = [10, 4, 2]
def selection_sort(input):
    n = len(input)
    for loop1 in range(n - 1):
        min_index = loop1
        for loop2 in range(n-loop1):
            print(min_index + loop2, min_index , input)
            if input[min_index] > input[loop1 + loop2]:
                min_index = loop1 + loop2
        input[loop1], input[min_index] = input[min_index], input[loop1]
    return input
print(selection_sort(input)

삽입정렬

항상 정렬된상태를 유지, 첫번째 루프보다 작은 인덱스의 숫자들 비교.

이미 정렬된 숫자중 가장 큰수보다 크면 더이상진행안해도됨.

시간복잡도가. 최선의 경우 N만큼의 시간복잡도. .

input = [10, 4, 2,3,5,7,]
def insertion_sort(input):
    n = len(input)
    for loop1 in range(n - 1):
        for loop2 in range(loop1):
            #print(loop1, loop2)
            print(loop1-loop2-1 ,loop1-loop2)
            if input[loop1-loop2-1] <input[loop1-loop2]:
                input[loop1-loop2-1],input[loop1-loop2] =input[loop1-loop2],input[loop1-loop2-1]
            else:
                break
    return input
print(insertion_sort(input))

병합정렬

N/2^k = 1

k = log2N

log2N * O(N) → O(NlogN)

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]
array = [5, 3, 2, 1, 6, 8, 7, 4]

def merge_sort(array):

    if len(array)<=1:
        return array

    mid = len(array)//2
    left_array = merge_sort(array[:mid])
    right_array = merge_sort(array[mid:])

    print(left_array, right_array)
    return merge(left_array, right_array)

def merge(array1, array2):
    array_c =[]

    index_a = 0
    index_b = 0

    for i in range(len(array1)+len(array2)):
        #print(len(array1)+len(array2),i )
        #print(index_a,index_b)
        if len(array1) <= index_a:
            array_c.append(array2[index_b])
            index_b += 1
        elif len(array2) <= index_b:
            array_c.append(array1[index_a])
            index_a += 1
        elif array1[index_a] >= array2[index_b]:
            array_c.append(array2[index_b])
            index_b += 1
        else:
            array_c.append(array1[index_a])
            index_a += 1
    return array_c


print(merge(array_a,array_b))

print(merge_sort(array))

퀵정렬

gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

input = [10, 4, 2]
def quick_sort(input):
    data_length = len(input)
    if data_length <=1:
        return input
    pivot = input[data_length//2]
    min = []
    max = []
    for num in range(data_length):
        if input[num] < pivot:
            min.append(input[num])
        elif input[num] > pivot:
            max.append(input[num])
    return quick_sort(min)+[pivot]+ quick_sort(max)
print(quick_sort(input))