정렬 알고리즘 || 파이썬 || 데이터 구조 및 알고리즘

정렬 알고리즘

1. 버블정렬

여기서는 배열의 끝에 도달할 때까지 상위 요소를 이웃 요소와 교환합니다. 이제 가장 높은 요소가 마지막 위치에 있습니다. 그래서 경계를 변경하고 마지막에서 1씩 감소시킵니다. 최악의 경우 배열을 정렬하려면 n번 반복해야 합니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

알고리즘 -

1. 배열을 반복하여 최대 요소를 찾은 다음 마지막 요소로 바꿉니다.
2. 인접한 모든 요소를 ​​비교하고 큰 요소가 작은 요소보다 앞에 있는지 교환합니다. 배열의 끝에 도달할 때까지 이 작업을 계속하세요.
3. 플래그 유지: 요소가 교체되지 않으면 배열이 정렬되므로 루프를 중단할 수 있습니다.

시간복잡도 :

• 최상의 사례 - 배열이 이미 정렬된 경우 한 번의 반복만 필요합니다. 시간 복잡도 - O(n)
• 평균 사례 - 배열이 무작위로 정렬된 경우 시간 복잡도 - O(n2)
• 최악의 경우 - 배열이 내림차순인 경우 n*2 반복이 필요합니다.

공간 복잡도 - O(1), 추가 메모리가 필요하지 않습니다.

장점 -

1. 추가 메모리가 필요하지 않습니다.

2. 요소가 상대적인 순서를 유지하므로 안정적입니다.

단점 -

1. 시간 복잡도 - O(n2)로, 대규모 데이터 세트의 경우 매우 높습니다.

애플리케이션-

1. 데이터 세트가 매우 작고 시간 복잡도가 높아 단순성이 비효율성보다 중요한 경우에만 사용할 수 있습니다.

2. 선택 정렬

여기서는 배열에서 가장 작은 요소를 찾아 첫 번째 요소로 바꿉니다. 그런 다음 경계를 1만큼 늘리고 배열의 끝에 도달할 때까지 동일한 단계를 반복합니다.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

알고리즘 -

1. 배열을 반복하여 최소 요소를 찾습니다.

2. 첫 번째 요소와 바꾸고 포인터를 1씩 늘립니다.

3. 배열의 끝에 도달할 때까지 이 과정을 반복합니다.

시간 복잡도 :최상, 평균, 최악 세 가지 경우 모두 O(n2)의 시간 복잡도를 갖습니다.

최소 요소를 선택해야 하기 때문입니다. 배열이 이미 정렬되었는지 여부에 관계없이 매번 교체합니다.

공간 복잡도 -

O(1), 추가 메모리가 필요하지 않습니다.

장점 -

1. 추가 메모리가 필요하지 않습니다.

2. 버블 정렬보다 스왑 횟수가 적습니다.

단점 -

1. 시간 복잡도 - O(n2)로, 대규모 데이터 세트의 경우 매우 높습니다.<🎜>

2. 동등한 요소의 상대적 순서를 유지하지 않기 때문에 안정적이지 않습니다.

애플리케이션 -

1. 추가 저장공간이 필요하지 않아 메모리가 제한된 시스템에서도 사용할 수 있습니다.

2. 쓰기 작업이 느린 시스템과 같이 스왑 수를 최소화하는 것이 중요한 시스템에서 사용됩니다.

3. 삽입정렬

요소의 위치부터 배열의 시작 부분까지 역방향으로 반복적으로 확인하여 정렬되지 않은 요소를 올바른 위치에 삽입하는 방식으로 작동하는 알고리즘입니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

알고리즘 -

1. 배열의 두 번째 요소부터 시작하여 첫 번째 요소와 비교합니다. 현재 요소가 첫 번째 요소보다 작으면 교체하세요.

2. 이제 포인터를 늘리고 세 번째 요소에 대해 다음을 수행합니다. 두 번째 및 첫 번째 요소와 비교합니다.

3. 나머지 요소에 대해서도 동일한 과정을 반복하여 이전 요소와 비교한 후 적절한 위치에 삽입하세요.

시간복잡도 :

- 최선의 경우 - 배열이 이미 정렬된 경우 한 번의 반복만 필요합니다. 시간복잡도는 O(n)
- 평균 사례 - 배열이 무작위로 정렬된 경우 시간 복잡도는 O(n2)입니다.
- 최악의 경우 - 배열이 내림차순인 경우 n2번의 반복이 필요합니다.

공간 복잡도 - O(1), 추가 메모리가 필요하지 않습니다.

장점 -

