정렬 알고리즘[버블정렬, 삽입정렬, 선택정렬, 퀵정렬, 병합정렬]

정렬 알고리즘: 이러한 알고리즘은 알파벳순 또는 숫자순과 같은 특정 순서로 데이터를 정렬하는 데 사용됩니다.

버블정렬, 삽입정렬, 선택정렬, 퀵정렬, 병합정렬 등이 대표적이다

 

버블 정렬: 정렬할 요소의 수가 적을 때 사용할 수 있는 간단한 정렬 알고리즘입니다.
정렬 알고리즘과 시간 복잡도의 개념을 학생들에게 소개하는 교육 도구로 자주 사용됩니다.
정렬할 요소가 거의 정렬되었거나 이미 정렬된 경우에도 버블 정렬을 사용할 수 있습니다.
이러한 경우 배열을 완전히 정렬하는 데 더 적은 스왑이 필요하기 때문에 버블 정렬이 다른 정렬 알고리즘보다 빠를 수 있습니다.
그러나 큰 배열의 경우 버블 정렬은 퀵 정렬이나 병합 정렬과 같은 다른 정렬 알고리즘에 비해 느리고 비효율적일 수 있습니다.
일반적으로 버블 정렬은 O(n^2) 시간 복잡성으로 인해 큰 데이터 집합을 정렬하는 데 일반적으로 사용되지 않습니다.
그러나 단순성과 구현 용이성이 효율성보다 더 중요한 특정 상황에서는 여전히 유용할 수 있습니다.

 

버블정렬 예제

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

이 구현에서는 먼저 입력 배열의 길이를 계산합니다 arr. 그런 다음 중첩 루프를 사용하여 배열을 반복합니다.

외부 루프는 에서 i=0까지 실행되고 i=n-1 내부 루프는 에서 j=0까지 실행됩니다 j=n-i-1.
내부 루프 내에서 인접한 요소를 비교 arr[j]하고 arr[j+1]. 가 arr[j]보다 크면 arr[j+1]Python의 튜플 압축 풀기 구문( )을 사용하여 교환합니다 arr[j], arr[j+1] = arr[j+1], arr[j].
정렬이 완료되면 정렬된 배열이 반환됩니다.

다음은 함수의 사용 예입니다 bubble_sort.

arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print(sorted_arr)

그러면 다음이 출력됩니다.

[11, 12, 22, 25, 34, 64, 90]

 

선택 정렬: 정수 목록을 오름차순으로 정렬하는 선택 정렬 알고리즘을 구현합니다.

def selection_sort(arr):
    n = len(arr)
    
    for i in range(n):
        min_idx = i
        
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
                
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

이 구현에서는 먼저 입력 배열의 길이를 계산합니다 arr. i=0

그런 다음 에서 까지 실행되는 루프를 사용하여 배열을 반복합니다 i=n-1.
루프 내에서 배열의 정렬되지 않은 부분에서 인덱스부터 시작하여 최소 요소의 인덱스를 찾습니다 i+1. j=i+1에서 까지 실행되는 다른 루프를 사용하여 배열을 반복하고 현재 최소값보다 작은 요소를 찾으면 j=n-1의 값을 업데이트하여 이 작업을 수행합니다. min_idx
최소 요소를 찾은 후 i배열의 정렬되지 않은 부분의 시작인 index 에 있는 요소로 교체합니다.
정렬이 완료되면 정렬된 배열이 반환됩니다.

다음은 함수의 사용 예입니다 selection_sort.

my_arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(my_arr)
print("Sorted array:", my_arr)

그러면 다음이 출력됩니다.

Sorted array: [11, 12, 22, 25, 34, 64, 90]

삽입 정렬: 삽입 정렬은 배열의 정렬되지 않은 부분의 요소를 배열의 정렬된 부분의 올바른 위치에 반복적으로 삽입하여 작동하는 또 다른 간단한 정렬 알고리즘입니다. 다음은 Python에서 삽입 정렬을 구현한 예입니다.

def insertion_sort(arr):
    n = len(arr)
    
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            
        arr[j+1] = key

