요즘 퀵정렬 공부하는데 이게 왜 정렬이 되는지 아직도 이해가 안됨...
피벗 기준으로 계속 나눠서 정렬한다는 그 느낌은 알겠는데
left랑 right 인덱스를 막 쪼이면서 피벗 위치를 찾는 그 과정이 아무리 생각해도 노근본같음;;
힙정렬은 부모랑 자식 인덱스간의 규칙이 명확하고 언제까지 뭘 해야된다는게 딱 정해져있는데
얘는 직관적이지도 않고 그냥 될때까지 한다는 식으로 배째는거같고
다른사람 코드좀 참고하려고 구글링해봐도 사람마다 피벗도 달라 파티션 방식도 달라
심지어 기본적인 중복 처리도 안한 코드가 대다수임...
진짜 이거땜시 ㅈㄴ골때리는데 그냥 이론만 대충 알고 넘어가도 무방함?
ㅇㅇ 더 호어 퀵소트 로무토 퀵소트가 있다는 것 정도만 알아도 되지 않을까 싶은데
글켓지? 어차피 직접 짜야될땐 합병정렬쓰면 되니까
상식적으로 보면 그냥 pivot보다 작은 애들 왼쪽으로 빼놓고 큰 애들 오른쪽으로 빼놓고 가운데에 pivot 넣어서 합치면 된다고 생각할 수 있지만 데이터를 빼내서 재배열하려면 새로운 메모리 공간이 필요하게 된다는 문제가 있음. 따라서 주어진 배열 공간에서 어떻게든 해결을 하려고 생각을 해본 결과 pivot보다 작은 애들을 왼쪽으로 밀어넣고, 큰 애들은 오른쪽으로 밀어넣어야 한다고 생각하는 거지? left와 right 인덱스는 각각의 인덱스의 값이 왼쪽에 들어가야 할지 오른쪽에 들어가야 할지 판별하기 위해 설정을 한 거고, 만약 left의 값이 pivot보다 크다면 오른쪽으로 가야 할 테니까, 오른쪽 거랑 교환을 하는거지. 결과적으로 보면 left 왼쪽은 모두 pivot보다 작고, right 오른쪽은 크게됨
나도 일단 호어방식으로 구현해보고 정상 작동되는거 까지 확인했는데 솔직히 아직도 받아들이질 못하겠음... 첫 파티션에서는 대충 이해가 되는데 계속 반복해도 과연 제대로 될까하는 의구심이 들어서 직접 연필로 그려보면서 눈으로 보기도 했는데 그냥 되는구나 싶지 이게 왜 되는건지는 모르겠으니 길이가 2가 되고 1이 돼도 똑같이 작동할지, 중복이 가득찬 배열에서도 과연 제대로 될지 의심만 계속 쌓이는 상태임... 그냥 하나의 방식으로 받아들이면 되는건데 내가 너무 호기심이 많은거같기도 함
어떤 수는 1)pivot보다 작거나 2)pivot보다 크거나 3)pivot과 같을 수 있음 만약 pivot보다 작은 수와 pivot보다 큰 수를 각각 pivot의 왼쪽 오른쪽에 분리하여 놓으면 pivot의 위치는 그곳으로 "확정"인 거지? pivot과 같은 경우에는 왼쪽으로 가든 오른쪽으로 가든 상관없는 것도 자명함 왼쪽에 놓든 오른쪽에 놓든 pivot과 같은 값들은 전부 연속되어 있기 때문에 그 중 한 pivot의 위치를 pivot으로 잡아도 그곳으로 "확정"할 수 있음 참고로 이래서 퀵 소트는 unstable함
퀵은 보자마자 이해되는 직관적인 소트인데
원래 그런 소트야 될때까지 하니까 최악이 O(n^2)인 거고 중복 처리 안 하니까 unstable인 거임
어떻게 분할하던, 그 분할한 모든 부분은 결국 n = 2나 n = 3 같은 기저 케이스로 쪼개질것이고, 그렇게 쪼개진 부분에서는 완벽하게 정렬된다는 것은 당연하겠지. 그런 조각 조각들을 뭉텅이로 하나씩 합쳐나가면 당연히 전체가 정렬됨. 정말 직관적으로 잘 이해되는 합병 정렬이랑 바텀 업이냐 탑 다운이냐 차이만 있다고 봄