버블 정렬(Bubble Sort) 구현 Python / C++ / JAVA / Kotlin / PHP

여러가지 언어는 조금씩은 했었지만 기본적으로 반복,조건문 입출력 등의 기본 문법 형태를 기억하는지, 복습해보고자 수업에 나왔던 버블 정렬을 구현하면서 복습하기 위해 글을 작성합니다. 사실 언어들이 기본 문법의 생김새가 막 엄청 크게 다르지는 않아서...

예시로는 아래와 같은 배열을 사용하겠습니다. 

array = [3, 2, 7, 10, 5, 9, 4, 1, 6, 8]

버블정렬

버블정렬은 시간 복잡도가 O(n2)인 간단한 코드로 구현할 수 있는 정렬 알고리즘이다.

현재 인덱스의 값과 우측(다음) 인덱스에 값을 비교하여 우측 인덱스의 값이 더 작다면 자리를 바꿔준다. 

array = [3, 2, 7, 10, 5, 9, 4, 1, 6, 8]

위의 array처럼 배열의 원소가 10개라고 가정해보자.

가장먼저 3에서 시작하여 3, 2를 비교하고 2가 더 작기 때문에 자리를 바꾼다. [2, 3, 7, 10, 5, 9, 4, 1, 6, 8]

3과 7을 비교하면 3이 더 작기 때문에 바꿀 필요없이 그대로 두고 7과 10을 비교한다.

이과정을 처음에는 0~9번 인덱스까지 다음에는 0~8번 인덱스까지 ... 계속해서 반복하면

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]과 같은 형태로 정렬이 된다.

 

무작위 배열수의 거품 정렬 예

 

 

파이썬 / Python

array = [3, 2, 7, 10, 5, 9, 4, 1, 6, 8]

for i in range(len(array)-1):
    for j in range(len(array) - 1 - i):
        if array[j] > array[j+1] :
            array[j], array[j+1] = array[j+1], array[j]

print(array) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 출력

코틀린 / Kotlin

fun main(){
    var array = mutableListOf(3, 2, 7, 10, 5, 9, 4, 1, 6, 8)

    for (i in 0 until array.size-1){
        for(j in 0 until array.size-1-i){
            if (array[j] > array[j+1]){
                var temp = array[j+1]
                array[j+1] = array[j]
                array[j] = temp
            }
        }
    }
    print(array) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 출력
}

PHP

$array = [3, 2, 7, 10, 5, 9, 4, 1, 6, 8];
for ($i=0; $i<count($array)-1; $i++){
    for($j=0; $j<count($array)-1-$i; $j++){
        if ($array[$j] > $array[$j+1]){
            $temp = $array[$j+1];
            $array[$j+1] = $array[$j];
            $array[$j] = $temp;
        }
    }
}

print_r($array);
// Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 
// [5] => 6 [6] => 7 [7] => 8 [8] => 9 [9] => 10 ) 출력

C++

#include <iostream>
using namespace std;

int main(){
    int array[10] = {3, 2, 7, 10, 5, 9, 4, 1, 6, 8};
    int length = sizeof(array) / sizeof(int);

    for (int i = 0; i < length; i++){
        for(int j = 0; j < length-i; j++){
            if (array[j] > array[j+1]){
                int temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
            }
        }

    }
    
    for (int i = 0; i < length; i++){
        cout << array[i] << " ";
    }
    // 1 2 3 4 5 6 7 8 9 10 출력
    return 0;
}

JAVA

public class blog {

    public static void main(String[] args) {
        int[] array = {3, 2, 7, 10, 5, 9, 4, 1, 6, 8};

        for (int i = 0; i < array.length - 1; i++) {

            for (int j = 0; j < array.length-1-i; j++ ){
                if (array[j] > array[j+1]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }
        }
        for(int i = 0; i<array.length; i++){
            System.out.print(array[i] + " "); // 1 2 3 4 5 6 7 8 9 10 출력
        }
    }
}