1. 추가 메모리가 필요하지 않습니다.
2. 요소가 상대적 순서를 유지하므로 안정적입니다.

단점 -

1. 시간 복잡도 - O(n2)로 대규모 데이터 세트의 경우 매우 높습니다.

2. 동등한 요소의 상대적 순서를 유지하지 않기 때문에 안정적이지 않습니다.

애플리케이션-

1. 라이브 데이터 스트림과 같이 요소가 실시간으로 도착하여 정렬이 필요한 시나리오에 효율적입니다.

4. 병합 정렬

병합 정렬은 분할 정복 접근 방식을 따르는 알고리즘입니다. 두 가지 주요 단계로 구성됩니다. 첫째, 배열을 재귀적으로 분할하고, 둘째, 분할된 배열을 정렬된 순서로 병합합니다.

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

알고리즘 -

1. 중간점을 계산하여 배열을 두 부분으로 나눕니다.

2. 각 하위 배열의 길이가 1이 될 때까지 계속 나눕니다.

3. 왼쪽 절반과 오른쪽 절반 모두에서 병합 기능을 호출하세요.

4. 병합 프로세스에 세 가지 지침을 사용하세요.

• 왼쪽 절반 배열의 첫 번째 포인터입니다.
• 오른쪽 절반 배열의 두 번째 포인터입니다.
• 정렬된 배열의 세 번째 포인터입니다.

1. 두 부분을 반복하고 해당 요소를 비교합니다. 정렬된 배열에 더 작은 요소를 삽입하고 해당 포인터를 1씩 증가시킵니다.

2. 전체 배열이 정렬될 때까지 이 과정을 반복적으로 반복합니다.

시간 복잡도: 병합 정렬은 최고, 평균, 최악의 세 가지 경우 모두 O(n log n)의 시간 복잡도를 갖습니다. 배열이 이미 정렬되어 있는지 여부에 관계없이 각 분할과 병합에 대해 동일한 단계를 따르기 때문입니다.

O( log n ) - 분할 단계 중 각 단계에서 배열 크기가 절반으로 줄어듭니다.

O(n) - 병합 프로세스 중에 모든 요소를 ​​한 번 반복해야 합니다.

따라서 총 시간 복잡도는 O(n) * O(log n) = O(n log n)

입니다.

공간 복잡도 - O(n), 병합 과정에서 임시 배열을 저장하기 위해 추가 메모리가 필요합니다.

장점 -

1. 요소가 상대적 순서를 유지하므로 안정적입니다.

2. 대규모 데이터세트의 경우에도 시간 복잡도는 O(n log n)입니다.

3. 하위 배열이 독립적으로 병합되므로 병렬 처리에 적합합니다.

단점 -

1. 시간 복잡도 - O(n2)로, 대규모 데이터 세트의 경우 매우 높습니다.
2. 병합 과정에는 추가 메모리가 필요합니다.
3. 추가 메모리가 필요하므로 설치되지 않았습니다.
4. 대부분의 데이터세트에서 일반적으로 QuickSort보다 느립니다.

애플리케이션 -

1. 대용량 파일을 병합하는 등 데이터가 너무 커서 메모리에 맞지 않는 상황에서 사용됩니다.
2. 랜덤 액세스가 필요하지 않기 때문에 연결 목록을 정렬하는 데 사용됩니다.

5. 빠른 정렬

퀵 정렬은 분할 정복 방식을 따르는 알고리즘입니다. 피벗 요소를 선택하고 피벗을 올바른 정렬 위치에 배치한 후 피벗 요소 주위로 배열을 분할합니다.

첫 번째 단계는 피벗 요소를 선택한 다음 피벗 주위로 배열을 분할하는 것입니다. 피벗보다 작은 모든 요소는 왼쪽에 배치되고 피벗보다 큰 모든 요소는 오른쪽에 배치됩니다. 그러면 피벗이 올바른 정렬 위치에 있게 됩니다. 재귀적으로 배열을 두 부분으로 나누어 동일한 프로세스가 적용됩니다. 첫 번째 절반에는 피벗 이전의 요소가 포함되고 두 번째 절반에는 피벗 이후의 요소가 포함됩니다. 이 과정은 각 하위 배열의 길이가 1이 될 때까지 반복됩니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

알고리즘 -

1. 중간점을 계산하여 배열을 두 부분으로 나눕니다.
2. 피벗을 선택하세요. 모든 요소를 ​​피벗으로 선택할 수 있습니다.
3. 배열을 반복하고 각 요소를 피벗과 비교합니다.
4. 피벗보다 작은 요소는 모두 왼쪽에 배치하고 피벗보다 큰 요소는 모두 오른쪽에 배치합니다.
5. 피벗이 올바른 정렬 위치에 있도록 왼쪽 포인터로 피벗을 바꿉니다.
6. 파티션 길이가 1보다 커질 때까지 이 과정을 반복적으로 반복합니다.

