Elearning CodePath – CTP Online Judge

🎯 Mục tiêu bài học

Hiểu cơ chế sắp xếp chia để trị: Merge Sort và Quick Sort.
Phân tích độ phức tạp O(n log n).

📘 1. Merge Sort

Ý tưởng: chia đôi mảng → sắp xếp từng nửa → trộn hai nửa đã sắp xếp.

Python

def merge_sort(a):
    if len(a) <= 1: return a
    mid = len(a)//2
    L = merge_sort(a[:mid])
    R = merge_sort(a[mid:])
    res=[]; i=j=0
    while i



C++
#include 
using namespace std;
void merge(vector& a, int l, int m, int r){
    vector L(a.begin()+l, a.begin()+m+1);
    vector R(a.begin()+m+1, a.begin()+r+1);
    int i=0,j=0,k=l;
    while(i& a,int l,int r){
    if(l>=r)return;
    int m=(l+r)/2;
    mergeSort(a,l,m);
    mergeSort(a,m+1,r);
    merge(a,l,m,r);
}
int main(){
    int n;cin>>n;
    vector a(n);
    for(int i=0;i>a[i];
    mergeSort(a,0,n-1);
    for(int x:a)cout<




📘 2. Quick Sort
Ý tưởng: chọn một phần tử (pivot), chia mảng thành hai phần nhỏ hơn và lớn hơn pivot, rồi sắp xếp đệ quy.

Python
def quick_sort(a):
    if len(a) <= 1: return a
    pivot = a[0]
    less = [x for x in a[1:] if x <= pivot]
    greater = [x for x in a[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)
print(*quick_sort(list(map(int, input().split()))))



🧩 Bài tập luyện tập

  Cài đặt Merge Sort để sắp xếp mảng giảm dần.
  Cài đặt Quick Sort không dùng list comprehension.
  So sánh thời gian Merge Sort và Bubble Sort với n = 10⁴.



  💡 Xem lời giải mẫu
  # Python
import random, time

def bubble(a):
    for i in range(len(a)-1):
        for j in range(len(a)-i-1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]

def merge_sort(a):
    if len(a)<=1:return a
    mid=len(a)//2
    L=merge_sort(a[:mid])
    R=merge_sort(a[mid:])
    res=[];i=j=0
    while i