CH10-2복잡하지만 효율적인 정렬 알고리즘(11)

10-2. 복잡하지만 효율적인 정렬 알고리즘 ⑪

이번시간에는 퀵소트함수 실행흐름에 대해 설명하겠다.

파티션과 퀵 소트에서 pivot의 의미는 달라진다. 파티션의 반환값을 받는 피봇은 ‘중간값’이라는 의미가 더 가깝다. 이름을 mid이런게 아니라 pivot으로 한건… 파티션의 반환값이 pivot이 된다는 의미를 전달하기 위함이었음. 재귀적으로 진행되는 성격을 강조하려고

여기서 이제 탈출 조건에 대해 알아보자. left와 right와 가까워진다는건 어떤 의미인가??

left와 right가 실제로 이동한다는게 아니다. 새로운 퀵 소트를 재귀적으로 호출할때마다 새로운 left와 right가 선언될 뿐이다.

재귀적으로 호출하다가 어느순간 더이상 정렬할 필요가 없을때는… left와 right가 같아지는 것도 아니고 left와 right가 역전된다.

전 시간에도 내가 언급했지만… -1하고 +1하기 때문에 어떤 시행에서는 서로 역전된다.

• 퀵소트의 흐름을 보니… 흠 이거 들었던 강의네

복잡하지만 효율적인 정렬 알고리즘(12)

10-2. 복잡하지만 효율적인 정렬 알고리즘 ⑫

이번시간에는 퀵 정렬에서 피벗 선택에 관한 논의를 진행하겠다.

결론은 피벗은 가급적 중간에 해당되는 값이 선택되어야 좋은 성능을 보인다는 것임.

• 이건 내가 테스트하면서도 느낀 것임.. 피벗으로 극단적인 값을 선택하면 이렇게 된다.

0을 피벗으로 선택하니… 그냥 자기 자신만 그자리에 정렬되고 자기 오른쪽에 오는 값들은 전혀 정렬되지 않았다.