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

풀풀풀

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

풀풀풀

검색하기 폼
  • 분류 전체보기 (60)
    • coding test (4)
      • 백준 (3)
      • swea (0)
    • algorithm & data structure (6)
    • programming language (10)
      • c++ (9)
      • java (1)
    • android (6)
    • spring (5)
    • windows (7)
    • interview (16)
      • OS (6)
      • Network (8)
    • etc (6)
  • 방명록

정렬 알고리즘 (2)
[알고리즘] 힙정렬(Heap Sort)

힙 정렬 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 1. 정렬해야할 n개의 요소들로 최대힙(완전 이진 트리 형태)를 만든다. 내림차순 기준 정렬2. 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.3. 삭제되는 요소들(최댓값부터 삭제)는 값이 감소되는 순서로 정렬되게 된다. - 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬방식이다.- 힙은 1차원 배열로 쉽게 구현될 수 있다.- 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값이나 작은 값을 구할 때, 최대 k만큼 떨어진 요소들을 정렬할 때 이다. 시간 복잡도최선/최악/평균 모두 O(n..

algorithm & data structure 2018. 10. 25. 22:07
[알고리즘] 퀵정렬(Quick Sort)

퀵 정렬 퀵소트는 divide and conquer 방법을 통해 정렬한다. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피봇이라고 한다.피봇 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피봇 뒤에는 피봇보다 값이 큰 모든 원소들이 오도록 피봇을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피봇은 더 이상 움직이지 않는다.분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.[ 위키백과 참조 ] 시간 복잡도 ( T(n) 은 n의 리스트를 정렬하는데 걸리는 시간 ) 평균적으로 O(nlog n) 의 시간복잡도를 갖는다. 최선의 경우 : O(nlog n) 최악의 경우 ..

algorithm & data structure 2018. 10. 25. 11:42
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • [JPA] JPA 장점/사용하는⋯
  • [Spring boot] Controller⋯
  • [Spring boot] 스프링부트⋯
  • [Spring boot] IntelliJ -⋯
최근에 달린 댓글
  • 굿잡
  • 안녕하세요. 우연히 검색하다⋯
  • seq number가 랜덤한 이유에⋯
  • 우아 간단 명료하게 딱딱 들⋯
Total
77,505
Today
28
Yesterday
88
링크
TAG
  • HTTP
  • handshake
  • frameLayout
  • 퀵정렬
  • LinearLayout
  • 스프링부트
  • 스프링
  • 이진탐색트리
  • 정렬 알고리즘
  • 백준
  • OS
  • layout
  • 안드로이드
  • adapter
  • DATABASE
  • ConstraintLayout
  • debug
  • BOJ
  • C
  • 윈도우
  • 운영체제
  • listview
  • Android
  • WinDbg
  • 네트워크
  • C++
  • 알고리즘
  • 백준알고리즘
  • RelativeLayout
  • windows
more
«   2022/05   »
일 월 화 수 목 금 토
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
글 보관함
  • 2021/01 (4)
  • 2020/12 (1)
  • 2020/06 (4)
  • 2020/04 (1)

Blog is powered by Tistory / Designed by Tistory