2.정렬 알고리즘(Sorting Algorithm)

※일반정렬

1.버블정렬O(n²)

버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

def BubbleSort(arr): #버블정렬 알고리즘

    for i in range(len(arr)):

        for j in range(1,len(arr)-i,1):

            if arr[j] < arr[j-1]:

                arr[j],arr[j-1] = arr[j-1],arr[j]

    return arr

2.선택정렬O(n²)

선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.

def SelectionSort(arr): #선택정렬 알고리즘

    

    for i in range(len(arr)-1):

        key = i

        for j in range(i,len(arr),1):

            if arr[j] < arr[key]:

                key = j

        arr[i],arr[key] = arr[key],arr[i]

    return arr

3.삽입정렬O(n²)

삽입 정렬(insertion sort)은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다.

def InsertionSort(arr): #삽입정렬 알고리즘

    for i in range(1,len(arr),1):

        for j in range(0,i,1):

            if arr[i] < arr[j]:

                for swap in range(i,j,-1):

                    arr[swap],arr[swap-1] = arr[swap-1],arr[swap]

    return arr

※빠른정렬

1.병합정렬 O(nlogn)/O(nlogn) - 제자리정렬 x

병합 정렬(merge sort)은 하나의 리스트를 정렬하기 위해서 해당 리스트를 n개의 서브리스트로 분할하여 각각을 정렬한 수, 정렬된 n개의 서브리스트로 합병시켜서 정렬하는 방식이다.

def MergeSort(arr): #병합정렬 알고리즘

    if len(arr) > 1: #배열이 하나이상일때

        mid = int(len(arr)/2)

        left = arr[:mid]

        right = arr[mid:]

        l = MergeSort(left)

        r = MergeSort(right)

        return Merge(l,r)

    else: #배열이 하나면 배열 리턴

        return arr

def Merge(left,right):

    i = 0

    j = 0

    arr = []

    while (i<len(left)) & (j<len(right)): #비교하면서 한쪽이 끝날때까지 데이터담기

        if left[i] < right[j]:

            arr.append(left[i])

            i += 1

        else:

            arr.append(right[j])

            j += 1

    while (i<len(left)): #남은 데이터 담기

        arr.append(left[i])

        i+=1

    

    while (j<len(right)): #남은 데이터 담기

        arr.append(right[j])

        j+=1

    return arr

2.퀵정렬 O(nlogn)/O(n²) - 제자리정렬 o

퀵 정렬(quick sort)은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.

3.힙정렬 O(nlogn)/O(nlogn) - 제자리정렬 o

힙 정렬(heap sort)은 힙 트리 구조(Heap Tree Structure)를 이용하는 정렬 방법입니다. 

참조https://medium.com/@fiv3star/%EC%A0%95%EB%A0%AC%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-sorting-algorithm-%EC%A0%95%EB%A6%AC-8ca307269dc7