정렬 알고리즘(버블/삽입/선택)

 

정렬 알고리즘은 주어진 데이터를 특정한 순서대로 정렬하는 방법입니다. 여러 가지 정렬 알고리즘 중에서 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort)은 기본적인 비교 기반 정렬 알고리즘으로 자주 사용됩니다. 이들은 모두 시간 복잡도가 O(n²)로 비효율적이지만, 간단하게 구현할 수 있습니다.

---

1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 교환하는 방식으로 정렬을 수행하는 알고리즘입니다. 가장 큰 값이 매번 마지막으로 "버블처럼" 올라가므로 버블 정렬이라는 이름이 붙었습니다.

작동 원리

• 배열의 처음부터 끝까지 인접한 두 값을 비교하고, 그 순서가 잘못되었으면 값을 교환합니다.
• 첫 번째 반복이 끝나면 가장 큰 값이 마지막에 위치하게 됩니다.
• 이 과정을 배열의 크기만큼 반복하여 정렬합니다.

시간 복잡도: O(n²)

• 최선: O(n) (이미 정렬된 경우)
• 최악: O(n²) (역순 배열의 경우)

let arr = [4,7,12,3,6,1,8];

function bubbleSort(arr){

    for(let i=0;i<arr.length-1;i++){
        for(let j=i+1;j<arr.length;j++){
            if(arr[i]>arr[j]){
                let temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
    return arr;
}

console.log(bubbleSort(arr));

 

 

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 이미 정렬된 부분에 새로운 요소를 적절한 위치에 삽입하는 방식으로 정렬을 수행하는 알고리즘입니다. 마치 카드 정리와 비슷한 방식으로 작동합니다.

작동 원리

• 첫 번째 요소는 이미 정렬된 상태로 간주하고, 두 번째 요소부터 차례대로 정렬된 부분에 삽입합니다.
• 삽입할 위치를 찾기 위해 정렬된 부분을 뒤에서부터 비교합니다.
• 배열의 모든 요소가 정렬될 때까지 이 과정을 반복합니다.

시간 복잡도: O(n²)

• 최선: O(n) (이미 정렬된 배열)
• 최악: O(n²) (역순 배열의 경우)

let arr = [4,7,12,3,6,1,8];

function insertionSort(arr){
    for(let i=1;i<arr.length;i++){
        for(let j=0;j<i;j++){
            if(arr[i]<arr[j]){
                let temp = arr[i];
                arr.splice(i,1);
                arr.splice(j,0,temp);
            }
        }
    }

    return arr;
}

console.log(insertionSort(arr));

//chat gpt의 답
let arr1 = [4, 7, 12, 3, 6, 1, 8];

function insertionSort1(arr1) {
    for (let i = 1; i < arr1.length; i++) {
        let current = arr1[i]; // 현재 삽입할 값
        let j = i - 1;

        // current보다 큰 값을 오른쪽으로 이동
        while (j >= 0 && arr1[j] > current) {
            arr1[j + 1] = arr1[j];
            j--;
        }

        // 적절한 위치에 current 삽입
        arr1[j + 1] = current;
    }

    return arr1;
}

console.log(insertionSort1(arr1)); // [1, 3, 4, 6, 7, 8, 12]

 

3. 선택 정렬 (Selection Sort)

선택 정렬은 배열에서 가장 작은 값을 찾아 앞쪽에 놓는 방식으로 정렬을 수행하는 알고리즘입니다. 한 번의 반복에서 최솟값을 찾아서 첫 번째 요소와 교환하는 방식입니다.

작동 원리

• 첫 번째 요소부터 시작하여 배열에서 가장 작은 값을 찾습니다.
• 찾은 가장 작은 값과 첫 번째 요소를 교환합니다.
• 두 번째 요소부터 다시 배열에서 가장 작은 값을 찾아 두 번째 요소와 교환합니다.
• 이 과정을 배열의 끝까지 반복하여 정렬합니다.

시간 복잡도: O(n²)

• 최선: O(n²)
• 최악: O(n²)

let arr = [4,7,12,3,6,1,8];

function selectionSort(arr){
    for(let i=0;i<arr.length-1;i++){
        let min =i;
        for(let j=i+1;j<arr.length;j++){
            if(arr[min]>arr[j]){
                min = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
    return arr;
}

console.log(selectionSort(arr));

 

직접 구현해봤는데 생각보다 어려웠고 정렬되는 과정을 손으로 써가면서 짰더니 좀 편했다.