Cho một mảng và phạm vi của mảng [startval, endval]. Mảng được chia thành ba phần.
- Tất cả phần tử nhỏ hơn startval đến trước.
- Tất cả phần tử trong phạm vi startval đến endval đến tiếp theo.
- Tất cả phần tử lớn hơn endval xuất hiện ở cuối.
Ví dụ
Input: A = [1, 14, 51, 12, 4, 2, 54, 20, 87, 98, 3, 1, 32] startval = 14, endval = 54 Output: A = [1, 12, 4, 2, 3, 1, 14, 51, 20, 32, 54, 87, 98]
Thuật toán
Bước 1: Đầu tiên danh sách được chia thành ba phần, phần đầu chứa phần tử nhỏ hơn startval, phần hai chứa phần tử giữa startval và endval và phần ba chứa phần tử lớn hơn endval. Bước 2: Nối tất cả ba phần lại với nhau.
Mã ví dụ
def partition_array(input, lowVal, highVal):
# Tách danh sách đầu vào thành ba phần
my_first = [num for num in input if num < lowVal]
my_second = [num for num in input if (num >= lowVal and num <= highVal)]
my_third = [num for num in input if num > highVal]
# Nối tất cả ba phần
print(my_first + my_second + my_third)
# Chương trình driver
if __name__ == "__main__":
my_input = [10, 140, 50, 200, 40, 20, 540, 200, 870, 980, 30, 10, 320]
my_lowVal = 140
my_highVal = 200
partition_array(my_input, my_lowVal, my_highVal)
Đầu ra
[10, 50, 40, 20, 30, 10, 140, 200, 200, 540, 870, 980, 320]