이 구현에서 착용자. 그러면 i=1에서 i=n-1까지입니다.
thearr[i] inkey 내부. 또한 anotherj를 인덱스 i-1로 초기화합니다.
그런 다음 key를 arrayj의 정렬된 부분에 있는 요소와 비교합니다. 키가 arr[j]보다 작으면 `arrarr[j]를 오른쪽으로 한 위치 이동하고 j를 감소시킵니다. 키를 반복합니다.
올바른 위치를 찾으면 인덱스 `j+1j+1에 `key를 삽입합니다.
정렬이 완료되면 정렬된 배열이 반환됩니다. 다음은 theinsertion_sort 함수의 사용 예입니다.

my_arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(my_arr)
print("Sorted array:", my_arr)

그러면 다음이 출력됩니다.

 

Sorted array: [11, 12, 22, 25, 34, 64, 90]

 

병합 정렬: 병합 정렬은 배열을 두 개의 절반으로 나누고 각 절반을 재귀적으로 정렬한 다음 정렬된 절반을 다시 병합하여 작동하는 분할 정복 정렬 알고리즘입니다.
다음은 Python에서 병합 정렬을 구현한 예입니다.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

이 구현에서는 먼저 입력 배열 arr의 길이가 1보다 큰지 확인합니다.

그렇다면 배열의 중간점을 찾아 이를 두 개의 절반(left_half 및 right_half)으로 나눕니다.
그런 다음 각 절반이 정렬될 때까지 각 절반에 대해 재귀적으로 merge_sort를 호출합니다.
절반이 정렬된 후 왼쪽 및 오른쪽 절반의 요소를 비교하고 정렬된 배열 arr에 삽입하여 다시 병합합니다. 3개의 인덱스 i, j, k를 0으로 초기화하고 while 루프를 사용하여 양쪽 절반의 요소를 비교하고 arr에 삽입합니다.
마지막으로 절반에 나머지 요소가 있는지 확인하고 arr에 삽입합니다.
정렬이 완료되면 정렬된 배열이 반환됩니다. 다음은 merge_sort 함수의 사용 예입니다.

my_arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(my_arr)
print("Sorted array:", my_arr)

그러면 다음이 출력됩니다.

Sorted array: [11, 12, 22, 25, 34, 64, 90]

퀵정렬: Quicksort는 분할 정복 방식을 사용하는 또 다른 인기 있는 정렬 알고리즘입니다. 배열에서 "피벗" 요소를 선택하고 피벗보다 작은지 큰지에 따라 다른 요소를 두 개의 하위 배열로 분할하여 작동합니다. 그런 다음 하위 배열이 재귀적으로 정렬되고 결과가 연결됩니다.

다음은 Python에서 퀵 정렬을 구현한 예입니다.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = []
        greater = []
        for num in arr[1:]:
            if num < pivot:
                less.append(num)
            else:
                greater.append(num)
        return quicksort(less) + [pivot] + quicksort(greater)

이 구현에서는 먼저 입력 배열 arr의 길이가 1보다 작거나 같은지 확인합니다. 그렇다면 이미 정렬된 배열을 반환합니다.
그렇지 않으면 배열의 첫 번째 요소를 피벗으로 선택하고 점점 더 커지는 두 개의 빈 목록을 만듭니다. 그런 다음 배열의 나머지 요소를 반복하고 피벗보다 작은지 큰지에 따라 더 작거나 큰 요소에 추가합니다.
그런 다음보다 작은 것과 큰 것 모두에 대해 재귀적으로 빠른 정렬을 호출하고 정렬된 하위 배열을 피벗 요소와 연결하여 최종 정렬된 배열을 얻습니다.
다음은 퀵 정렬 기능의 사용 예입니다.

my_arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quicksort(my_arr)
print("Sorted array:", sorted_arr)

그러면 다음이 출력됩니다.

Sorted array: [11, 12, 22, 25, 34, 64, 90]

이러한 유형의 문제를 잘 수행하려면 이러한 알고리즘과 그 구현에 익숙해지는 것이 중요합니다.