✍️
TIL
  • TIL
  • react
    • react 16.3 이후 라이프 싸이클
    • 함수형 컴포넌트 vs 클래스 컴포넌트
    • React의 장점
    • 기본문법
    • Flow Diagram
    • redux-saga
    • nextjs
    • mobx
    • 리액트는 어떻게 동작할까?
  • data-structure
    • 이진 검색 트리(binary search tree)
    • HashTable
    • Tree
    • 트라이(Trie)
    • 선형 구조 vs 비선형 구조
    • 연결 리스트(linked-list)
    • Queue
    • Graph
    • Heap
    • Stack
  • web
    • 웹 브라우저의 동작 원리
    • Basic
    • Webpack이란?
    • rendering
    • npm
    • babel
  • graphQL
    • Query
    • Mutation
    • Introduction
  • algorithm
    • big-o
    • 버블 정렬(bubble sort)
    • 힙 정렬(heap sort)
    • 선택 정렬(selection sort)
    • 퀵 정렬(quick sort)
    • 백트래킹 알고리즘
    • 삽입 정렬(insertion sort)
    • 계수 정렬(counting sort)
    • 다엑스트라 알고리즘
    • 이진 탐색
    • 합병 정렬(merge-sort)
    • 동적 계획법(Dynamic programming)
  • web-security
    • XSS(Cross Site Scripting)
    • CSRF(Cross-site request forgery)
    • Tabnabbing
  • javaScript
    • dom
    • 자바스크립트 성능 최적화
    • Event Loop
    • Snippets
    • javaScript
  • programming-paradigm
    • Object Oriented Programming
    • 함수형 프로그래밍
    • 구조적 프로그래밍
  • computer-science
    • Process vs Thread
    • 비트 연산자
    • 그레이 코드
  • vue
    • Vue
  • design-pattern
    • MVP pattern
    • Flux
    • 아토믹 디자인
    • MVVM pattern
    • MVC pattern
  • css
    • css
    • Grid
    • css-methodologies
    • FlexBox
  • html
    • html
  • regExp
    • regExp
  • git
    • Git-flow
Powered by GitBook
On this page

Was this helpful?

  1. algorithm

버블 정렬(bubble sort)

오름차순 정렬 기준으로 첫 번째 값과 두 번째 값을, 두 번째 값과 세 번째 값을, ..., (마지막 - 1)번째 값과 마지막 값을 비교하여 큰 값을 뒤로 보내면서 배열을 정렬한다

처음 정렬 한뒤 가장 큰 값이 맨 뒤로 이동하므로 그다음 정렬에서는 맨 끝에 있는 값은 정렬에서 제외되고, 두 번째 정렬을 한뒤 끝에서 두 번째 값은 정렬에서 제외된다. 이렇게 끝까지 반복한다

시간 복잡도: O(n²)

공간 복잡도: O(1)

// 오름차순
function ascBubbleSort(array) {
  // 순차적으로 비교하기 위한 반복문
  for (let i = 0; i < array.length - 1; i++) {
    // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문
    for (let j = 0; j < array.length - i; j++) {
      // array[j]값이 arrat[j + 1]값보다 크면 변경
      if (array[j] > array[j + 1]) {
        // 두 수를 서로 바꿔줌
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

// 내림차순
function descBubbleSort(array) {
  // 순차적으로 비교하기 위한 반복문
  for (let i = 0; i < array.length - 1; i++) {
    // 끝까지 돌았을 때 다시 처음부터 비교하기 위한 반복문
    for (let j = 0; j < array.length - 1 - i; j++) {
      // array[j]값이 arrat[j + 1]값보다 크면 변경
      if (array[j] < array[j + 1]) {
        // 두 수를 서로 바꿔줌
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

ascBubbleSort([7, 1, 5, 4, 6, 3, 2, 8]); // [ 1, 2, 3, 4, 5, 6, 7, 8 ]
descBubbleSort([7, 1, 5, 4, 6, 3, 2, 8]); // [ 8, 7, 6, 5, 4, 3, 2, 1 ]
Previousbig-oNext힙 정렬(heap sort)

Last updated 5 years ago

Was this helpful?