알고리즘 스터디 5일차

목차

1. 퀵 정렬

2. 퀵 정렬 실전 문제

3. 병합 정렬

4. 병합 정렬 실전 문제

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

1. 퀵 정렬

기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬

평균 시간복잡도 : O(nlogn)

최악 시간복잡도 : O(n²)

설명 : 기준값을 피벗으로 두고 남은 범위에서 한쪽은 큰값, 한쪽은 작은값으로 swap하며 반복진행 후 마지막 남은 값을 기준에 맞게 피벗과 swap하는 과정을 반복

 

2. 퀵 정렬 실전 문제

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

11004번: K번째 수

1

 

3. 병합 정렬

분할정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합침

시간복잡도 : O(nlogn)

설명 : 그룹으로 나눠 각 그룹마다 정렬진행 후 가까운 그룹끼리 다시 그룹을 만들어 정렬하는 과정을 반복 (예를들어 오름차순 정렬하는 경우 정렬된 두 그룹끼리 병합하는 과정은 두 그룹중 작은값을 저장하는 과정을 반복하는 방식으로 병합)

 

 

4. 병합 정렬 실전 문제

4.1

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

1517번: 버블 소트

2

 

 

 

4.2

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

2751번: 수 정렬하기 2

3