Algorihtm :: 코드카타 5주차 선택정렬(selection Sort), 버블정렬(Bubble Sort)

정렬 알고리즘?

정렬알고리즘은 순서가 없던 데이터를 순서대로 바꿔 정렬하는 알고리즘이다. 그런데 정렬에서는 sort 메소드가 존재한다. 프로그래밍언어에는 너무나도 당연하게 자체적 정렬메소드가 꼭 존재한다. 그런데 우리는 왜 정렬 알고리즘을 배우는걸까? 그 이유는 시스템에서 자체적으로 존재하는 정렬 메소드가 내가 원하는 정렬을 완벽하게 해낸다고 보장하지 않기 때문이다. 상황에 따라 정렬을 어떻게 사용하는것이 좋을지가 달라지기 때문에 기본적인 정렬 알고리즘은 꼭 알아야한다!

 

---

 선택정렬(selection Sort) 

 

 

선택정렬은 가장 쉽고 기본적인 정렬 알고리즘이다. 선택정렬은 정렬되지 않은 데이터 중 가장 작은 데이터를 선택해서 맨앞부터 순서대로 정렬해나간다. 

 

위코드 repl.it 자료

 

주어진 리스트에서 가장 최소값을 찾아본다! 최소값을 구해 가장 맨 처음 index값과 비교한다. 하나씩 index값을 증가시키며 비교해나간다.

 

선택정렬의 장점으로는 구현하기도, 이해하기도 쉽다는 것과 in place알고리즘으로 메모리가 절약된다는것이다. 하지만 아무리 최선의 경로를 탄다고해도 시간이 걸리는 만큼 성능이 떨어진다.

※ in place 알고리즘 : 저장된 그 공간내에서 알고리즘이 돌기 때문에 추가적인 메모리 공간을 많이 필요로 하지 않는 혹은 전혀 필요하지 않는 알고리즘

 

 

 

---

 

 

 생각해보자,코드리뷰! 

 

nums라는 정렬되지 않은 숫자 배열을 주면, 오름차순(1,2,3..10) 으로 정렬된 배열을 return해주세요.

const selectionSort = (nums) => {
  if(nums.length < 2){
    return nums;
  }
  const arr = [nums[0]];
  const min = [];
  const max = [];
  
  for(i=1; i<nums.length; i++){
    if(nums[i] < arr){
      min.push(nums[i]);
    }else if(nums[i] > arr){
      max.push(nums[i]);
    }
    return min.concat(arr, max);
  }
}

 

처음 문제를 보고 바로 썼던 알고리즘이다. runJS에서는 무난하게 돌아갔지만 치명적인 문제가 있었으니 최소값을 제대로 설정하지 않았다는것이다. ;-; 이부분은 아직 수정을 하지 못했다. 이번 주말에 반드시 해결해서 아래에 첨언하도록 하겠다.

 

 

 

---

 

 버블정렬(Bubble Sort) 

 

 

버블정렬은 인접한 데이터를 교환해서 정렬해주는 알고리즘이다. 알고리즘이 정렬되는 모습이 마치 거품처럼 일어난것처럼 연쇄적으로 정렬이 되기 때문에 이러한 이름을 붙게 되었다.

 

위코드 repl.it 자료

 

비교할 데이터를 앞, 뒤로 두개씩 묶어 비교한 후 큰쪽이 오른쪽으로 이동하도록 만든다. 반복문이 한번 끝난과 동시에 해당 리스트에서 가장 큰 값이 가장 오른쪽이 가기 때문에 맨 오른쪽 자리가 결정난다. 결론은 n번째 정렬회차가 끝나면 뒤에서 n번째 자리의 데이터가 확정된다는 것이다.

 

버블정렬의 장점으로는 선택정렬과 동일하다. 쉽고 이해하기 좋은 알고리즘, 그리고 메모리를 적게 사용하는 in place알고리즘이라는 것이다. 또한 순회가 빠르기 때문에 테스트용도로도 사용할 수 있다. 그러나 자료의 개수가 많아지면 많아질수록 성능도 떨어진다는 단점을 가지고 있다.

 

 

---

 

 생각해보자,코드리뷰! 

 

nums라는 배열을 주면, 버블정렬 알고리즘으로 배열을 정렬해주세요.

const selectionSort = (nums) => {
const bubbleSort = nums => {
 let arr = [...nums];
  
for(i = 0; i < arr.length - 1; i++) {
  for (j = 0; j < arr.length - i; j++) {
    if (arr[j] > arr[j + 1]) {
      let point = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = point;
    }
  }
}  return arr;
}

해당 알고리즘은 정석대로 두개의 for문을 돌려서 작성했다. j와 j+1값을 i만큼 반복하여 가장 큰 값부터 가장 작은 값을 순차적으로 구한다.

 

 

참고문서 : im-developer.tistory.com/133

[JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기 (Bubble Sort, Insertion Sort, Select