버블 정렬 (재귀 버전).md

버블 정렬 (재귀 버전)

Bubble Sort is one of the simplest sorting algorithms that compares two elements at a time and swaps them if they are in the wrong order. This process is repeated until the entire sequence is in order.

절차

Base case: If the size of the array is 1, return.

• We need to fix the last element of the current sub-array. For this, iterate over the entire array using normal Bubble Sort, and perform swapping.
• Next, call the function on the entire array excluding the last element(which was fixed by the iteration in the above step)
• Repeat until Base Case is reached.

시간 복잡도

• 최선: $O(n)$
• 평균: $O(n^2)$

공간 복잡도

• 최악: $O(n)$ (참고: 기존 버블 정렬의 공간 복잡도는 $O(1)$)

예시

Let the given array be: {5, 3, 2, 1, 4}

First Iteration:

• {5, 3, 2, 1, 4} -> {3, 5, 2, 1, 4} Swap since 5 > 3
• {3, 5, 2, 1, 4} -> {3, 2, 5, 1, 4} Swap since 5 > 2
• {3, 2, 5, 1, 4} -> {3, 2, 1, 5, 4} Swap since 5 > 1
• {3, 2, 1, 5, 4} -> {3, 2, 1, 4, 5} Swap since 5 > 4

This iteration has fixed the position of 5. Now, we will consider the array up to index 3.

Second Iteration:

• {3, 2, 1, 4, 5} -> {2, 3, 1, 4, 5} Swap since 3 > 2
• {2, 3, 1, 4, 5} -> {2, 1, 3, 4, 5} Swap since 3 > 1
• {2, 1, 3, 4, 5}; As 3 < 4, do not swap

Note: As we check one less element with every iteration, we do not need elements at index 3 and 4 i.e., 4 and 5, as 5 is already in order. Formally, for an array with n integers, we consider elements only up to index n - i, where i is the iteration number.

Third Iteration:

• {2, 1, 3, 4, 5} -> {1, 2, 3, 4, 5} Swap since 1 > 2
• {1, 2, 3, 4, 5}; As 2 < 3, do not swap

Fourth Iteration:

• {1, 2, 3, 4, 5}; As 1 < 2, do not swap

Fifth Iteration:

• {1, 2, 3, 4, 5}; As the size of the array is 1, return.

Note: This is the base case.

Pseudo Code

void bubbleSort(arr[], n)
    if(n==1)
        return;

    for(i = 0; i<n-1; i++)
        if(arr[i] > arr[i+1])
            swap(arr[i], arr[i+1])

    bubbleSort(arr, n-1)

영상 URL

• Programming Tutorials