[알고리즘] 버블, 선택, 삽입 정렬 알고리즘

정렬알고리즘의 종류

정렬알고리즘의 종류로써는 아래와같은것들이 있다.

• 버블 정렬(Bubble Sort)
• 선택정렬(Selection Sort)
• 삽입정렬(Inser Sort)
• 등등.....

위 정렬 알고리즘이 가장 빠른 정렬 알고리즘은 아니다 설명하기 쉬운 알고림즘 종류들이며

그 이유는 사람들이 정렬을하는 방법과 유사하기 때문이다.

 

1)버블정렬(Bubble Sort)

배열의 처음부터 두개의 값을 비교를 한 후 첫 번째값이 더큰 경우 자리를 바꾼다(swap)을 한다.

 

예) 위 사진의 경우 2,5를 비교한후 첫번째가 더 작기에 가만히 있고, 그 다음 5,3을 비교한후 5가 더 크기에 자리를 바꾼다. 

이런 방식을 처음 부터 끝까지 진행한다.

 

이렇게 한 싸이클을 진행할 경우 가장큰수가 맨 뒤에 가긴하지만 그외의 숫자들이 한사이클안에 각자의 자리로 가지는 않는다.

그렇기에 6개의 요소가있는 배열일경우 5번,4,3,2,...즉 n-1,n-2,n-3..을 비교와 자리바꿈을 진행해야한다.

 

빅오표기법 O(n^2)이다.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
   
    for (let j = 0; j < arr.length; j++) {
        console.log(arr,arr[j], arr[j + 1]);
      if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    }
    console.log("one pass complete");
  }
  return arr;
}

// [ 3, 5, 12, 7, 14, 2 ] 5 12
// [ 3, 5, 12, 7, 14, 2 ] 12 7
// [ 3, 5, 7, 12, 14, 2 ] 12 14
// [ 3, 5, 7, 12, 14, 2 ] 14 2
// [ 3, 5, 7, 12, 2, 14 ] 14 undefined
// one pass complete
// [ 3, 5, 7, 12, 2, 14 ] 3 5
// [ 3, 5, 7, 12, 2, 14 ] 5 7
// [ 3, 5, 7, 12, 2, 14 ] 7 12
// [ 3, 5, 7, 12, 2, 14 ] 12 2
// [ 3, 5, 7, 2, 12, 14 ] 12 14
// [ 3, 5, 7, 2, 12, 14 ] 14 undefined
// one pass complete
// [ 3, 5, 7, 2, 12, 14 ] 3 5
// [ 3, 5, 7, 2, 12, 14 ] 5 7
// [ 3, 5, 7, 2, 12, 14 ] 7 2
// [ 3, 5, 2, 7, 12, 14 ] 7 12
// [ 3, 5, 2, 7, 12, 14 ] 12 14
// [ 3, 5, 2, 7, 12, 14 ] 14 undefined
// one pass complete
// [ 3, 5, 2, 7, 12, 14 ] 3 5
// [ 3, 5, 2, 7, 12, 14 ] 5 2
// [ 3, 2, 5, 7, 12, 14 ] 5 7
// [ 3, 2, 5, 7, 12, 14 ] 7 12
// [ 3, 2, 5, 7, 12, 14 ] 12 14
// [ 3, 2, 5, 7, 12, 14 ] 14 undefined
// one pass complete
// [ 3, 2, 5, 7, 12, 14 ] 3 2
// [ 2, 3, 5, 7, 12, 14 ] 3 5
// [ 2, 3, 5, 7, 12, 14 ] 5 7
// [ 2, 3, 5, 7, 12, 14 ] 7 12
// [ 2, 3, 5, 7, 12, 14 ] 12 14
// [ 2, 3, 5, 7, 12, 14 ] 14 undefined
// one pass complete
// [ 2, 3, 5, 7, 12, 14 ] 2 3
// [ 2, 3, 5, 7, 12, 14 ] 3 5
// [ 2, 3, 5, 7, 12, 14 ] 5 7
// [ 2, 3, 5, 7, 12, 14 ] 7 12
// [ 2, 3, 5, 7, 12, 14 ] 12 14
// [ 2, 3, 5, 7, 12, 14 ] 14 undefined
// one pass complete
// [ 2, 3, 5, 7, 12, 14 ]
// console.log(bubbleSort(array));

 

