[JavaScript] 버블, 선택 정렬 정리

알고리즘 정리

코딩테스트 문제를 풀어보기 전에 기본적인 알고리즘이 무엇이 있고 개념은 무엇인지 알고 넘어가야 할 것 같아서 정리를 해보려고 합니다.

알고리즘이란 ? 어떤 문제를 해결하기 위해 사용되는 풀이과정이다. 즉 , 문제해결방법.

수학문제 처럼 여러가지 풀이 과정이 있고, 이 중 가장 효율이 좋은 방법 또는 과정으로 정답에 도달 하는 과정을 알고리즘 이라고 합니다.

💡 처음 알고리즘에 대해 공부 하는 것이다 보니 틀린 부분이 있다면 알려주시면 감사합니다.😀

알고리즘의 종류

버블정렬(Bubble Sort)

인접한 두 데이터의 크기를 비교하여 정렬하는 알고리즘 입니다. 정렬 알고리즘에서 가장 기본적인 알고리즘으로 오름차순 또는 내림차순 정렬 하는데 쓰이고 있습니다.

 

	function bubbleSort(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]){
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

const array = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전 배열:", array);

// 버블 정렬 실행
const sortedArray = bubbleSort(array);
console.log("정렬 후 배열:", sortedArray);			

정렬 전 배열: [ 64, 34, 25, 12, 22, 11, 90 ]
정렬 후 배열: [ 11, 12, 22, 25, 34, 64, 90 ]

Js로 버블 정렬 코드를 구현 해봤습니다.

• outLoop(첫번째 for문) 에서 비교할 범위를 지정합니다.
• InnerLoop(두번째 for문) 에서 비교할 범위를 지정합니다.
• if문으로 비교를 해서 자리를 바꿉니다.
  • 첫번째 자리의 값이 그 뒤의 값보다 크다면
    • temp 변수에 첫번째 자리 값을 저장
    • 첫번째 자리 위치를 비교한 자리의 위치와 바꾸기
    • 바꾼 위치의 자리에 temp값 저장

단순한 알고리즘 이지만 공부를 하고 코드를 가보니 생각보다 생각을 많이 해봤던 것 같아요.

• 왜 OutLoop 에서 arr.length -1 인가?
  • 답변: 버블 정렬을 하게 되면 두 개씩 비교를 하기 때문에 n-1까지는 유효 범위이다. 예를 들어 [3,6,7,3] 이라는 배열이 있다면 원래라면 총 4번을 돌아야 겠지만 [3,6], [6,7], [7,3] 이렇게 비교를 하면 총 3번만 돌아도 가능하기 때문에 arr.length -1 까지는 유효 범위 안에 들어갑니다.
• 왜 InnerLoop 에서 arr.length - i - 1 인가?
  • 답변: 두 개씩 비교를 하면서 최종적으로 비교가 끝난 값은 배열의 맨 오른쪽에 위치를 하게 되기 때문에 비교를 할 이유가 없어집니다. 따라서 - i 는 이미 비교가 끝난 값 이기 때문에 - i를 해주었습니다.

 

선택정렬(Selection Sort)

주어진 데이터 중 최소값을 찾아 순서대로 정렬하는 알고리즘입니다.

function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let min = i; // 현재 인덱스를 최솟값으로 초기화
        for (let j = i + 1; j < arr.length; j++) { // i 이후의 요소들과 비교
            if (arr[j] < arr[min]) { 
                min = j; 
            }
        }
        if (min !== i) { 
            const temp = arr[min];
            arr[min] = arr[i];
            arr[i] = temp;
        }
    }
    return arr;
}

const array = [64, 34, 25, 12, 22, 11, 90];
console.log("정렬 전 배열:", array);

// 선택 정렬 실행
const sortedArray = selectionSort(array);
console.log("정렬 후 배열:", sortedArray);

Js로 선택 정렬 코드를 구현 해봤습니다.

• outLoop(첫번째 for문) 에서 비교할 범위를 지정합니다.
• InnerLoop(두번째 for문) 에서 비교할 범위를 지정합니다.
• 첫번째 if문으로 비교를 해서 자리를 바꿉니다.
  • 만약 첫번째 자리의 값이 그 뒤의 값보다 크다면
    • 첫번째 자리의 위치와 비교한 값과 위치 바꾸기
• 두번째 if문으로 첫번째 위치에 값 넣기
  • 만약 최소값 (첫번째 자리의 값)이 i (배열중 최소값이 아니라면)
    • temp 변수에 최소값 저장
    • arrmin의 인덱스 arr[i] 현재의 최소값 저장
    • arr[i](현재 최소값)에 temp에 저장된 최소값 저장

단순한 알고리즘 이지만 공부를 하고 코드를 가보니 생각보다 생각을 많이 해봤던 것 같아요.

• 왜 OutLoop 에서 arr.length -1 인가?
  • 답변: 선택 정렬도 버블 정렬과 마찬가지로 두 개씩 비교를 하기 때문에 n-1까지는 유효 범위이다. 예를 들어 [3,6,7,3] 이라는 배열이 있다면 원래라면 총 4번을 돌아야 겠지만 [3,6], [6,7], [7,3] 이렇게 비교를 하면 총 3번만 돌아도 가능하기 때문에 arr.length -1 까지는 유효 범위 안에 들어갑니다.
• 왜 InnerLoop 에서 j = i + 1, 그리고 j < arr.length 인가?
  • 답변: 선택 정렬은 맨 처음에 있는 값을 기준으로 비교를 하기 때문에 기준점이 i = 0 으로 시작 합니다. 따라서 첫번째 기준 다음부터 비교를 해야 하기 때문에 j = i + 1이고, 배열을 끝까지 비교를 해야하기 때문에 arr.length 까지 입니다.
• 왜 if (min !== i) 이 존재 하는가 !!!
  • 답변: 처음에는 if문을 제외하고 최소값의 위치를 현재 최소값의 위치와 바꾸는 코드로 작성을 했습니다. 그리고 결과를 보니 모든 반복에서 요소를 교환하려고 시도를 하여 코드가 정상적으로 정렬되지 않는 문제가 발생 했습니다.