JS 버블정렬

Sorting Algorithm

-무작위로 섞여있는 데이터를 어떤 기준에 맞춰 정렬하는 알고리즘은 여러가지 있다. 정렬 알고리즘은 다양한 경우에 매우 유용하게 사용된다.

 

1.각종 데이터 목록을 정리하고 싶을 때

2.분포도의 중위값을 알아내고 싶을 때

3.데이터에서 중복값을 잡아내고 싶을때

4.이진 탐색을 하고 싶을 때

-sort()라는 메소드가 존재하지만 좋은 퍼포먼스를 보장하지 않기 때문에 배워야한다. `

 

 

Bubble sort

-요소들이 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고 해서 버블정렬.

-데이터를 두개씩 묶어서 비교한 후 크기가 가장 큰 쪽이 오른쪽으로 가도록 자리를 바꿔가며 크기가 큰 데이터를 오른쪽으로 민다. 1회전이 끝남과 동시에 가장 큰 값이 오른쪽에 가기 때문에 맨 오른쪽 자리가 결정된다.

-n번째 정렬 회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정된다.

 

Big O

-worst Case: O(n^2): 정렬이 하나도 안되어 있는경우

-best Case: O(n):이미정렬이 되어있는 경우

-최악일 경우 각 자리를 찾기 위해서 n번의 순회를 해야하면 n번의 회전 동안에 요소의 개수만큼 또 순회를 해야하기 때문이다. 

장점: in place이기 때문에 메모리가 절약된다. in place라는 것은 자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻이다.

-구현이 쉽고, 이미 정렬된 데이터를 순회하는경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용가능

 

단점: 자료의 개수가 많아질 수록 성능이 매우 떨어진다. 최악일 경우 O(n ^2)이기 때문에

 

 stable: 버블 정렬은 중복 데이터가 있을 경우 데이터의 위치를 교환하지 않고 지나가기 때문에 stable 한 정렬이다. 중복데이터가 있는 경우에 기존 중복 데이터의 순서가 정렬이 다 끝난 이후에도 유지된다.

for문으로 i가 0부터  array.length보다 작을 때까지 loop를 돌고

그 안에 j가 0부터 array.length-1-j까지 loop를돈다.

array.length -1-j인 이유는 array[j]와 array[j+1]을 비교할 것이다.

배열의 마지막 데이터를 포함하지 않아도 검색 대상에 포함되므로 -1

두번째로 각 회전이 끝날때마다 마지막 데이터의 정렬이 끝나기 때문에 i를 빼야해.

swap변수 만들어서 array[j], array[j+1]을 비교하여 array[j]가 더 큼녀 자리를 교환한다.