#3 Python / O(n^2)정렬 알고리즘(선택, 버블, 삽입, 셸)

🧐 O(n^2)의 시간복잡도를 가지는 정렬들

O(n^2)의 시간복잡도를 가지는 비교적 간단한 정렬에는 선택, 버블, 삽입, 셸 정렬 등이 있다.

👉 선택 정렬

(오름차순 정렬 시)
주어진 배열에서 가장 작은 수를 찾아 첫 번째 수와 교환하고,
두 번째 작은 수를 찾아 두 번째 수와 교환하고, ...

def select_sort(arr):

    for j in range(len(arr)):

        index=j

        for i in range(1+j,len(arr)):
            if arr[i]<arr[index]:
                index=i

        arr[j],arr[index]=arr[index],arr[j] 

⁙ 제자리 정렬(사용되는 추가 저장공간이 적다), 불안정 정렬(같은 값일 때 순서가 변할 수 있다)

👉 거품 정렬(Bubble Sort)

(오름차순 정렬 시)
인접한 원소끼리 비교하는 정렬. 한 번의 루프를 돌 때마다 가장 큰 값이 맨 뒤로 이동한다.

def bubble_sort(arr):

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

        for j in range(0,len(arr)-i):
        
            if arr[j]>arr[j+1]:
                arr[j], arr[j+1]=arr[j+1], arr[j]

⁙ 제자리 정렬(사용되는 추가 저장공간이 적다), 안정 정렬(같은 값이면 순서가 변하지 않음)

👉 삽입 정렬

배열 중에서 자신이 삽입될 위치를 찾아 그 곳에 삽입시키며 정렬

def insert_sort(arr):

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

        memory=a[i]
        j=i-1

        while j>=0 and memory<a[j]:

            arr[j+1]=arr[j]
            j-=1

        arr[j+1]=memory

⁙ 제자리 정렬(사용되는 추가 저장공간이 적다), 안정 정렬(같은 값이면 순서가 변하지 않음), 매 루프마다 배열을 한 칸 씩 이동해야 하므로 배열의 크기가 큰 경우 비효율적

👉 셸 정렬

삽입 정렬을 보완한 정렬.

삽입 정렬은 정렬해야 할 수가 멀리 떨어져있을 때에도 한 칸씩만 배열을 옮기며 비효율적으로 수행됨.

그렇기에 특정 거리만큼의 수들을 삽입 정렬하고 그 특정 거리를 줄여 다시 삽입 정렬하는 것을 반복.

결과적으로 거리가 1일 때 삽입 정렬을 하는 것으로 정렬이 마무리 되고 최악의 경우를 제외하면 삽입 정렬보다 속도가 빠름.

소스 코드는 생략!

⁙ 제자리 정렬(사용되는 추가 저장공간이 적다), 불안정 정렬(같은 값일 때 순서가 변할 수 있다)