[Sort] Bubble Sort (버블 정렬, 거품 정렬)

Bubble sort (버블 정렬)

Bubble sort is a basic sort algorithm.

1. choose one object in the j(th) position in arraylist from the beginning.

2. compare with the next object. If the chosen object is bigger than next object, swap objects. 

3. Add one to j and increment to the end of the arraylist. Repeat this process until the end of arraylist.

4. Repeat 1~3 process for length of array times.

** j (second loop) should increase from 1 to i(first loop). Because we can guess that the biggest object in the array will go to end when the loop finishes.

Bubble sort is basic and very easy sort algorithm, but it is inefficient.

The complexity of this algorithm is 

Iteration	Comparison	max swaps
1	n-1	n-1
2	n-2	n-2
...	...	...
n-1	1	1

- Python -

def bubble_sort(collection):

print('----- Bubble Sort -----')

print('input : ' + str(collection))

for i in range(len(collection)-1, 0, -1):

for j in range(0, i):

if collection[j] > collection[j+1]:

collection[j], collection[j+1] = collection[j+1], collection[j]

print(str(len(collection) - i) + 'th ' + 'progressing ... ' + str(collection))

return collection

input = [3, 1, 6, 5, 4, 2]

result = bubble_sort(input)

print('\nresult : ' + str(result))

Result 

- Javascript -

function bubbleSort(array) {

console.log("----- Bubble Sort -----");

console.log(`input : ${array}`);

let input = array;

let tmp;

for(let i = input.length - 1; i > 0; i--) {

for(let j = 0; j < i; j++) {

if(input[j] > input[j + 1]) {

tmp = input[j + 1];

input[j + 1] = input[j];

input[j] = tmp;

}

}

console.log(`${input.length - i}th progressing ... ${input}`);

}

return input;

}

const input = [3, 1, 6, 5, 4, 2];

const result = bubbleSort(input);

console.log(`\nresult : ${result}`);

Result

( 설명추가예정 .. 귀찮아..)