[알고리즘] 정렬 알고리즘 알기

[이코테] 나동빈 유튜브

www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

---

선택 정렬

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.

 

파이썬 코드

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

for i in range(len(array)):
    min_indxe = i
    for j in range(i+1, len(array)):
        if array[min_indxe] > array[j]:
            min_indxe = j
    array[i], array[min_indxe] = array[min_indxe], array[i]

print(array)

 

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 알고리즘

선택 정렬에 비해 난이도가 조금 높지만, 효율이 조금 더 좋다.

 

시간 복잡도

평균 O(N^2)

최고 O(N)

 

파이썬 코드

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

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j-1] > array[j]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

print(array)

 

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘이다.

 

시간 복잡도

평균 = O(NlogN)

최악 = O(N^2)

 

파이썬 코드

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


def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        # 엇갈렸을 때는 pivot과 작은 값을 바꿈
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        # 안 엇갈렸을 때는 작은 값과 큰 값을 바꿈
        else:
            array[left], array[right] = array[right], array[left]
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)


quick_sort(array, 0, len(array) - 1)
print(array)

 

계수 정렬

특정 조건에서 정말 빠르게 작동하는 알고리즘, 수의 범위가 제한되어 있을 때 사용 가능하다.

수의 각 자리수의 수가 몇 번 등장했는지 카운트를 해서, 반복적으로 순서대로 출력하면 된다.

 

파이썬 코드

array = [4, 3, 1, 7, 8, 9, 5, 2, 0, 9, 8, 7, 6]
sort_array = []
count = [0] * (max(array) + 1)

for i in array:
    count[i] += 1

for i in range(len(count)):
    for j in range(count[i]):
        sort_array.append(i)
    
print(sort_array)

 

정리