알고리즘 / 버블소트

2022 / 8 / 12 금

 

• 알고리즘_버블소트

---

✔️알고리즘_버블소트

 

알고리즘?  

- 문제를 해결하는 방법

 

컴퓨팅에서의 알고리즘이란?

- 데이터에 관한 문제를 해결하는 방법 !

 

알고리즘 성능 평가란?

- 알고리즘이 주어진 문제를 해결하는데 걸리는 시간과 데이터 입력량의 함수 관계를 해석하는 과정

데이터가 증가하면 알고리즘의 시간도 늘어난다.

 

A : 1억개의 데이터를 넣었는데 시간이 1초 걸림

B : 1억개의 데이터를 넣었는데 시간이 60초 걸림

 

누가 더 좋은 코드일까? 당연히 시간 1초 걸리는 A 

 

여기서 원인과 결과를 알 수 있음.

원인은 1억개 

결과는 걸린 시간

알고리즘 성능 평가 기준

- 입력된 데이터의 수와 연산 횟수의 함수 관계로 표현

- 데이터의 수와 연산 횟수의 관계를 정확하게 표현하는 것은 현실적으로 불가능

- 같은 알고리즘, 같은 데이터량 일지라도 상황에 따른 결과를 도출

 

알고리즘 평가 모델

시간 복잡도를 기반으로 한 평가는 아래와 같은 목표로 평가

1 - 최악의 경우를 기준

2 - 정확도가 아닌 근사치 측정

이와 같은 평가모델을 bigO 모델이라 한다.

즉 빅오는 최악의 경우를 기준으로 정확하게 보는게 아니라 패턴으로 보겠다는 것! 

 

알고리즘 성능 평가 시 고려사항

 

무엇이 좋은 알고리즘인가?!

둘 중 뭐가 좋다고 말하기는 애매하다.

그렇다고 하나의 알고리즘을 좋다, 나쁘다라고 말하는 것도 애매함

왜냐하면 다양한 조건을 종합적으로 고려해야 하기 때문.

 

만약 1개의 요소를 가진 배열이 있는데 값은 랜덤이고 0은 단 한 개.

근데 데이터가 1억개인데 0이 1억번째라면..? 5천번째라면..? 

결과 시간은 엄청나다는 것.

 

그렇기에 뭐가 더 좋은 알고리즘이라고 말하기가 애매하다 할 수 있다. 

---

bubble sort

-  앞에서부터 두 수를 비교하여 큰 수가 뒤로 가는 형식으로 오름차순으로 정렬이 가능하다. (내림차순도 가능)

 

        // 배열을 오름차순으로 정렬해보자.

        let bubbleSort = function(arr)

        {

            let i = 0;

            let j = 0;

 

            // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문

            for ( i = 0; i < arr.length -1; i++)

            {

                 // 순차적으로 비교하기 위한 반복문

                for ( j = 0; j < ((arr.length - 1) - i); j++)

                {

                    // 두수를 비교하여 앞 수가 뒷 수보다 크면

                    if (arr[j] > arr[j+1])

                    {

                        // temp에 arr[j]값을 임시저장해둔다.

                        temp = arr[j];

 

                        //arr[j]값에 arr[j+1]값을 넣는다

                        arr[j] = arr[j+1];

 

                        //arr[j+1]에 저장해두었던 temp = arr[j]값을 불러온다.

                        arr[j+1] = temp;

                    }

                }

            }

            return arr;

        };

 

        console.log(bubbleSort([4,2,3,5,1,6]));