반응형 SMALL 자료구조 & 알고리즘1 퀵 정렬(1) : 구간 시작점 다음 수를 피벗으로 설정 - 가장 빠른 정렬 알고리즘 중 하나 - 피벗을 기준으로 배열을 더이상 분해할 수 없을 때까지(그룹 요소의 개수가 1개인 경우) 분해한다. - 평균 시간 복잡도 : O(n logn) - 최악 시간 복잡도 : O(n^2) ex> 이미 정렬이 되어 있는 경우, 매번 단 하나의 요소와 나머지 요소로 나누어지는 경우 -> 이 때는 삽입정렬이 더 빠르다. 퀵 정렬 예시 start, end : 구간의 시작점과 끝점 pivot: 그룹을 나누는 기준점(인덱스가 아닌 들어있는 값임) left, right: 인덱스 값 1. 가장 왼쪽에 있는 수(5)를 피벗으로 지정한다. 2. left부터 오른쪽으로 가면서 피벗보다 큰 값을 가진 인덱스 를 찾을 때까지 left의 값을 증가시킨다. ex> 7 3. right부터 왼쪽으로 가.. 2020. 9. 25. 이전 1 다음 반응형 LIST
