7-2) 버블 정렬

문제

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요. 정렬하는 방법은 버블정렬입니다.
[입력설명]
첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
[출력설명]
오름차순으로 정렬된 수열을 출력합니다.

입력예제 1

6
13 5 11 7 23 15

출력예제 1

5 7 11 13 15 23


문제 풀이

예습 이론

  • 버블 정렬은 정렬하는 모습이 거품이 꺼지는 모습과 비슷하기 때문에 지어진 이름이다. 정렬되는 모습
    버블 정렬은 O(n^2)이기 때문에 성능이 좋지 않다. 거기에 성능이 안 좋은 정렬 중에서도 가장 안 좋은 편에 속하는 정렬이라, 주로 알고리즘 교육용을 제외하고는 사용되지 않는다. (앞 챕터에서 배웠던 선택정렬보다 교환이 많이 일어나기 때문에, 복잡도도 더 크다)
    한 과정에 겨우 두 수의 위치를 서로 바꾸는 작업밖에 못한다. 따라서 위에서 말했던 것 처럼 성능이 매우 좋지 않다. 하지만 간단한 작업을 하는 만큼, 코드를 짜기는 쉽다. 코드는 간단하지만 반복문을 두 번 중첩해서 돌기 때문에 성능이 좋지 않다.
    버블정렬은 사용하지 말자!

코드

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(arr){
                let answer=arr;
                for(let i=0; i<arr.length-1; i++){
                    for(let j=0; j<arr.length-i-1; j++){
                        if(arr[j]>arr[j+1]) {
                            [arr[j], arr[j+1]]=[arr[j+1], arr[j]]; 
                        }
                    }
                }
                return answer;
            }

            let arr=[13, 5, 11, 7, 23, 15];
            console.log(solution(arr));
        </script>
    </body>
</html>

참고

https://www.zerocho.com/category/Algorithm/post/57f67519799d150015511c38

좋은 웹페이지 즐겨찾기