본문 바로가기 메뉴 바로가기

덕's IT Story

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

덕's IT Story

검색하기 폼
  • 분류 전체보기 (198)
    • IT 이야기 (31)
      • 그 외 (15)
      • 대외활동 소식 (9)
      • 컴퓨터 지식 (7)
    • 클라우드&오픈스택 (8)
      • 클라우드 (2)
      • 오픈스택 (6)
    • 프로그래밍 (86)
      • C/C++ (1)
      • 자료구조&알고리즘 (11)
      • 다음API (6)
      • OpenCV (2)
      • RabbitMQ (6)
      • Git&GitHub (3)
      • Web (2)
      • 자바스크립트 (12)
      • Spring (7)
      • Java (36)
    • Ruby&Rails (21)
      • Rails (16)
      • Gem (5)
    • OS (20)
      • 리눅스&우분투 (12)
      • CentOS (5)
      • 안드로이드 (3)
    • 해킹&보안 (5)
      • 무선해킹 (2)
      • 시스템해킹 (3)
  • 방명록

시간복잡도 (2)
퀵정렬(Quick Sort)

퀵정렬(Quick Sort)는 평균적으로 좋은 성능을 가져 현장에서 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우(Worst-Case) Θ(n^2)의 시간복잡도를 가져 Θ(nlogn)의 시간복잡도를 가지는 병합정렬, 힙정렬보다 성능이 안좋아보일 수 있으나 평균적인 성능은 어떤 정렬에도 뒤떨어지지 않는다. 퀵정렬(Quick Sort)는 배열의 한 원소를 기준(피봇, pivot)으로 삼아 피봇보다 작은 수들은 피봇의 앞으로, 피봇보다 큰 수들은 피봇의 뒤로 보낸다. 정렬되지 않은 피봇의 좌우는 재귀적으로 문제를 해결하여 배열 전체가 정렬이 되도록 한다. 예를 들어 설명하면 다음과 같다. 이 예는 배열의 젤 뒷원소를 피봇으로 삼아 퀵정렬(Quick Sort)를 수행하는 경우이다. 피봇인 15보다 작은 수들..

프로그래밍/자료구조&알고리즘 2014. 4. 23. 12:09
버블정렬(Bubble Sort)

버블정렬(Bubble Sort)도 선택정렬(Selection Sort)처럼 제일 큰 원소를 옮기는 작업을 반복하는 정렬이다. 다만, 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다. 선택정렬(Selection Sort) 이란 ? 클릭 선택정렬(Selection Sort) 버블정렬(Bubble Sort)는 위의 예제 처럼 배열의 처음 인덱스부터 n-1 인덱스까지 이동하면서 인접하는 다음 인덱스의 원소와 크기를 비교하여 순서를 바로 잡아 나간다. 이 과정을 반복하게 되면 배열의 맨끝에는 배열의 가장 큰 원소가 자리하게 된다. 그러면 배열의 제일 마지막을 잊어버리고 이를 반복하게 되면 배열이 차례대로 끝에서 부터 내림차순으로 정렬되게 된다. 버블정렬(Bubble Sort)의 슈도코드는 다음과 같다. 버블..

프로그래밍/자료구조&알고리즘 2014. 4. 22. 20:03
이전 1 다음
이전 다음
최근에 올라온 글
  • [책 리뷰] 자바 최적화 (Optimizing J⋯
  • Spring Webflux + JDBC(혹은 bl⋯
  • [macOS Mojave] Evernote (혹은⋯
  • spring-boot-starter-webflux⋯
TAG
  • 컴퓨터
  • ubuntu
  • install
  • rabbitmq
  • Java
  • 자료구조
  • IT
  • CSS
  • codecademy
  • html
  • javascript
  • 우분투
  • IceHouse
  • ruby on rails
  • gem
  • 티스토리 초대장
  • 다음지도 API
  • OpenStack
  • 다음지도
  • ruby
  • 리눅스
  • 클라우드 컴퓨팅
  • Rails
  • 다음
  • 알고리즘
  • Message Queue
  • 이펙티브 자바
  • 프로그래밍
  • 오픈스택
  • 웹프로그래밍
more
글 보관함
  • 2019/06 (1)
  • 2018/12 (2)
  • 2018/11 (2)
  • 2018/10 (1)
  • 2018/07 (2)
Total
695,667
Today
68
Yesterday
235

Copyright ⓒ 2018 kkd927. All rights reserved.

티스토리툴바