알고리즘, CS

알고리즘 특강 - 4. 버블 정렬, 선택 정렬, 삽입 정렬

차돌박이츄베릅 2023. 6. 7. 12:21

버블 정렬

출처: 이해가 어려워서 이미지 자료도 빌리겠습니다 ㅜㅜ

첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, …

이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식.

작은 숫자, 큰 숫자 순서로 있으면 내버려두고 큰 숫자,  작은 숫자 순서로 있으면 둘의 위치를 변경!

버블 정렬의 시간 복잡도는 O(N^2)

 

 

[버블정렬 함수_오름차순 버전]

function bubbleSort(array) {
    let n = array.length; // array의 길이를 n에 저장해요! 루프 카운트 변수로 쓰겠죠?
    for (let i = 0; i < n; i++) {
        // 이건 array를 순차적으로 돌겠다는 뜻이구요!
        // 이건 버블정렬 알고리즘의 특성처럼 1개씩 줄어들면서 반복하며 비교를 해요.
        for (let j = 0; j < n - i - 1; j++) {
            // n-1 -> n-1-1 -> n-2-1
            if (array[j] > array[j + 1]) {
                // 앞의 원소가 뒤의 원소보다 크면 바꿔야겠죠?
                let temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}

console.log('정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ', bubbleSort([4, 6, 2, 9, 1]));
console.log('정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ', bubbleSort([3, -1, 17, 9]));
console.log('정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ', bubbleSort([100, 56, -3, 32, 44]));

 

 

 


선택 정렬

이미지도 퍼옴

선택 정렬은 index 하나마다 위치할 원소를 결정하고 그 다음 index로 넘어가는 기법이에요!

다음과 같이 사람들이 일렬로 쭉~ 서 있는데, 한번 쓱 둘러보면서 가장 키 작은 사람을 찾는겁니다.

 

그리고 전부 다 봤다면, 그 중 가장 키 작은 사람! 맨 앞으로 와! 한 다음에 또 둘러보면서 두 번째로 키 작은 사람을 두 번째에 배치 시킵니다.

 

선택 정렬도 시간 복잡도는 O(N^2)

 

 

[선택정렬 함수_오름차순 버전]

function selectionSort(array) {
    let n = array.length; // 루프 카운트!
    // 이번에는 i ~ n - 2까지 돌면서 실험군을 선택해요!
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i; // i번째에 들어갈 최소값을 찾아요!
        for (let j = i + 1; j < n; j++) {
            // 현재 최소값으로 설정된 친구보다 더 작은 친구를 발견하면!
            if (array[j] < array[minIndex]) {
                minIndex = j; // 최소값 인덱스를 갱신합니다!
            }
        }
        // i번째에 최소값 인덱스에 있는 값을 넣어줍니다!
        let temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
    return array;
}

console.log('정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ', selectionSort([4, 6, 2, 9, 1]));
console.log('정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ', selectionSort([3, -1, 17, 9]));
console.log('정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ', selectionSort([100, 56, -3, 32, 44]));

 

 

 


삽입 정렬

이미지도 퍼옴

선택 정렬이 전체에서 최솟값을 "선택" 하는 거 였다면,

삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식

 

선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만,

삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식입니다!

 

이미 키 순으로 정렬된 사람들이 일렬로 쭉~ 서 있는데,

다음 원소가 그 정렬된 사람들 사이를 비집고 들어가면서

아 여기가 내 자리구나! 하면서 삽입하며 정렬하는 방식

 

삽입 정렬의 시간 복잡도는 O(N^2)지만 최선의 경우엔 Ω(N)만큼의 시간 복잡도가 걸립니다.

대상 배열이 거의 정렬되었다고 가정하면 더 비교를 하지않고 바로 다음 스텝으로 넘어가기 때문

 

 

[삽입정렬 함수_오름차순 버전]

function insertionSort(array) {
    let n = array.length; // 루프 카운트!
    // 삽입 정렬의 0번째 인덱스는 정렬된 상태라고 판단하므로 인덱스가 1부터 시작해요!
    for (let i = 1; i < n; i++) {
        // 최초 i = 1 -> i = 2
        // 현재 index 범위 내에서 비교를 시작하죠! 비교 방향은 끝에서부터 시작해요!
        for (let j = i; j > 0; j--) {
            // 최초 j = 1 -> j = 2 -> j = 1
            // 뒤의 값보다 앞의 값이 크면 바꿔줘요!
            if (array[j - 1] > array[j]) {
                // array[1-1] > array[1]
                let temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            } else {
                // 그렇지 않다면 정렬된 상태이기 때문에 이번 루프는 바로 나가도 되어요!
                break;
            }
        }
    }
    return array;
}

console.log('정답 = [4, 5, 7, 7, 8] / 현재 풀이 값 = ', insertionSort([5, 8, 4, 7, 7]));
console.log('정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ', insertionSort([3, -1, 17, 9]));
console.log('정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ', insertionSort([100, 56, -3, 32, 44]));

 

 

 


그 외 앞으로 추가로 공부해야될 것들 메모 ...ㅎㄷㄷ

정렬 알고리즘

  • 머지 정렬
  • 힙 정렬
  • 퀵 정렬
  • 셸 정렬
  • 기수 정렬

자료구조

  • 트리 (참고로 트리 종류도 엄청 많아요!)
  • 트라이
  • 그래프
  • 해시 테이블

이 밖에 재귀, DP(다이나믹 프로그래밍), 탐욕 알고리즘, 근사 알고리즘, 메모이제이션, 휴리스틱 등등