누구나 자료 구조와 알고리즘 | 빅 오 표기법 | 빅 오로 코드 속도 올리기

✔️버블 정렬 : 매우 기본적인 정렬 알고리즘

• 버블 정렬 방법
  • 배열의 첫 번째 원소부터 다음 원소와 비교하며 오른쪽 값이 더 크면 두 항목을 교환
  • 교환이 일어나지 않는 패스스루가 생길 때까지 반복
  • 버블 : 각 패스스루마다 정렬되지 않는 값 중 가장 큰 값
• 버블 정렬 실제로 해보기

• 버블 정렬의 효율성
  • 버블 정렬 알고리즘 = 비교 + 교환
  • ex) 원소가 5개라면.. ⇒ 총 20단계
    • 비교 : 4 + 3 + 2 + 1 = 10번
    • 교환 : 4 + 3 + 2 + 1 = 10번
  • ex) 원소가 10개라면.. ⇒ 총 90단계
    • 비교 : 9 + 8 + 7 + … + 1 = 45번
    • 교환 : 9 + 8 + 7 + … + 1 = 45번
  • ex) 원소가 20개라면.. ⇒ 총 380단계
    • 비교 : 20 + 19 + 18 + … + 1 = 190번
    • 교환 : 20 + 19 + 18 + … + 1 = 190번
  • 원소 수가 증가할수록 기하급수적으로 늘어남..!
  • 버블 정렬의 장점
    • in place 알고리즘으로 메모리가 절약됨
      in place란?
      👉🏻 자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아닌 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻
  • 버블 정렬의 단점
    • 자료의 개수가 많아질수록 성능이 매우 떨어짐
    • 배열의 원소가 N개일 때 비교•교환의 최악의 단계 수 = $n(n-1)$ ⇒ 대략 O(n^2) (이차 시간이라고 부름) 소요됨
• 이차 문제

중첩 루프가 보인다면 O(N^2) 냄새를 바로 맡아야 한다!!!

• 선형 해결법 

hasDuplicateValueA() (바로 위 코드👆🏻)보다는 메모리를 더 소비하지만 엄청난 속도 향상을 이룸