퀵정렬2 Quick Sort - 퀵 정렬과 코드 앞서 다른 정렬들은 영어부분을 번역해서 "ㅁㅁ정렬" 이렇게 부르던데 퀵소트는 그냥 퀵정렬이라고 부르는부분이 약간 웃기다. 퀵정렬은 분할 정복을 사용한다. 1. 배열의 끝에 있는 수를 Pivot으로 설정한다. (기준값) 그리고 맨 처음에 Pivot보다 작은 수를 세기위한 low와 (오름차순) 차례 차례 수를 확인하고 비교하기위한 ptr 을 둔다. 2. ptr에 있는 값과 Pivot값을 비교한다. 오름차순의 경우 ptr값이 더 작으면 low값을 뒤로 한칸 옮긴다. (++ 그리고 이때 만약 ptr값과 low값이 다르면 두 값을 Swap한다) 비교가 끝나면 ptr을 한 칸 뒤로 옮긴다. 3. 계속해서 ptr과 Pivot값을 비교한다. ptr에 있는 값이 더 크다면 low는 그대로 두고 ptr을 뒤로 옮긴다. .. 2022. 7. 6. [알고리즘] 퀵 정렬 | Quick Sort | C++코드 해석 병합정렬(Merge Sort)과 함께 기본 정렬알고리즘인 퀵정렬. 병합정렬이 수열을 반으로 쪼개가며 정렬했다면, 퀵정렬은 기준을 두고 기준보다 작은값들, 기준보다 큰값들로 쪼개가며 정렬한다. 병합정렬은 따로 정렬해둔 값을 저장해둘 메모리공간이 필요했다면 퀵정렬은 따로 메모리공간이 필요하지 않다. 하지만 병합정렬은 언제나 시간복잡도가 일정한 반면 퀵정렬은 잡히는 기준에 따라 시간복잡도가 O(n^2)까지 올라갈수있다고한다. 코드는 이러하다. pivot이 기준 값이 되고 i가 pivot의 자리를 찾아준 다고 생각하면된다. 이해하기 쉽게 예시를들어 그림으로 설명해보자면 이런식이다. 2020. 2. 20. 이전 1 다음
