Bubble Sorting

 

빨간색 밑줄은 정렬된 요소를 의미한다.

시간복잡도는 O(n)과정을 n번 수행해야 하므로 O(n^2)이고,

정렬을 수행하는 동안 추가로 필요한 메모리가 없으므로 공간복잡도는 O(1) 이다.

Bubble Sorting 과정

 

#include <bits/stdc++.h>



void BubbleSort(std::vector<int> & arr) {
    for (int i = arr.size(); i >= 0; --i) {
        for (int j = 0; j < i - 1; ++j){
            if (arr[j] > arr[j + 1]) std::swap(arr[j], arr[j + 1]);
        }
    }
}


void printArr(std::vector<int> arr){
    for (int ele : arr) {
        std::cout << ele << " ";
    }
    std::cout << "\n";
}


int main(int argc, char** argv) {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<int> arr = {9, 3, 5, 7, 1};
    std::cout << "before : ";
    printArr(arr);
    BubbleSort(arr);
    std::cout << "after  : ";
    printArr(arr);
	return 0;
}

 

 

 

정렬 알고리즘의 안정성 테스트

 

숫자를 기준으로 정렬했을 경우 뒤에 있는 알파벳의 상대적 위치가 유지된다.

그러므로 Stable 정렬이다.

 

 

#include <bits/stdc++.h>



void BubbleSort(std::vector<std::string> & arr) {
    for (int i = arr.size(); i >= 0; --i) {
        for (int j = 0; j < i - 1; ++j){
            if (arr[j][0] > arr[j + 1][0]) std::swap(arr[j], arr[j + 1]);
        }
    }
}


void printArr(std::vector<std::string> arr){
    for (auto ele : arr) {
        std::cout << ele << " ";
    }
    std::cout << "\n";
}


int main(int argc, char** argv) {

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<std::string> arr = { "7a", "5a", "5b", "7b", "3c"};
    std::cout << "before : ";
    printArr(arr);
    BubbleSort(arr);
    std::cout << "after  : ";
    printArr(arr);
	return 0;
}

 

 

 

 

정리

시간복잡도 O(N^2)

공간복잡도 O(1)

Stable : O