[Python]정렬 백준 2751

   문제

   https://www.acmicpc.net/problem/2751

이전 문제와 달리 숫자의 범위가 매우 커졌다.

기본적인 선택정렬이나 버블정렬로는 해결 되지 않을것이다.

퀵 정렬이나 힙정렬 혹은 병합정렬을 이용해 보자.

알고리즘 선택할때 참조

http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html

퀵정렬에 대한 설명

https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC

퀵정렬 피봇선택을 통한 개선

https://www.it-swarm.net/ko/python/python%EC%9D%84-%EC%82%AC%EC%9A%A9%ED%95%9C-%ED%80%B5-%EC%A0%95%EB%A0%AC/1040341322/

이론상으론 충분히 이해하고 있다고 생각해 빠르게 작성할수 있을줄 알았는데 의외로

 잦은실수가 많았다.

퀵정렬은 피벗값을 기준으로 나누어 정렬하는 방법이다.

코드가 많아 질거같아 파일로 첨부했다.

QuickSort.py

퀵정렬은 O(nlogn)의 평균속도를 가지지만 최악의 경우 O(n^2)의 속도를 가진다.

코드는 두가지 방법으로 작성하였는데 첫째값을 피벗으로 선택하여 실행하였을때와 중간

값을 피벗으로 선택하였을때로 나뉜다. 피벗을 선택하는 방법은 여러가지가 있으며 첫번

째 값을 피벗으로 선택하였을때는 시간초과가 떳으며 중간값을 피벗으로 선택했을때는 성

공하는 모습을 보였다.

퀵정렬외에도 힙정렬과 합병정렬도 구현해 봤다.

힙정렬의 경우에는 힙구조를 만든후 값을 하나씩 고정시키는 방식이다.

힙 구조

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

최대힙을 구성하고 0번째 인자(최대값)를 마지막 인자와 바꾸어 준다.

마지막 인자를 제외하고 다시 최대힙구조를 만든다. 이때 logN번만 수행하면 다시 최대힙

 구조가 만들어지는것을 알수있다.이렇게 최대힙구조가 다시 만들어지면 다시 0번째 인자

와 마지막에서 두번재 인자를 바꾸어준다, 이런식으로 끝까지 반복해준다.

HeapSort.py

힙정렬 역시 시간초과가 떳고 pypy3으로 제출했을때는 성공하는 모습을 보였다.

마지막을 병합정렬

사실 병합정렬이 일반적으로 제일 이해하기 쉽다.

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

병합정렬의 경우 추가로 배열크기만큼의 메모리가 하나 더 필요하다.

병합정렬의 경우 한번에 성공하는 모습을 보여주었다.

MergeSort.py

세가지 정렬 모두 처음 구현한다면 쉽지 않을것이다.

하지만 정렬중에서는 기본중에 속하고 이 정도는 바로 구현할수 있어야한다.

그리고 구현하는것 만큼이나 경우에 따라 어떤 알고리즘을 선택할 것인지도 알아야 

할것이다.

복습하는 과정이었지만 다시한번씩 구현해보아야겠다.