[알고리즘 구현] Bubble sort

Bubble sort

• 면접준비로 버블소트까지 구현을 해보고싶었다.
• 평소에 개념은 알지만 사용은 안해봐서 2학년때? 이후로 처음 짜봤다.
• 평균 시간복잡도는 O(n^2), 최악도 O(n^2) 상당히 비효율적이다

코드(C++)

bool checkIncrease(int * arr){
    for(int i=1;i<n; i++){
        if(arr[i-1] > arr[i]){
            return false;
        }
    }
    return true;
}
void bubbleSort(int * arr){
    while(!checkIncrease(arr)){
        for(int i=1;i<n;i++){
            if(arr[i-1] > arr[i]){
                swap(arr[i-1], arr[i]);
            }
        }
    }
}