인프런 커뮤니티 질문&답변

com4011554님의 프로필 이미지

작성한 질문수

Do it! 알고리즘 코딩테스트 with JAVA

퀵 정렬 (Quick Sort)

퀵정렬 설명시 오류

해결된 질문

23.04.02 19:20 작성

·

586

·

수정됨

0

퀵 정렬을 설명할 때 start와 end가 만나면 swap이 아니라 start와 end값을 비교해서 적정 위치에 넣어주는것 아니었나요?

답변 1

0

하루코딩님의 프로필 이미지
하루코딩
지식공유자

2023. 04. 04. 20:18

안녕하세요 반갑습니다.

음 어떤 부분으로 말씀하신것인지는 제가 정확하게 이해하지는 못하였는데 -

말씀해주신 것이 맞습니다. ^^ ( 데이터와 pivot 값을 비교하여 pivot을 중심으로 두개의 집합으로 쪼개준다)

예를들어 10 64 15 19 20 100 59 14 88 이 데이터이고 피벗이 50일 경우 오름차순 정렬이라고 할때

왼쪽에서부터 탐색하여 피벗보다 큰수가 나오면 멈추고 선택하여 줍니다. (64 선택)

오른쪽부터 탐색하여 피벗보다 작은수가 나오면 멈추고 선택하여 줍니다. (14 선택)

두 데이터를 스왑하여 줍니다.

10 14 15 19 20 100 59 64 88

그다음을 보면 왼쪽에서 계속 탐색하여 피벗보다 큰수는 100

오른쪽에서도 계속 탐색하여 피번보다 작은 수는 20

그런데 해당 상태에서는 왼쪽 index와 오른쪽 index가 서로 만났(교차)기 때문에 더 이상 진행하지않고

이 둘 사이에 pivot을 넣고 두개의 집합으로 나누어집니다.

왼쪽 집합 => 10 14 15 19 20

오른쪽 집합 => 100 59 64 88

그럼 또 각각의 집합안에서 적절한 pivot을 선택하고 반복을 해주는 방식이라고 생각해주시면 될 것 같습니다. ^^

 

감사합니다. 즐거운 저녁 되세요 :0