퀵정렬4 [Java API] 정렬 메서드(sort) 종류와 차이점 https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A0%AC-%EC%A0%95%EB%A6%AC-%EB%B0%8F-%EC%84%A0%ED%83%9D-%EB%A7%A4%EB%89%B4%EC%96%BC [알고리즘] 정렬 정리 및 선택 매뉴얼ㅇ버블정렬 - 실무에서는 아예 사용하지 말자 "제자리 + stable" O(n^2) ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현) "제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합 ㅇ삽입정렬: 우선순위 큐claremont.tistory.com먼저 위 포스트를 통해 정렬에 대한 기본적인 공부를 하고 오는 것을 추천한다 자바에서 Primitive T.. 2024. 10. 29. [알고리즘] ep1-6+) 퀵정렬의 다양한 버전 (출력형식)Limit 결정적1 결정적3 무작위1 무작위31 X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 100 X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 500 X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX 1000 X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX X.XXXXXXXX(참고: X.XXXXXXXX는 측정된 cputime in milliseconds). [주요 함수들의 설계 가이드라인]global integer n = 100000global array Limits = {1, 100, .. 2024. 7. 10. [알고리즘] 정렬 알고리즘 선택 매뉴얼 ㅇ버블정렬 - 실무에서는 아예 사용하면 안된다"제자리 + stable" O(n^2) ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)"제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합 ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)"제자리 + stable" O(n^2): 느리다 - 소규모 입력에 적합 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ ㅇ힙정렬: 우선순위 큐 (힙으로 구현)"제자리 + unstable" O(nlog(n)): 빠르다 - 대규모 입력에 적합 ㅇ병합정렬: 분할통치"제자리 X + stable" O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합 ㅇ퀵정렬: 분할통치"제자리 + unstable".. 2024. 7. 7. [알고리즘] ep1-6) 퀵정렬(quick sort) ㅇ퀵정렬(quick sort): 분할통치법에 기초한 정렬 알고리즘"제자리 + unstable" O(nlog(n))※ 최악의 시간 복잡도: O(n^2) (이미 정렬된 리스트에서 항상 최악의 피벗을 선택하는 경우) 이름에서 알 수 있듯이 복잡하지만 매우 효율적인 알고리즘이다 일각에서는 이렇게 지칭한다 '살아있는 레전드' *피벗(pivot): 기준점1. 피벗을 기준점으로 잡는다2. 피벗보다 작으면 왼쪽에, 피벗보다 크면 오른쪽에 둔다3. 왼쪽과 오른쪽을 각각 정복한다 [분할 함수(partition 함수) 과정] 다양한 피봇 선정 방식 -> 다양한 퀵소트 버전 (참고)퀵정렬 트리: quickSort의 실행을 이진트리로 보이기이진트리의 각 노드는 quickSort의 재귀호출을 표현하며 다음을 저장- 실행.. 2024. 7. 7. 이전 1 다음
