'Quicksort' 태그의 글 목록

퀵정렬이란? "빠른" 정렬 알고리즘. 피벗을 기준으로 큰 값과 작은값을 서로 비교하고 교체하는 정렬. 리스트 가운데서 피벗이라고 하는 하나의 원소를 고름 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 함. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복하며 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복됨 값을 서로 교체하는데 N번, (엇갈렸을때) 전체 원소 나누는데 평균 logN번이 소요되므로 평균적으로 O(NlogN)의 시간복잡도를 가짐 최악의 경우에는 O(N²)번의 비교를 수행함 퀵정렬은 완전..

컴퓨터공학 2019. 10. 11. 00:42

이전 1 다음