[Unity C#] 거품 정렬

개념

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.

과정

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

시간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O($n^2$) 이다.

 

장점

• 구현이 매우 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않다. => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장히 비효율적이다.
• 정렬 돼있지 않은 원소가 정렬 됐을때의 자리로 가기 위해서, 교환 연산(swap)이 많이 일어나게 된다.

소스코드

public class BubbleSort_Source : MonoBehaviour
{
    void Start()
    {
        int[] arr = new int[10] { 8, 2, 5, 4, 3, 9, 1, 6, 10, 7 };

        BubbleSort(arr);
    }

    void BubbleSort(int[] arr){

        for (int i = 0; i < arr.Length; i++)
        {       
            for (int j = 1; j < arr.Length - i; j++) // 뒤쪽엔 i만큼 이미 정렬되어 있으므로 -i
            { 
                if (arr[j - 1] > arr[j])
                {            
                    swap(arr, j);
                }
            }
        }

        PrintArray(arr);
    }

    void swap(int[] arr, int j){
        int temp;
        
        temp = arr[j - 1];
        arr[j - 1] = arr[j];
        arr[j] = temp;
    }


    void PrintArray(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            Debug.Log(arr[i]);
        }
    }
}

 

*참고

gyoogle.dev/blog/algorithm/Bubble%20Sort.html

거품 정렬(Bubble Sort) | 👨🏻‍💻 Tech Interview

C++ 소스코드

#include <iostream>

int main() {
    int N, i, j, tmp;
    
    int arr[100];
    
    scanf("%d",&N);
    
    for(i = 0; i < N; i++){
        scanf("%d",&arr[i]);
    }
    
    for(i = 0; i < N-1; i++){ //i는 거들뿐, 반복해주는거 밖에 없음
        for(j = 1; j < N-i; j++){//j에서 인접한 것들끼리만 비교하고 교환함
            if(arr[j-1] > arr[j]){
                tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }
        }
    }
    
    for(i = 0; i < N; i++){
        printf("%d ",arr[i]);
    }
    return 0;
}