버블 정렬

정렬 알고리즘

데이터 사이에는 유사한 속성이나 일련의 순서가 있습니다.

그래서 많은 컴퓨팅 알고리즘에서는 처리중인 데이터를 특정 형태로 정렬할 때가 있습니다.

 

예를 들어

이진 탐색은 알고리즘을 수행하기 전에 데이터를 비교하도록 특정 순서로 배열을 정렬합니다.

데이터베이스는 쿼리를 실행하여 ㄷ특정 속성에 따라 항목을 정렬합니다.

즉, 데이터를 정렬하면 알고리즘이 중복 데이터를 빠르게 식별하거나 필요한 데이터를 매우 빠르게 찾을 수 있습니다.

 

버블정렬알고리즘

• 첫번째와 두번째, 두번째와 세번째, ... 마지막까지 비교하면서 교환하며 자료를 정렬하는 방식입니다.

출처 : https://sylagape1231.tistory.com/17

• 이 방식을 사용하면 가장큰 수는 첫 사이클에 배열의 맨 마지막에 위치하게 됩니다.

• 이렇게 모든 사이클이 끝나면 오름차순으로 정렬되게 됩니다.

 

구현하기

1. 비교할 수를 정합니다.

2. 비교를 하면서 왼쪽의 수가 오른쪽보다 크다면 오른쪽과 왼쪽을 교환합니다.

3. 1사이클씩돌면서 가장 큰수들이 맨 뒤에 가므로 비교를 하지 않아도 됩니다.

4. 이 과정을 비교할 수의 양만큼 반복합니다.

(오름차순)

function bubblesort(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1]
                arr[j + 1] = temp;
            }
        }
    }
    return arr
}
console.log(bubblesort([8, 5, 1, 6, 9]))

 

이중 for 문을 사용하는 이유

→ arr[0]번째부터 arr[1]을 비교하고 arr[1]과 arr[2]를 비교하면서 배열의 n-2번째 와 배열의 n-1번째 까지 비교하고 끝내면 가장 큰수가 가장 뒤에 배치하게 된다.

이 과정을 배열의 수-1만큼 비교 하면서 배열을 정렬해야 하므로 이중for문을 사용하게 되었다.

 

n - i - 1을 하여 for문의 종료 조건을 줄인 이유

→ 배열의 끝은 한사이클이 돌때마다 가장큰수들이 가장 뒤에 배치되게 된다.

즉, 한 사이클이 돌면 가장큰수가 맨뒤에 배치, 그 다음 사이클에 가장큰수보다 작은 큰수가  맨뒤 -1에 배치 되게 된다.

그렇게 때문에 한사이클이 끝나고 맨뒤에서부터 하나씩 줄여 나가면서 반복을 한다.

 

 

temp를 사용하는 이유

→ 변수는 서로 교환을 할수가 없습니다

예를들어

let a = 15;
let b = 10;

이렇게 있다고 가정해봅시다. 

a = b

b = a

를 해보면  a에는 b가 들어가게 되면서 결과적으로

a = 10, b = 10이 되버립니다.

 

즉, 서로 값을 교환해 주기 위해서는 값을 대입할 변수가 하나더 필요하게 됩니다.

let a = 15;
let b = 10;
let temp = 0;

위처럼 있게 되면 

temp = a
a = b
b = temp

a의 값은 temp에 저장, a는 b의 값 저장, b는 다시 a의 값을 저장한 temp를 저장하게 되면

a와b는 서로 교환을 하게 된겁니다.

 

그렇기 때문에 temp를 써서 배열의 교환을 할수 있었습니다.

 

버블 정렬은 로직이 간단하여 생각 만큼 어렵지 않게 구현을 할 수가 있었습니다.

하지만 버블정렬은 단순한 만큼 느리기 때문에 실제 응용 프로그램에 적용할 수가 없다고 합니다.

좋은 공부였다..