시간복잡도 :

1. 최상의 사례 - 시간 복잡도 - O(n log n), 피벗이 배열을 두 개의 동일한 반으로 나누는 경우.
2. 평균 사례 - 시간 복잡도 - O(n log n), 피벗이 배열을 두 개의 동일한 반으로 나누는 경우. 하지만 반드시 같지는 않습니다.
3. 최악의 경우 - 시간 복잡도 - O(n2) , When -

• 이미 정렬된 배열에서 가장 작은 요소가 피벗으로 선택됩니다.

• 내림차순으로 정렬된 배열에서 가장 큰 요소가 피벗으로 선택됩니다.

O( log n ) - 분할 단계 중 각 단계에서 배열 크기가 절반으로 줄어듭니다.

O(n) - 요소를 정렬하는 동안

그러므로 총 시간 복잡도는 O(n) * O(log n) = O(n log n)

입니다.

공간 복잡도 :

1. 최고 및 평균 사례 - O(log n) - 재귀 스택의 경우

2. 최악의 경우 - O(n) - 재귀 스택의 경우

장점 -

1. 피벗을 잘못 선택하지 않는 한 대규모 데이터 세트에 효율적입니다.
2. 동일한 어레이에서 정렬 작업을 수행하고 데이터를 보조 어레이에 복사하지 않으므로 캐시 친화적입니다.
3. 안정성이 필요하지 않은 대용량 데이터를 위한 가장 빠른 범용 알고리즘 중 하나입니다.

단점 -

1. 시간 복잡도 - O(n2)로, 대규모 데이터 세트의 경우 매우 높습니다.
2. 동등한 요소의 상대적 순서를 유지하지 않으므로 안정적이지 않습니다.

애플리케이션 -

1. 프로그래밍 라이브러리와 프레임워크에 사용됩니다. 예를 들어 Python의 sorted() 함수와 Java의 Array.sort()는 빠른 정렬을 기반으로 합니다.
2. 쿼리 실행 시 효율적으로 행을 정렬하여 indDatabase 쿼리 최적화에 사용됩니다.
3. 캐시 친화적인 속성으로 인해 대규모 데이터세트의 메모리 내 정렬에 적합합니다.

6.힙 정렬

힙 정렬은 비교 기반 정렬 알고리즘입니다. 선택 정렬의 확장입니다. 힙 정렬에서는 이진 힙을 생성하고 최대 또는 최소 요소를 마지막 요소와 교환합니다. 그런 다음 힙 크기를 1만큼 줄입니다. 이 프로세스는 힙 길이가 1보다 커질 때까지 반복됩니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

알고리즘 -

1. heapify 프로세스를 사용하여 최대 힙을 구축합니다. Heapify는 바이너리 힙 데이터 구조의 힙 속성을 유지하는 데 사용되는 방법입니다.
2. 배열의 크기가 n이면 n//2개의 상위 노드가 포함됩니다.
3. 색인 i에 있는 부모의 경우:

a.왼쪽 하위 항목은 인덱스 2i 1에 있습니다

ㄴ. 오른쪽 자식은 인덱스 2i 2에 있습니다

1. 인덱스 n//2에서 0까지 부모가 있는 모든 하위 트리를 반복하고 그에 대해 heapify 함수를 호출합니다.
2. 이제 배열은 인덱스 0에 가장 큰 요소가 있는 최대 힙이 됩니다.
3. 첫 번째 요소를 힙의 마지막 요소와 바꾸고 힙 크기를 1씩 줄입니다.
4. 힙 길이가 1보다 커질 때까지 이 과정을 반복하세요

시간 복잡도: 힙 정렬은 최고, 평균, 최악의 세 가지 경우 모두 O(n log n)의 시간 복잡도를 갖습니다. 이는 배열이 이미 정렬되었는지 여부에 관계없이 최대 힙이 생성되고 요소가 교체될 때마다 동일한 단계를 따르기 때문입니다.

O( log n ) - 최대 힙을 생성하려면

O(n) - 최대 힙이 생성되고 요소가 n번 교체됩니다.

그러므로 총 시간 복잡도는 O(n) * O(log n) = O(n log n)

공간 복잡도 : 모든 경우 - O(log n) - 재귀 스택의 경우

장점 -

