[알고리즘 종류] 정렬 알고리즘

1) 버블 정렬

• 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
• 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
• 시간 복잡도 : O(n²)

def bubble_sort(a): # 정렬할 List
    for i in range(len(a)-1, 0, -1):
        for j in range(0, i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]

 

2) 카운팅 정렬

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형시간에 정렬
• 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
• 시간 복잡도 : O(n + k) : n은 리스트 길이, k는 정수의 최대값

def counting_sort(A, B, k):
    #A : 입력 배열(1 to k), B : 정렬된 배열, C : 카운트 배열

    C = [0 for _ in range(K)]

    for i in range(0, len(B)):
        C[A[i]] += 1

    for i in range(1, len(C)):
        C[i] += C[i-1]

    for i in range(len(B)-1, -1, -1):
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1

 

3) 선택 정렬

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
• 리스트의 최솟값을 찾고 그 값을 리스트의 맨 앞에 위치한 값과 교환하는 과정 반복
• 시간 복잡도 : O(n²)

def selcetion_sort(a):
    for i in range(0, len(a)-1):
        min = i
        for j in range(i+1,len(a)): # 이미 정렬된 값은 빼주기 위해 시작값이 i+1
            if a[min] > a[j]:
                min = j
            a[i], a[min] = a[min], a[i]

 

4) 퀵정렬

• 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
• 시간복잡도: O(nlogn) (최악의 경우 O(n²))

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

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)

 

5) 팀정렬

• Insertion sort와 Merge sort를 결합하여 만든 정렬
• 시간복잡도: O(nlogn) (최선의 경우 O(n))
• sorted()와 list.sort()에 사용된 정렬 알고리즘
• 현업에서 가장 많이 사용되는 정렬법

코드는 다음에,,,