안녕하십니까, 홍익대학교 소프트웨어융합학과 19학번 권덕재입니다.

알고리즘 및 실습 과목의 설계과제 1에 대한 영상을 시작하겠습니다.

설계과제 1의 내용은 다음과 같습니다.

반복문을 사용한 Iterative Quicksort

자기호출 방식을 사용한 Recursive Quicksort

pviot 요소를 랜덤으로 정하는 방식을 사용한 Randomized Quicksort

이렇게 3가지 버전의 퀵정렬을 구현하고 입력 데이터에 대해 각 알고리즘의 비교 연산 횟수를 출력, 비교 연산 횟수의 평균을 그래프로 나타내어 비교합니다.

입력 데이터는 10의 2승, 10의 4승 개의 난수를 30개씩 만들어서 테스트했고 영상의 마지막에 10의 6승까지 테스트해볼 예정입니다.

먼저 퀵정렬에 대해 설명하겠습니다.

퀵정렬은 입력 배열에서 임의의 원소 pivot을 고른 뒤 pivot보다 작은값을 왼쪽으로, 큰 값을 오른쪽으로 이동시켜 pivot의 위치를 고정시켜주는 partition 메서드를 재귀적으로 실행하여 정렬하는 알고리즘입니다.

다음은 코드 설명입니다.

입력 데이터에 난수를 입력받고 Randomized Quicksort에서 pivot의 위치를 랜덤으로 잡기 위해 random을,

결과값을 DataFrame 형태로 저장하여 깔끔하게 출력하기 위해 pandas를,

최종 결과를 그래프로 보기 좋게 출력하기 위해 matplotlib(맷 플롯 립) 의 pyplot(파이 플롯) class를 import 했습니다.

또한 Mac OS 환경에서 폰트가 깨지는 것을 방지하기 위해 os를 import하고 다음과 같은 명령어를 실행했습니다.

QuickSort 클래스입니다.

3가지 버전의 퀵정렬이 구현되어있는 클래스로 객체를 생성할 때 비교 연산의 횟수를 의미하는 self.count 변수를 0으로 초기화합니다.

다음은 각 퀵정렬을 실행할 때 필요한 메서드들에 대한 설명입니다.

initCount 메서드는 self.count를 다시 0으로 초기화하는 메서드입니다. 각 퀵정렬의 비교 연산의 횟수를 구한 후에 사용됩니다.

plusCount 메서드는 비교 연산이 발생할 때 비교 횟수만큼 self.count에 더하는 메서드입니다.