버블 정렬

버블 정렬은 인접한 요소의 연속 쌍이 정렬되지 않은 경우 반복적으로 교환하여 배열을 정렬하는 가장 간단한 정렬 알고리즘입니다.

버블 정렬 알고리즘은 다음과 같습니다.

Bubble Sort (A,N)
1.Repeat Step 2 for I=0 to N-1
2.  Repeat for J=0 to N-I
3.    If A[J] > A[J+1]
4.    SWAP A[J] and A[J+1]
5.  [END OF INNER LOOP]
6.[END OF OUTER LOOP]

버블 정렬이 주어진 배열을 정렬하는 방법을 그림으로 표현해 봅시다.



따라서 첫 번째 반복이 끝나면 가장 큰 요소가 올바른 위치를 차지하고 두 번째 반복 후에 두 번째로 큰 요소가 정렬된 위치를 차지하고 계속됩니다.

코드를 작성할 시간입니다.

   void bubbleSort(int arr[],int n)
    {
     int i, j,temp;

        for(i = 0; i < n-1; i++)
        {
            for (j = 0; j < n-i-1; j++)
            {
                if (arr[j] > arr[j+1])
                 temp=arr[j];
                 arr[j]=arr[j+1];
                 arr[j+1]=temp;
            }
        }           
    }

6개 요소의 배열이 버블 정렬 알고리즘을 사용하여 정렬된다고 가정합니다. 두 번째 또는 세 번째 반복 후에 배열이 정렬되더라도 루프는 6번째 반복까지 계속됩니다. 이것은 단지 시간 낭비일 뿐입니다. 따라서 컴퓨터 과학자들은 내부 for 루프에서 스와핑이 발생하는지 확인하는 또 다른 변수 swapped를 사용하여 이 알고리즘을 최적화하는 방법을 알아냈습니다. 내부 루프 내부에 스와핑이 없다면 배열이 이미 정렬되어 있고 모든 반복을 실행하는 대신 for 루프에서 빠져나올 수 있음을 의미합니다.

버블 정렬 알고리즘의 최적화된 구현은 다음과 같습니다.

void bubbleSort(int arr[],int n)
        {
         int i, j,temp;
         int swapped=0;

            for(i = 0; i < n-1; i++)
            {
                for (j = 0; j < n-i-1; j++)
                {
                    if (arr[j] > arr[j+1])
                    {
                     temp=arr[j];
                     arr[j]=arr[j+1];
                     arr[j+1]=temp;
                     // if swapping occurs update swapped to 1
                     swapped =1
                     }
                }
                //If the value of swapped is 0 after all the iterations of the inner loop
                //then break out
                if(swapped==0)
                {
                    break;
                }

            }           
        }

버블 정렬의 복잡도 분석
버블 정렬에서 우리는 첫 번째 통과에서 N-1 비교, 두 번째 통과에서 N-2 비교가 있는 것을 보았습니다. 따라서 버블 정렬의 복잡도를 계산하기 위해서는 비교 횟수를 계산해야 합니다. 다음과 같이 표시할 수 있습니다.

f(n) = (n – 1) + (n – 2) + (n – 3) + ..... + 3 + 2 + 1
f(n) = n (n – 1)/2
f(n) = n^2/2 + O(n) = O(n^2)

버블 정렬 알고리즘의 시간 복잡도는 다음과 같이 요약할 수 있습니다.

최악의 경우 시간 복잡도 [ Big-O ]: O(n^2)

최상의 경우 시간 복잡도[Big-omega]: O(n)

평균 시간 복잡도[Big-theta]: O(n^2)

버블 정렬 알고리즘의 주요 장점은 알고리즘의 단순성입니다.

위의 블로그 게시물을 통해 거품 정렬 알고리즘에 대한 건전한 지식을 얻었을 것이라고 확신합니다. 질문이 있거나 추가 설명이 필요한 경우 언제든지 의견을 남겨주세요.
감사합니다.