C의 버블정렬

정렬은 모든 프로그래밍 언어에서 배워야 하는 필수 개념입니다. 대부분 정렬은 숫자와 관련된 배열에서 수행되며 배열의 데이터를 탐색하고 액세스하는 기술을 익히는 디딤돌입니다.
오늘 글에서 다룰 정렬기법의 종류는 버블정렬(Bubble Sort)입니다.

버블정렬

버블 정렬은 인접한 요소의 순서가 잘못된 경우 반복적으로 교체하여 작동하는 간단한 정렬 알고리즘입니다. 이 배열 정렬 방법은 평균 및 최악의 시나리오에 대한 시간 복잡도가 매우 높기 때문에 대규모 데이터 세트에는 적합하지 않습니다.

버블정렬 알고리즘 :

1. 버블 정렬은 여러 단계를 거쳐 정렬하여 배열을 구성합니다.
2. 첫 번째 패스: 가장 큰 요소가 마지막 위치, 즉 올바른 위치로 이동합니다.
3. 두 번째 패스: 두 번째로 큰 요소가 마지막에서 두 번째 위치로 이동하며, 이는 후속 패스에서도 계속됩니다.
4. 각 패스마다 배열의 정렬되지 않은 부분만 처리됩니다.
5. k개를 통과한 후 가장 큰 k개 요소가 마지막 k개 슬롯의 올바른 위치에 있습니다.
6. 각 패스 동안:
   • 정렬되지 않은 섹션에서 인접한 요소를 비교하세요.
   • 큰 요소가 작은 요소보다 먼저 나타나면 요소를 교체하세요.
   • 패스가 끝나면 정렬되지 않은 가장 큰 요소가 올바른 위치로 이동합니다. 이 프로세스는 전체 배열이 정렬될 때까지 반복됩니다.

버블 정렬은 어떻게 작동하나요?

아래는 버블 정렬의 구현입니다. 내부 루프로 인해 스왑이 발생하지 않은 경우 알고리즘을 중지하여 최적화할 수 있습니다.

// Easy implementation of Bubble sort
#include <stdio.h>
int main(){
    int i, j, size, temp, count=0, a[100];
    //Asking the user for size of array
    printf("Enter the size of array you want to enter = \t");
    scanf("%d", &size);
    //taking the input array through loop
    for (i=0;i<size;i++){
        printf("Enter the %dth element",i);
        scanf("%d",&a[i]);
    }
    //printing the unsorted list
    printf("The list you entered is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    //sorting the list
    for (i = 0; i < size - 1; i++) {
        count = 1;
        for (j = 0; j < size - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                //swapping elements
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                count = 1;
            }
        }

        // If no two elements were swapped by inner loop,
        // then break
        if (count == 1)
            break;
    }
    // printing the sorted list
    printf("\nThe sorted list is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    return 0;

}

출력 :

**

버블 정렬의 복잡성 분석:

시간 복잡도: O(n2)
보조공간 : O(1)

버블 정렬의 장점:

• 버블 정렬은 이해하고 구현하기 쉽습니다.
• 추가 메모리 공간이 필요하지 않습니다.
• 안정적인 정렬 알고리즘입니다. 즉, 동일한 키 값을 가진 요소는 정렬된 출력에서 ​​상대적 순서를 유지합니다.

버블 정렬의 단점:

• 버블 정렬의 시간 복잡도는 O(n2)이므로 대규모 데이터 세트의 경우 속도가 매우 느립니다.
• 버블 정렬은 비교 기반 정렬 알고리즘입니다. 즉, 입력 데이터 세트에서 요소의 상대적 순서를 결정하려면 비교 연산자가 필요합니다. 특정 경우에는 알고리즘의 효율성이 제한될 수 있습니다.

문의사항은 댓글 달아주세요!!
그리고 모든 토론에 감사하겠습니다 :)

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