퀵정렬 질문

안녕하세요. 반갑습니다.

말씀하신 부분이 설명이 혼선을 드린 부분이 있어서 답변드립니다.

이해하신 것이 모두 맞는 말씀인데, 제가 설명시 약간 혼합하여 말씀드린 부분이 있는 것 같습니다.

보통 배열에서는 설명드린것과 같이 중간에 삽입을 할 경우에는 이후 데이터를 모두 뒤로 한 칸씩 미뤄야 하는

로직이 필요하고 시간복잡도 이슈가 있기 때문에 swap을 더 일반적으로 사용합니다.

swap을 사용하는 부분은 19번 문제 코드를 보면 이해가 가능하실 것 같습니다.

다만 swap을 사용할 경우 pivot을 오른쪽 끝 data로 지정하였는지

왼쪽 끝 data로 지정하였는지에 따라 약간 로직을 생각해 보아야합니다.

이 경우는 오른쪽을 pivot으로 지정 하였기 때문에 두 그룹 중 큰 수 집합의 첫번째 수인 32와 pivot 값을 swap해야겠다고 제가 인지하고 말씀을 드렸네요. 첫번째 정렬과 달라서 충분이 혼선을 드릴 수 있었을 것 같습니다.

첫번째 정렬도 비슷하게 한다고 하면

42 32 24 5 15 60 90 45 의 상태에서

두 무리는

42 32 24 5 15 | 60 90 로 분리되고 pivot은 45입니다. 이때 pivot data의 위치가 오른쪽에 있기 때문에

큰 쪽 무리의 첫번째 값인 60과 swap을 진행하여 주면

42 32 24 5 15 45 90 60 이 되고 45를 기준으로 양쪽이 나누어 지게 됩니다.

좋은 질문 감사드리고 이부분은 제가 유튜브 고정 댓글로 부연 설명 및 책의 다음 쇄에도 추가 설명으로 기재해 두도록 하겠습니다.

감사하합니다. 좋은하루 되세요 🙂