2)선택정렬(Selected Sort)

배열에서 가장 작은 숫자를 찾은후 맨앞으로 이동시키후,그 부분을 제외한 남은 정렬에서 다시 가장 작은 숫자를 찾아서 다시 맨앞으로 (정렬되지 않은 부분)으로 옮긴다.

비록 비교하는 과정은 버블정렬과 똑같다 (N-1,N-2...) 하지만 자리바꿈 (Swap)의 경우는 최악의 경우가 아닌이상 선택정렬이 더 좋다.

 

빅오 표기법 O(n^2)이다.

 

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    //타겟을 0부터 시작하여
    let minimum = i;
    for (let j = i + 1; j < array.length; j++) {
      // 타겟을 제외한 그외 가장 작은 값을 찾는 과정
      if (array[j] < array[minimum]) minimum = j;
    }
    //현배열 상태, , 
    console.log(array, array[i]+"타켓값", array[minimum]+"타켓을 제외한 가장 작은값");
    //타켓을 제외한 가장 작은값을 찾은경우 자리를 바꾼다.
    if (i !== minimum) [array[i], array[minimum]] = [array[minimum], array[i]];
  }
  return array;
}

console.log(selectionSort([5, 3, 12, 4, 1]));

// [ 5, 3, 12, 4, 1 ] 5타켓값 1타켓을 제외한 가장 작은값
// [ 1, 3, 12, 4, 5 ] 3타켓값 3타켓을 제외한 가장 작은값
// [ 1, 3, 12, 4, 5 ] 12타켓값 4타켓을 제외한 가장 작은값
// [ 1, 3, 4, 12, 5 ] 12타켓값 5타켓을 제외한 가장 작은값
// [ 1, 3, 4, 5, 12 ] 12타켓값 12타켓을 제외한 가장 작은값
// [ 1, 3, 4, 5, 12 ]

3)삽입정렬

타켓이 되는 숫자와 이전위치에 있는 원소를 비교한다. (첫번째 타겟은 두번째 원소부터 시작한다.)

타겟이 되는 숫자가 이전위치에 있던 원소보다 작다면 위치를 서로 교환한다.

위과정이 끝난다면 그 다음 타켓을 찾아 위와 같은 방법으로 반복한다.

빅오표기법 O(n^2)이다.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    //targetValue 정한다.
    let targetValue = arr[i];
    let j;
    console.log(arr,targetValue+" targetValue");
    for (j = i - 1; j >= 0 && arr[j] > targetValue; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = targetValue;
  }
  return arr;
}

console.log(insertionSort([7, 3, 2, 8]));
// [ 7, 3, 2, 8 ] 3 targetValue
// [ 3, 7, 2, 8 ] 2 targetValue
// [ 2, 3, 7, 8 ] 8 targetValue
// [ 2, 3, 7, 8 ]

 

삽입 정렬의 성능

• Best Case : O(n)
  • 삽입 정렬은 완전히 무작위인 배열보다 거의 정렬되어 있는 배열에서 더 빠르다.
    • 온라인에서 실시간으로 데이터를 받고 있고 이를 모아서 정렬해야 하는 코드를 작성해야 할 때, 삽입 정렬은 배열의 한 쪽에 정렬된 부분을 두고 한 번에 하나씩 요소들을 삽입하는 방식이기 때문에 이런 경우 사용하는 것이 적절할 수 있다.
• Worst Case: O(n2)
• Average Case : O(n2)

 

 

참고

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

[JS 알고리즘] 버블 정렬(Bubble sort)

 

[JS 알고리즘] 삽입 정렬(Insertion sort)