1. 대규모 데이터세트의 경우에도 시간 복잡도는 O(n log n)입니다.
2. 메모리 사용량은 거의 일정합니다.

단점 -

1. 동등한 요소의 상대적 순서를 유지하지 않으므로 안정적이지 않습니다.
2. 병합 정렬에 비해 스왑이 많이 필요합니다.

애플리케이션 -

1. 최대 또는 최소 요소 추출이 빈번한 우선순위 큐를 구현하는 데 유용합니다.
2. 내부 정렬이 필요하고 메모리 사용량이 중요한 시스템에 유용합니다.
3. 순위가 필요한 시나리오에서 사용됩니다.

7.카운팅 정렬과 기수 정렬

카운팅 정렬은 비비교 기반 정렬 알고리즘입니다. 정렬할 요소의 개수에 비해 입력값의 범위가 작은 경우 특히 효율적입니다. 카운팅 정렬의 기본 아이디어는 입력 배열에서 각 고유 요소의 빈도를 계산하고 해당 정보를 사용하여 요소를 올바른 정렬 위치에 배치하는 것입니다.

Radix Sort는 Counting Sort를 서브루틴으로 사용합니다. 숫자의 각 자릿수에 Counting Sort를 적용하여 배열에서 가장 큰 숫자의 모든 자릿수를 처리할 때까지 반복적으로 정렬합니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False

        # Last i elements are already in place, so we don't need to check them
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Swap the elements
                swapped = True
        if not swapped:
            break

    return arr

def selectionSort(a):
    i = 0
    while i<len(a):

        smallest = min(a[i:])
        index_of_smallest = a.index(smallest)
        a[i],a[index_of_smallest] = a[index_of_smallest],a[i]

        i=i+1
    return a

알고리즘 -

1. 배열에서 최대 숫자를 찾고 그 안에 있는 자릿수(d)를 결정합니다. 숫자의 길이가 d이면 배열에서 Counting Sort가 d번 호출됩니다.

2. 통화 계산 배열의 각 자리에 대해 일의 자리부터 시작하여 열의 자리 등으로 정렬합니다.

3. 계산 정렬:

• 먼저 인덱스 배열을 생성하고 해당 값을 기준으로 요소를 매핑합니다. 예를 들어 숫자가 4인 경우 인덱스 배열의 4번째 인덱스에서 값을 증가시킵니다.
• 인덱스 배열에서 접두사 합계 배열을 만듭니다.
• 접두사 합계 배열을 사용하여 입력 배열의 길이와 동일한 새로운 정렬 배열을 만듭니다
• 예를 들어 접두사 합계 배열의 인덱스 1에 값 2가 있는 경우 정렬된 배열의 위치 2에 값 1을 배치하고 접두사 합계 배열의 값을 1만큼 감소시킵니다.

시간복잡도 :

Counting Sort의 시간 복잡도는 O(n k)입니다. 여기서 n은 정렬할 요소의 수이고 k는 값의 범위(인덱스 배열의 크기)입니다. 이 복잡도는 다음에 유효합니다. 세 가지 경우 모두 최고, 평균, 최악입니다.

이미 배열이 정렬되었는지 여부에 관계없이 매번 동일한 단계를 따르기 때문입니다.

Radix Sort의 시간 복잡도는 d배만큼 증가합니다. 여기서 d는 배열에서 가장 큰 숫자의 자릿수입니다. 시간 복잡도는 O(d * (n k))

그러므로 총 시간 복잡도는 O(d) * O(n k) = O(d * (n k))

공간 복잡도: 모든 경우 - O(n k), 여기서 n은 입력 배열의 길이이고 k는 인덱스 배열의 값 범위입니다.

장점 -

1. 요소가 상대적인 순서를 유지하므로 안정적입니다.
2. 카운팅 정렬은 일반적으로 입력 범위가 입력 개수 순서인 경우 병합 정렬, 퀵 정렬과 같은 모든 비교 기반 정렬 알고리즘보다 더 빠르게 수행됩니다.

단점 -

1. 소수점 값에서는 계산 정렬이 작동하지 않습니다.
2. 정렬할 값의 범위가 너무 크면 계산 정렬이 비효율적입니다.
3. 추가 공간 O(O(n m))을 사용하므로 제자리 정렬 알고리즘이 아닙니다.

애플리케이션 -

1. 문자열의 문자 수 계산과 같은 응용 프로그램에 사용됩니다.
2. ID, 전화번호 등 값의 범위가 넓은 정수를 정렬하는 데 유용합니다.
3. 날짜나 튜플과 같은 여러 키가 있는 데이터를 정렬하는 데 효율적입니다.

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