• 빅오 사용 시 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 기회가 생김

버블 정렬

정렬 알고리즘, 정렬되지 않은 배열이 주어졌을 때 어떻게 오름차순으로 정렬?
순서>
1. 베열 내 연속되 두항목 가리켜, 첫 번째 항목과 두 번쨰 항목 비교
2. 두 항목 비교해 왼쪽이 오른쪽 값보다 크면 두 항목 교환하고 순서 올바르면 그대로
3. 포인를 오른쪽으로 한 셀씩 옮김
4. 배열 끝까지 또는 이미 정렬된 값까지 1-3단계 반복해 배열 첫 패스스루 끝내기
5. 두 포인터 다시 배열 처음 두 값으로 옮겨 1-4 단계 다시 실행해 교환 일어나지 않으면 정렬되어 문제 해결

• 버블 정렬이라 부르는 까닭은 각 패스스루마다 정렬되지 않은 값 중 가장 큰 값, 즉 버블이 올바른 위치로 가기 때문(즉 한 번 패스스루를 수행하면 마지막 항목은 비교하지 않아도 됌)

버블 정렬 적용

function bububbleSort(list){
  let unsortedUntilIdx = list.length - 1;
  let isSorted = false;
  
  while(!isSorted){
    isSorted = true;
    for(let i = 0; i < list.length; i ++){
        if(list[i] > list[i+1]){
          [list[i], list[i+1]] = [list[i+1], list[i]];
          isSorted = false;
          unsortedUntilIdx -= -1;
        }    
      }
  }
  return list
}

bububbleSort([4,2,7,1,3])

• unsortedUntilIdx, 정렬되지 않은 배열 가장 오른쪽 인덱스 기록
  알고리즘 시작 시 전체 배열 정렬되지 않은 상태이므로 배열 마지막 인덱스로 변수 초기화
• isSorted, 배열 정렬 여부 기록하는 변수로 처음엔 정렬되지 않으므로 false
• 배열 정열 될때까지 while 루프 시작해 루프 한 번 실행이 배열의 한 패스스루
• 각 패스스루 안에 교환 일어나기 전까지 배열 정렬되어 있다 가정해 값 교환 시 변수 다시 false로 바꿈 > 전체 패스스루 통과 시 isSorted가 true로 남아 배열 완전 정렬된 상태임
• while 루프 내 for 루프 시작해 루프 안 배열 내 모든 값 쌍 가리켜 변수 i를 포인터로 배열 첫 인덱스부터 정렬되지 않은 인덱스까지 수행
• for 루프 내 모든 인접 값 쌍 비교해 순서 뒤바뀌어 있으면 교환하고 교환되면 isSorted를 false로 바꿈
• 각 패스스루 끝나면 오른쪽 올려준 버블 값 올바른 위치에 있으므로 기존 가리키던 unsortedUntilIdx 인덱스가 정렬된 상태니 값을 1 감소
• isSorted가 true 되면 배열 완전 정렬되어 while 문 종료 후 정렬된 배열 반환

버블 정렬 효율성

• 두 가지 중요한 단계 포함
  1> 비교 2> 교환
• 버블 정렬은 원소 수 증가할수록 단계수 기하급수적으로 늘어남
• 값이 N인 경우 N2 단계, 이차 시간이 소요

이차 문제

• 느린 알고리즘, N2 빠른 알고리즘 N으로 대체
• 보통 배열 n개 값 있을 때 함수 n2번 빅 수행하는데 순회마다 안쪽 루프는 n 번 다시 순회해야하기 때문임

선형 해결법

• 데이터 원소 n개 있을 때 비교 n번만 하되 배열에 삽입을 하여 비교하는 제약이 있긴함
• 속도 향상은 보장되었으나 메모리 소비 하는 부분 고려

마무리

• 빅오 표기법 명확하게 이해 시 느린 코드 식별해 두 경쟁 알고리즘 중 빠른 알고리즘 고를 수 있음

연습문제

다음 함수 배열 가장 큰 수 하나 찾아내지만 효율성 n2 이를 n이 되도록 함수 다시 작성
O(N)2 코드

function greatestNum(arr){
  for(let i=0; i<arr.length; i++){
    let isValGreatest = true
      for(let j=0; j<arr.length; j++){
          if(arr[j]>arr[i]) isValGreatest = false
      }
      if(isValGreatest) return arr[i]
    
  }
}

greatestNum([1,23,4,35,3,23,5])

O(N) 코드

function upgradeGreatestNum(arr){
  let greatestNum = arr[0]
  for(let i=1; i<arr.length; i++){
     greatestNum = greatestNum < arr[i] ? arr[i] : greatestNum
  }
  return greatestNum
}

upgradeGreatestNum([1,23,4,35,3,26,52,123,3,4,2,3,52,2,35])