Sorting Algorithm :: Bubble Sort(거품 정렬)

1. Principle of the Bubble Sort

Compare two values, and think as if the smaller value among those value floats up like a bubble.

2. Algorithm of the Bubble Sort

2.1 Method 1

void bubbleSort(int arr[], int n)
{
    for (int i=0; i < n-1; i++)
        bubble(arr, i, n);
}

void bubble(int arr[], int n)
{
    int temp;
    for(int j=0; j<n-1-i; j++)
    {
        if(arr[j] > arr[j+1])
        {
            //swap
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

2.2 Method 2

void bubbleSort(int arr[], int n)
{
    for (int i=0; i<n-1; i++)
    {
        for(int j=0; j<n-1-i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                //swap             
                temp = arr[j];             
                arr[j] = arr[j+1];             
                arr[j+1] = temp;
            }
        }
    }
}

* n-1-i

In the bubble sort, The biggest value is always placed at the last index. It means the last value of the array always locates in the sorted area.

Therefore in the next iteration, we do not need to compare the last value again. That is how we reduce components that we should have to check to see if it is sorted or not.

* n-i

If use n-i, not n-1-i, It might cause the error(out of range).