[Python Algorism] 6-2. 정렬 알고리즘

DO IT 자료구조와 함께 배우는 알고리즘 입문 파이썬책을 공부하는 취준생으로써 해당 책의 공부 내용을 정리하고 다른 입문자들도 쉽게 이해 하도록 공유하고자 만든 페이지입니다. 모든 문제의 저작권은 관련 저작자에게 있으며 문제가 됐을 시 삭제하겠습니다. 감사합니다

---

P 255 퀵정렬

퀵 정렬은 일반적으로 사용되는 아주 빠른 정렬 알고리즘입니다. 앞에서 쉘정렬은 간격을 통해 그룹을 나누고 정렬을 진행했다면 퀵 정렬은 pivot(기준점)을 정해서 분리합니다. 피벗은 임의로 선택할 수 있으며 나눈 그룹 어디든 넣어도 상관없습니다. 피벗을 매번 설정해서 계속 나눠서 모든 데이터가 정렬이 될 때까지 이와 같은 과정을 반복해줍니다.

 

퀵 정렬을 구현할 때는 pivot(기준점)을 잡고 pl(왼쪽점)부터 pivot 까지 이동하여 큰 값은 오른쪽으로 넘겨주고 반대로 pr(오른쪽점)부터 pivot까지 이동하여 작은 값은 왼쪽으로 넘겨줍니다. 순간 하나만 있어도 되지 않을까? 했지만 안된다는 걸 알았습니다.. ㅎㅎ

 

 

비재귀적인 방법과 원소가 9개 이하인 단순 정렬 방법은 그냥 코드를 따라했기 때문에 첨부하지 않겠습니당

책을 참고하시면 더 좋을 것 같아요~

 

 

P 277 병합정렬

병합 정렬은 배열의 앞 부분과 뒷부분의 두 구릅으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다

중앙을 기준으로 왼쪽 / 오른쪽 나누었습니다

 

 

left 첫번째원소 - right 첫번째원소... 끝까지 비교하여 새로운 리스트에 추가하고

남은 원소들을 모두 결과에 추가합니다

 

P 286 힙정렬

힙 정렬은 부모의 값이 자식의 값보다 항상 같거나 크다 를 만족하는 완전 이진 트리의 특성을 이용하여 정렬하는 알고리즘입니다. 힙의 루트는 최댓값임을 알 수 있고, 형제 관계의 대소 관계는 일정하지 않을 수 있습니다.

힙 정렬은 선택 정렬을 응용한 알고리즘으로 데이터의 개수를 새어 최댓값을 뽑아내고 다시 남은 원소 중에서 최댓값을 구하며 남은 원소로 구성한 트리들도 힙이 되도록 재구성하게 해줍니다. 교재 289p를 참고하면 더 자세히 알 수 있습니다

 

왼쪽 자식과 오른쪽 자식을 비교하며 가장 큰 최댓값을 찾아줍니다. 

 

힙정렬 함수를 만들어줍니다

 

P297  도수정렬

 

도수정렬은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘입니다

 

 

 

Chap6.py

0.01MB