Partition trong QuickSort, giữ nguyên thứ tự các phần tử?

#1

Chuyện là em thường sử dụng Quicksort trong cùng 1 hàm, hôm nay buồn buồn dạo trên hackerrank, trong phần Quicksort, nó yêu cầu làm partition, mà thứ tự các phần tử giữ nguyên (thứ tự trước sau ấy), em bị vướng chỗ này, không biết làm sao, mọi người cho em ý tưởng với. Cho sẵn pivot (chốt) là phần tử đầu tiên

VD:
mảng: 4 5 3 7 2
output: 3 2 4 5 7
(3 phải đứng trước 2, 5 phải đứng trước 7

#2

vẫn chưa tưởng tượng được đề, đăng hết cả đề luôn nha :smile:
2 vòng for chắc ổn á

#3

Cái này giống merge sort là chia làm 2 phần bé hơn và lớn hơn hoặc bằng nhưng lại chọn trước sau mới sắp các phần :slight_smile:

Code:

# 
a=[4,5,3,7,2]
def partition(a):
 lower=filter(lambda x: x<a[0],a)
 upper=filter(lambda x: x>=a[0],a)
 a[:]=lower+upper
 print " ".join(map(str,a))
partition(a)
1 Like
#4

Cho một dãy, chốt là phần tử đầu tiên (trong Quicksort ấy, ở đây người ta cho sẵn chốt đúng luôn đỡ phải tìm). Yêu cầu;

  • Bè hơn chốt thì dời qua trái chốt
  • Lớn hơn chốt thì dời qua phải
  • Trong mảng đã xử lý đó (xử lý 2 yêu cầu trên ấy) thì vị trí (trước sau) của các phần tử ko đổi, N1 đứng trước N2 thì sau khi xử lý, N1 vẫn phải đứng trước N2.
    VD:
    4 5 3 7 2
    Thằng đầu tiên (4) sẽ là chốt (đề người ta cho sẵn chốt nằm đó), 5 đứng trước 7, 3 đứng trước 2.

Output: 3 2 4 5 7
3 vẫn đứng trước 2 và 5 vẫn đứng trước 7

@Gio vậy là giờ em phải đi học merge sort à :’(
cơ mà code python ngộ quá nhỉ a[:]. Để em đi học Python, tới bài 15 bên LPTHW rồi.

#5

À. Nói thế là để chỉ trong cpp có hàm stable_sort: khi key = nhau thì nó vẫn giữ đúng thứ tự là nó dùng merge sort.

Ở đây em dùng mảng phụ lọc ra 1 phần < a[0] với 1 phần >=a[0] để giải quyết bài này.

Bình thường qsort sẽ chạy i=0(phần bé hơn) và j=n-1( phần lớn hơn) để tìm cái không thoã mãn và đổi chỗ. Cách làm này tiết kiệm bộ nhớ hơn :smile:

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?