[알고리즘]오름차순으로 정렬하기_JS(버블정렬, 선택정렬)

Q. 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴하시오

버블정렬(bubble Sort)

먼저 많은 정렬 방법 중 버블정렬로 코드를 작성해 보았다.

버블정렬은 서로 다른 두 원소를 검사하여 정렬하는 방법이다.
n과 n+1의 인덱스를 비교해 크기가 순서대로 되어있지 않으면 서로 교환하는 방식이다.

이해를 위한 예시.
[5, 3, 2, 7, 1, 6]이라는 배열이 있다고 가정해보자.
이를 오름차순으로 정렬하기 위해서

1번째로 5와 3을 비교해서 순서(오름차순)이 아니기 때문에 [3, 5, 2, 7, 1, 6]로 교체
2번째로 5와 2를 비교해서 순서에 맞게 [3, 2, 5, 7, 1, 6] 교체
3번째로 5와 7을 비교해서 순서에 맞기 때문에 다음 인덱스로 넘어감
...
한바퀴를 다 확인해 [3, 2, 5, 1, 6, 7] 까지 변경이 완료되면 다시 0번째 인덱스부터 검사한다.
물론 가장 큰 숫자는 가장 끝 인덱스로 보냈기 때문에 길이-1만큼만 확인한다
정렬이 완료 될 때까지 반복한다.

이렇게 가장 큰 수부터 정렬되어 내려오는 것을 "버블정렬"이라고 한다.

버블 정렬을 실행하는 코드는 아래와 같다

const bubbleSort = function (arr) {
  let swap = 0
  let swaps = 0

  for(let i = 0; i<arr.length; i++)
    {
      for(let j = 0; j<arr.length-1; j++)
      {  
        if(arr[j] > arr[j+1])
          {
            swaps ++
            swap = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = swap
          }
      }
      if(swaps === 0)
        break
      //시간 복잡도를 위해 아무것도 정렬이 되지 않은 경우 배열이 정렬된 상태이므로 break로 for문 탈출
      //이 문구 넣어주지 않으면 시간 초과됨
    }
    return arr
};

 

버블정렬은 간단한 이론이지만 옆에 있는 요소와 계속해서 바꾸는 액션이 일어나기 때문에 이미 최종자리에 위치해 있는 경우에도 다른자리로 바뀌었다가 돌아오는 등 비효율적인 액션이 생길 수 있다

선택정렬(seletion  Sort)

선택정렬은 버블정렬처럼 그닥 효율적인 정렬방법으로는 평가받지 못한다.
하지만 간단하다는 장점이 있으며 그나마 버블정렬보다는 시간복잡도 부분에서 효율적으로 평가받는다.

선택정렬은 해당 순서에 들어갈 요소의 위치가 이미 정해져 있고, 해당 자리에 올 값을 찾는 방식이다

이해를 위한 예시

버블정렬과 동일하게 [5, 3, 2, 7, 1, 6]이라는 배열이 있다고 가정해보자
1번째로 해당 배열에서 최솟 값을 찾은 뒤 가장 앞자리의 5와 교환한다. [1, 3, 2, 7, 5, 6]
2번째로 두번째 자리와 최솟값을 비교한뒤 교환한다. [1, 2, 3, 7, 5, 6]
...
n번째로 남은 두 수를 비교하여 정렬한다 [1, 2, 3, 5, 6, 7]

이렇게 최솟값과 해당 자리의 값을 비교해서 정렬하는 것을 "선택정렬"이라고 한다.
위의 예시에서 확인 할 수 있 듯이 확인해야 하는 값이 선택정렬이 많이 적은 것을 볼 수 있다.

 

해당 문제를 선택정렬로도 풀어보았다.

function seletionSort (array) {  
  let swap = 0
  for (let i = 0; i < array.length; i++) {    
    let minIndex = i;
//최소값과 비교할 인덱스
    for (let j = i + 1; j < array.length; j++) {      
      if (array[minIndex] > array[j])
          minIndex = j; 
    //최솟값 찾기
    }
    if (minIndex !== i) {   
      swap = array[minIndex]; 
      array[minIndex] = array[i];
      array[i] = swap;
    }
    //최솟값과 비교할 인덱스와 최솟값이 다르다면 swap 하기
  } 
  return array;
}

이렇게 코드 작성했을 때, 10,000길이 이상 되는 큰 배열에는 시간이 많이 걸리는 모습을 보였다.

선택정렬일 때도 시간을 줄일 수 있는 방법은 없을까..

---

참고

다양한 정렬방법 중 소요되는 시간이 얼마인지 비교하는 영상이다. 

https://youtu.be/kPRA0W1kECg