버블 정렬과 버블정렬을 이용한 최대값, 최소값, 평균값 구하기

정렬의 기본 버블정렬(O(n^2))

• 정렬 중에 가장 기본 정렬인 버블정렬이다.
• 앞뒤 숫자를 바꾸는 방식을 계속 반복하는 방식으로 구현된다.

var arr = [100,40,30,70,10,90];
for (let i = 0; i < arr.length-1; i++) {
    // i를 빼주는 이유는 내부 for문이 한사이클 돌따마다 가장 큰수 - i번째 큰 수가 정렬 됬기 때문
    for (let j = 0; j < arr.length-1-i; j++) { 
        if(arr[j] > arr[j+1]) { // 앞의 수가 더크면
            const tmp = arr[j]; // 앞의 수를 임시값에 담음 
            arr[j] = arr[j+1]; // 앞에 뒤에껄 담음
            arr[j+1] = tmp; // 뒤에 임시값을 담음
            console.log(arr)
        }
    }
}

[인덱스] 앞의수 뒤의수 => 정렬된 결과 배열

i=0, j < 5(6-1-0)

[0] 100 40 => 40 100 30 70 10 90
[1] 100 30 => 40 30 100 70 10 90
[2] 100 70 => 40 30 70 100 10 90
[3] 100 10 => 40 30 70 10 100 90
[4] 100 90 => 40 30 70 10 90 100

• 처음부터 앞뒤를 비교하면서 반복하다보면 결국 **가장 큰 수가 맨 뒤로 가게 된다.
• 반복 횟수는 배열 크기 - 1

i=1, j < 4(6-1-1)

[0] 40 30 => 30 40 70 10 90 100
[1] 40 70 => 30 40 70 10 90 100 -> 앞의 수가 작음
[2] 70 10 => 30 40 10 70 90 100
[3] 70 90 => 30 40 10 70 90 100 -> 앞의수가 작음

• 다시 처음부터 앞뒤를 비교하면서 반복하다보면 **두번째로 큰 수가 뒤에서 두번째로 가게 된다.
• 반복횟수는 가장 큰 수를 찾았으니 배열크기 - 1 -1
• 앞의 수가 작은 경우는 if문에 걸리지 않기 때문에 실행 안되므로 실행 횟수에서 제외된다.

i=2, j < 3(6-1-2)

[0] 30 40 => 30 40 10 70 90 100 -> 앞의수가 작음
[1] 40 10 => 30 10 40 70 90 100
[2] 40 70 => 30 10 40 70 90 100 -> 앞의 수가 작음

• 다시 처음부터 앞뒤를 비교하면서 반복하다보면 **세번째로 큰 수가 뒤에서 세번째로 감.
• 반복횟수는 가장 큰 수와 두번째 큰 수를 찾았으니 배열크기 - 1 -2 **결국 배열크기 -1 - i와 같다.

i=3, j < 2(6-1-3)

[0] 30 10 => 10 30 40 70 90 100
[1] 30 40 => 10 30 40 70 90 100 -> 앞의 수가 작음

• 다시 처음부터 앞뒤를 비교하면서 반복하다보면 **네번째로 큰 수가 뒤에서 네번째로 감.

버블정렬을 이용해서 배열의 최소값, 최대값, 평균, 합계 구하기

아래와 같이 생각하고 구현했다.

• 버블정렬이 이해가 됬으므로 제대로 이해했나 확인해 볼겸 버블정렬 로직을 이용해서 4가지 값을 구해봤다.
• 오름차순으로 정렬했기 때문에 가장 첫번째 공간에는 최소값이 담겨있고 마지막 공간에는 최대값이 담겨있다.
• 정렬이 한사이클 돌때마다 정렬된 값을 값을 더해주고 마지막에 0번째 값을 더해주면 배열의 모든값이 더해지므로 합계이다.
• 구한 합계를 배열의 길이만큼 나누면 평균값이다.

function MinMaxAvg(arr) {
    let result = {}
    let sum = 0;
    let i, j, temp;
    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];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        sum += arr[j]; // 한차례 정렬이 끝날때마다 합계에 정렬된 수를 더해줌
    }
    result.sum = sum += arr[0]; // 가장 처음 0번째인 0번째를 마지막에 담으면 합계
    result.min = arr[0]; // 0번째가 최소값
    result.max = arr[arr.length-1]; // 마지막 번째가 최대값
    result.avg = sum / arr.length; // 합계를 길이만큼 나누면 평균
    return result;
}