Python의 정렬 알고리즘

정렬이란 무엇입니까?

정렬이란 데이터 항목 간의 선형 관계를 기반으로 특정 순서(일반적으로 오름차순 또는 내림차순)로 데이터를 정렬하는 프로세스를 의미합니다.

정렬이 필요한 이유는 무엇입니까?

정렬을 통해 효율적인 데이터 검색이 가능하고 데이터 분석이 단순화되며 전반적인 데이터 관리가 향상되므로 구조화된 데이터로 작업할 때 정렬이 매우 중요합니다.

정렬 알고리즘

이 게시물에서는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 빠른 정렬 등의 정렬 알고리즘을 다룹니다.

버블정렬

버블 정렬은 배열을 반복적으로 진행하면서 인접한 요소를 비교하고 순서가 잘못된 경우 교체합니다. 이 프로세스는 배열이 정렬될 때까지 계속되며 더 큰 요소는 끝까지 "버블링"됩니다.

연산

1단계: 시작
2단계: i = 0
3단계: i < length(array) - 1, 4단계로 이동합니다. 그렇지 않으면 10단계로 이동
4단계: j = 0
5단계: j < length(array) - i - 1, 6단계로 이동합니다. 그렇지 않으면 3단계로 이동
6단계: array[j] > array[j + 1], 7단계로 이동; 그렇지 않으면 8단계로 이동
7단계: array[j]와 array[j + 1] 바꾸기
8단계: j를 증가시킵니다. 5단계로 이동
9단계: i를 증가시킵니다. 3단계로 이동
10단계: 종료

암호

def bubble_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

시간 복잡도

최상의 사례 : O(n)
평균 사례 : O(n^2)
최악의 경우 : O(n^2)

선택 정렬

선택 정렬은 배열의 정렬되지 않은 부분에서 가장 작은 값을 찾아 해당 부분의 시작 부분에 배치합니다.

연산

1단계 : 시작
2단계 : i = 0
3단계: i < length(array) - 1, 4단계로 이동합니다. 그렇지 않으면 10단계로 이동
4단계: 최소값 = i; j = i + 1
5단계: j < 길이(배열), 6단계로 이동; 그렇지 않으면 9단계로 이동
6단계: 배열[최소_값] > array[j], 7단계로 이동; 그렇지 않으면 8단계로 이동
7단계: 최소값 = j
8단계: j를 증가시킵니다. 5단계로 이동
9단계: 배열[최소_값]과 배열[i]
교체 10단계: i를 증가시킨다. 3단계로 이동
11단계 : 종료

암호

def selection_sort(arr):
    print("Array Before Sorting: ", end='')
    print(arr)
    for i in range(len(arr) - 1):
        min_val = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_val]:
                min_val = j

        arr[i], arr[min_val] = arr[min_val], arr[i]

    print("Array After Sorting: ", end='')
    print(arr)

# Main
selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])

시간 복잡도

최상의 경우 : O(n^2)
평균 사례 : O(n^2)
최악의 경우 : O(n^2)

삽입 정렬

삽입 정렬은 정렬되지 않은 부분에서 각 요소를 가져와서 정렬된 부분의 올바른 위치에 삽입하여 한 번에 한 요소씩 정렬된 배열을 만듭니다.

연산

1단계: 시작
2단계: i = 1
3단계: i < len(arr), 4단계로 이동; 그렇지 않으면 12단계로 이동
4단계: 키 = arr[i]
5단계: j = i - 1
단계 6: j >= 0이고 arr[j] > 키를 누르고 7단계로 이동합니다. 그렇지 않으면 10단계로 이동
7단계: arr[j + 1] = arr[j]
8단계: j를 1씩 감소
9단계: 6단계로 이동
10단계: arr[j + 1] = 키
11단계: i를 1씩 증가시킵니다. 3단계로 이동
12단계: 종료

암호

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)

시간 복잡도

최상의 사례 : O(n)
평균 사례 : O(n^2)
최악의 경우 : O(n^2)

병합 정렬

병합 정렬은 배열을 더 작은 하위 배열로 재귀적으로 나누고 정렬한 다음 다시 병합하는 분할 정복 알고리즘입니다.

연산

병합 정렬 알고리즘

1단계: 시작
2단계: length(array) 3단계: mid_point = length(array) // 2
4단계: left_half = 배열[:mid_point]
5단계: right_half = 배열[mid_point:]
6단계: sorted_left = merge_sort(left_half)
7단계: sorted_right = merge_sort(right_half)
8단계: 병합 반환(sorted_left, sorted_right)
9단계: 종료

병합 기능

1단계: 시작
2단계: sorted_merge = []
3단계: l = 0, r = 0
4단계: l < len(왼쪽) 및 r < len(오른쪽), 5단계로 이동; 그렇지 않으면 9단계로 이동
5단계: left[l] <= right[r]인 경우 6단계로 이동합니다. 그렇지 않으면 7단계로 이동
6단계: sorted_merge에 left[l]를 추가합니다. l을 1씩 증가
7단계: sorted_merge에 right[r]를 추가합니다. r을 1씩 증가
8단계: 4단계로 이동
9단계: l < len(왼쪽), 10단계로 이동; 그렇지 않으면 12단계로 이동
10단계: sorted_merge에 left[l]을 추가합니다. l을 1씩 증가
11단계: 9단계로 이동
단계 12: r < len(오른쪽), 13단계로 이동; 그렇지 않으면 15단계로 이동
13단계: sorted_merge에 right[r]를 추가합니다. r을 1씩 증가
14단계: 12단계로 이동
15단계: sorted_merge 반환
16단계: 종료

암호

def merge(left, right):
    sorted_merge = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            sorted_merge.append(left[l])
            l += 1
        else:
            sorted_merge.append(right[r])
            r += 1

    while l < len(left):
        sorted_merge.append(left[l])
        l += 1

    while r < len(right):
        sorted_merge.append(right[r])
        r += 1

    return sorted_merge

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid_point = len(arr) // 2
    left_half = arr[:mid_point]
    right_half = arr[mid_point:]

    sorted_left = merge_sort(left_half)
    sorted_right = merge_sort(right_half)

    return merge(sorted_left, sorted_right)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
arr = merge_sort(arr)
print("Array After Sorting:", arr)

시간 복잡도

최상의 경우 : O(n log n)
평균 사례 : O(n log n)
최악의 경우 : O(n log n)

Quick Sort

Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.

Algorithm

Quick Sort

Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End

Partition Function

Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End

Code

def partition(arr, low, high):
    pivot = arr[high]
    left = low
    right = high - 1
    while left <= right:
        if arr[left] > pivot and arr[right] < pivot:
            arr[left], arr[right] = arr[right], arr[left]
        if arr[left] <= pivot:
            left += 1
        if arr[right] >= pivot:
            right -= 1
    arr[left], arr[high] = arr[high], arr[left]
    return left

def quicksort(arr, low, high):
    if low < high:
        pivot_index = partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
quicksort(arr, 0, len(arr) - 1)
print("Array After Sorting:", arr)

Time Complexity

Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

위 내용은 Python의 정렬 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!