[TIL] 06.27 버블 정렬

jindory·2022년 6월 27일
0
post-thumbnail

알고리즘 정렬

정렬을 배우는 이유?

정말 많이 사용 되기 때문...a

기본적인 정렬 알고리즘 3마리

  • 버블 정렬
  • 선택 정렬
  • 삽입 정렬

정렬 알고리즘 정렬 애니메이션 구경하기👀
https://www.toptal.com/developers/sorting-algorithms


버블 정렬

개요

  • 더 큰 숫자가 한 번에 하나씩 뒤로 이동한다.
  • 루프를 돌면서 각 항목을 다음 항목(해당 항목의 오른쪽에 있는 항목)과 비교하여 다음 항목이 더 크면 스왑한다.
  • 반복을 거듭하면서 정렬해야하는 항목의 수가 감소한다.
function swap(arr, idx1, idx2){
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
  
const swap = (arr, idx1, idx2)=> {
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

지침

  1. 루프를 시작한다.
    배열을 인자로 받쟈, i라는 변수를 가지고, 배열의 맨 끝에서 루프를 시작, 증감문은 감소
  2. 외부 루프 안에 내부 루프를 실행하잣 처음부터 i-1까지 실행
  3. 만약 arr[j]가 arr[j+1]보다 크면 교환
  4. 정렬된 배열 반환
function bubbleSort(arr){
  for(var i=arr.length; i>0; i--){
    for(var j=0; j<i-1; j++){ //루프가 실행될 때 마다  더 적은 횟수로 실행
      if(arr[j] > arr[j+1]){
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      } 
    }
  }
}
  1. 최적화 하기 (O(n²)에서 O(n)으로....)
function bubbleSort(arr){
  let noSwaps
  for(var i=arr.length; i>0; i--){
    noSwaps = true;
    for(var j=0; j<i-1; j++){ 
      if(arr[j] > arr[j+1]){
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps = false;
      } 
    }
    if(noSwaps) break;
  }
}

빅오 표기법의 단순화 규칙

O(2n) => O(n)
O(500) => O(1) ->연산 갯수가 어떤 상황에든 500개가 있다는 것. 일정한 시간
O(13n²) => O(n²)

O(n+10) => O(n)
O(1000n + 50) => O(n)
O(n²+5n+8) => O(n²)


Facts(사실,객관)

  • 비가와서 졸려서 정규 끝나고 살짝 꿀잠 ㅎ-ㅎ

Feelings(느낌,주관)

  • 알고리즘 문제는 한번 살펴보기 전에는... 문제를 못 풀 것 같다!;

Findings(배운점)

  • 상수는 숫자가 엄청 커도 상관없이 시간은 동일하다는 것?.?
profile
메모장/ FE연습장

0개의 댓글