Sắp xếp trong Pascal 2020-08-06T20:34:34+07:002020-08-06T20:34:34+07:00https://sachgiai.com/Tin-hoc/sap-xep-trong-pascal-13457.htmlhttps://sachgiai.com/uploads/news/2020_07/lap-trinh-pascal.jpgSách Giảihttps://sachgiai.com/uploads/sach-giai-com-logo.pngThứ năm - 06/08/2020 20:18 Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất định 1. KHÁI NIỆMa) Sắp xếp là một quá trình tồ chức lại một dãy các dữ liệu theo một trật tự nhất định.b) Mục đích của việc sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu được dễ dàng và nhanh chóng.Sắp xếp là một việc làm hết sức cơ bản và được dùng rộng rãi trong các kĩ thuật lập trình nhằm xử lí một dãy các dữ liệu.c) Các giải thuật sắp xếp được phân chia thành hai nhóm chính là:- Sắp xếp trong (hay sắp xếp mảng).Toàn bộ dữ liệu cần sắp xếp phải được đưa vào bộ nhớ chính của máy tính, do đó nó thường được sử dụng khi khối lượng dữ liệu không vượt quá dung lượng bộ nhớ chính.Nhóm sắp xếp trong bao gồm các phương pháp:• Phương pháp đếm.• Phương pháp chèn.• Phương pháp chọn.• Phương pháp đổi chỗ.• Phương pháp trộn.- Sắp xếp ngoài (hay sắp xếp tập tin).Áp dụng trong trường hợp ta phải sắp xếp các tập tin chứa nhiều mẫu tin và mỗi mẫu tin có chiều dài tương đôi lớn, do đó ta không thể nạp toàn bộ tập tin này vào bộ nhớ chính để sắp thứ tự. Vì vậy ta phải có những phương pháp thích hợp cho việc sắp thứ tự tập tin.2. SẮP XẾP TRONGa) Khái niệmCấu trúc dữ liệu thích hợp cho các phần tử cần sắp thứ tự là record. Mỗi phần tử có hai vùng đặc trưng là: vùng key để chứa khóa của phần tử và được sử dụng trong các giải thuật tìm kiếm, vùng info dùng đề chứa dữ liệu của phần tử.Ta khai báo:Type item = record key: integer; info: integer; end; 1Var a: array[1..n] of intern;Khóa của phần tử có thể là chữ hoặc số.Yêu cầu của giải thuật là dùng ít vùng nhớ và thời gian thực hiện nhanh.b) Phương pháp đếm (Counting sort)* Giải thích:Nội dung của phương pháp này là đếm phần tử có khóa nhỏ hơn hay bằng khóa của phần tử a[i]. Nếu có j phần tử có khóa nhỏ hơn khóa của phần tử a[i] thì phần tử a[i] sẽ có vị trí thứ (j + 1) trong dãy đã có thứ tự.Trong giải thuật, ta dùng mảng count(i) (i = 1, 2, ..., n) với count[i] cho biết số phần tử có khóa nhỏ hơn khóa của phần tử a[i]. Như vậy count[i + 1] là vị trí của phần tử a[i] trong dãy đã có thứ tự.* Ví dụ:Sắp xếp dãy 3 1 5 2 7 6 9 4 i: 1 2 3 4 5 6 7 8 a: 3 1 5 2 7 6 9 4 Count: 2 0 4 1 6 5 7 3Như vậy phần tử có khóa 9 ở vị trí thứ 8 vì Count[9] = 7* Thể hiện bằng PASCAL:Procedure Counting_Sort;Var Count: array[1..n] of integer; s: array[1..n] of item; i, j: integer;Begin For i:= 1 to n do count[i]:= 0 For i:= n down to 2 do For j:= i - 1 down to 1 do if a[i]. Key < a[j]. Key then Count[j]:= Count[i] + 1 else count[i]:= count[i] + 1; For i:= 1 to n do s[count[i] + 1] := a[i]; For i:= 1 to n do a[i]:= s[i];End;c) Phương pháp chèn (Insertion Sort)* Giải thích:Nội dung của phương pháp này là giả sử ta có dãy a[l]..a[i -1] đã có thứ tự, ta phải xác định vị trí thích hợp của phần tử a[i] trong dãy a[l]..a[i -1] bằng phương pháp tìm kiếm tuần tự từ a[i -1] bằng phương pháp tìm kiếm tuần tự từ a[i -1] trở về phía a[l] để tìm ra vị trí thích hợp của a[i]. Ta chèn a[i] vào vị trí này và kết quả là dãy a[l]..a[i] có thứ tự. Ta áp dụng cách làm này với i = 2, 3, n.* Ví dụ:Ta phải sắp xếp dãy số:39 50 7 37 89 13 1 62i = 2 39 50 7 37 89 13 1 62i = 3 39 50 7 37 89 13 1 62i = 4 7 39 50 37 89 13 1 62i = 6 7 37 39 50 89 13 1 62i = 5 7 37 39 50 89 13 1 62i = 7 7 13 37 39 50 89 1 62i = 8 1 7 13 37 39 50 98 62 1 7 13 37 39 50 62 89* Thể hiện bằng Pascal:Procedure Insertion-Sort;Var x: item; i, j: integer;Begin For i:= 2 to n do Begin x:= a[i]; a[0] := x; j := j - 1; While x. key < a[j]. key do begin a[j + 1] := a[j]; j := i - 1; end; a[j + 1]:= x; end;End;d) Phương pháp chọn (Selection Sort)* Giải thích:Nội dung của phương pháp này là ở bước thứ i (i = 1, 2, n-1) ta lựa chọn phần tử nhỏ nhất trong dãy a[i]..a[n] rồi đổi chỗ phần tử này với phần tử a[i]. Cuối cùng ta sẽ có dãy a[l]..a[n] có thứ tự.* Ví dụ:Ta phải sắp xếp dãy số: 39 50 7 37 89 13 1 62i = 1 39 50 7 37 89 13 1 62i = 2 1 50 7 37 89 13 39 62i = 3 1 7 50 37 89 13 39 62i = 4 1 7 13 37 89 50 39 62i = 5 1 7 13 37 89 50 39 62i = 6 1 7 13 37 39 50 89 62i = 7 1 7 13 37 39 50 89 62 1 7 13 37 39 50 89 62* Thể hiện bằng PASCAL:Procedure Selection_Sort;Var i, j, k: integer; x: item; min: interger;Begin For i := 1 to n - 1 do begin min:= a[i]. key; k := i; For:= i; For j:= i + 1 to n do If a[j]. key < min then Begin min:= a[j]. key; k:= j; end; x:= a[k] ; a[k]:= a[i]; a[i]:= x; end;end;e) Phương pháp đổi chỗCó rất nhiều phương pháp sắp xếp dựa trên việc đổi chỗ giữa 2 phần tử của dãy. Sau đây chúng ta sẽ xét các phương pháp:- Bubble Sort.- Shake Sort.- Sell Sort.- Quick Sort.* Bubble Sort* Giải thích:Nội dung của phương pháp này là ta duyệt dãy a[1], ..., a[n]. Nếu a[i].Key > a[i + l].Key > ai = 1, 2, ..., n - 1) thì ta đổi chỗ phần tử a[i] với phần tử a[i + 1]. Lập lại quá trình duyệt dãy này cho đến khi không có xảy ra việc đổi chỗ của hai phần tử.Chú ý rằng bất kì lúc nào phần tử nhỏ nhất cũng gặp trước tiên, nó như những bọt khí nhẹ sẽ nổi lên trên khi ta đun nước. Sau đó ở thứ hai phần tử nhỏ thứ 2 sẽ được đặt vào đúng vị trí. Vì vậy sắp xếp nổi bọt thao tác như một kiểu sắp xếp chọn, mặc dù nó không làm nhiều việc hơn để đưa từng phần tử vào đúng vị trí.* Ví dụ:Ta phải sắp xếp: 39 50 7 37 89 13 1 62Bước 0 1 2 3 4 5 6 7——————————————————————— 39 1 1 1 1 1 1 1 50 39 7 7 7 7 7 7 7 50 39 13 13 13 13 13 37 7 50 39 37 37 37 37 89 37 13 50 39 39 39 39 13 89 37 37 50 50 50 50 1 13 89 62 62 62 62 62 62 62 62 89 89 89 89 89* Thể hiện bằng PASCAL:Procedure Bubblej_Sort;Var i, j : integer; x : item;Begin For i:= 2 to n do For j:= n down to i do If a[j - 1]. key > a[j], key then Begin x := a[j - 1]; a[j - 1] := a[j]; a[j] := x; end;end;* Cải tiến:Ta nhận thấy rằng nếu ở một lần duyệt dãy nào đó mà không có xảy ra sự đổi chỗ giữa hai phần tử thì dãy đang sắp đã có thứ tự và giải thuật kết thúc.Ta có thể đặt cờ để ghi nhận điều này và co chương trình sau:Procedure Bubble_Sort2;VarFlag : Boolean; i : integer; x : item;Begin flag := true; While flag do Begin flag := false; for i := 1 to n - 1 do if a[i]. Key > a[i + 1].Key then Begin x := a[i]; a[i]:= a[i + 1]; a[i + 1] := a; flag:= true; end; end;end;* Shake Sort* Giải thích:Phương pháp này là một cải tiến của phương pháp Bubble Sort theo hướng không những phần tử nhẹ nổi lên trên mà cả phần tử nặng cũng xuống dưới giống như khi ta “rung” một cái nồi và thuật toán sắp xếp phải điều khiển cả hai quá trình “nổi lên” và “chìm xuống” này một cách tự giác. Muốn vậy ta phải ghi nhớ lần đổi chỗ cuối cùng khi duyệt dãy từ dưới lên và khi duyệt dãy từ trên xuống để quyết định trong chu trình kế tiếp sẽ chỉ duyệt từ đây đến đâu.* Ví dụ:Sắp xếp dãy số:39 50 7 37 89 13 1 62d = 2 3 3 4 4 c = 8 8 7 7 4 39 1 1 1 1 50 39 39 7 7 . 7 50 7 39 13 37 7 37 13 37 89 37 50 37 39 13 89 13 50 50 1 13 62 62 62 62 62 89 89 89 Thể hiện bằng PASCAL:Procedure Shake_Sort; Var i, k, d, c: integer; x : item ; Begin d:= 2; c:= n; k:= n; Repeat For i:= c down to d do if a[i - l].Key > a[i].Key then Begin x:= a[i - 1] a[i - 1] := [a] ; a[i] := x ; k := i; end; d := k + 1; For i:= d to c do If a[i - 1]. key > a[i].Key then Begin x:= a[i - 1]; a[i - 1]:= a[i] ; a[i] := x; k := i; end; c := k - 1 Until d > cend;* Shell Sort* Giải thích:Các phương pháp sắp xếp đã trình bày ở trên nói chung đều di chuyển mỗi phần tử đi một vị trí trong mỗi bước. Phương pháp Shell Sort dựa trên ý tưởng chính là hoán vị các phần tử ở xa nhau. Để làm được việc đó ta cần phải sắp xếp lại tập tin để cho nó có tính chất là việc lấy mọi phần tử thứ h (bắt đầu từ bất cứ vị trí nào) cũng đều cho ra một tập tin đã sắp. Một tập tin như vậy được gọi là sắp theo độ dài bước h. Nói một cách khác, một tập tin được sắp theo độ dài h là tập tin được sắp độc lập với nhau, đan xen vào nhau. Bằng cách sắp xếp theo độ dài bước h ứng với vài giá trị h khá lớn, chúng ta có thể di chuyển các phần tử ở những khoảng cách xa trong mảng và vì vậy dễ dàng hơn để sắp xếp độ dài bước h cho các giá trị h nhỏ hơn. Dùng thủ tục này cho bất kì một dãy các giá trị của h tận cùng là 1 sẽ cho ra một tập tin đã sắp cho xong: Đó chính là Shell Sort.* Ví dụ:Ta phải sắp xếp dãy: 39 50 7 37 89 13 1 62Bước 1: 4-Sort 39 50 7 37 89 13 1 62 39 13 1 37 89 50 7 62Bước 2: 2-Sort 39 13 1 37 89 50 7 62 1 13 7 37 39 50 89 62Bước 3: 1-Sort 1 13 7 37 39 50 89 62 1 7 13 37 39 50 89 62* Thể hiện bằng PASCAL:CHÚ Ý:- Ta dùng dãy phụ chứa độ tăng h[1], ..., h[t| để điều khiển quá trình sắp thứ tự với h[t]= 1. Việc chọn các độ tăng thích hợp sẽ làm giảm thời gian sắp thứ tự.Đặt hl = h[l] ta phải khai báo lại dãy a như sau:a: array [h1..n] of item;các phần tử a[i] (i <= 0) là các lính canh. Sau đây ta chọn: h[1] = 9, h[2] = 5, h[3] = 3, h[4] = 1Procedure Shell_Sort;Const t = 1Var i, j, k, s: integer; x: item; m: integer; h: array[l..t] of integer;Begin h[1] := 9; h[2] := 5; h[3] := 3; h[4] := 1; For m := 1 to t do Begin k := h[m|; s := -k; For i:= k + 1 to n do Begin x:= a[i]; j := i - k; If s = 0 then s := -k; x := s + 1 a[s] := x; while x.key < a[j].key do Begin a[j + k]:= a[j]; j := j - k; end; a[j + k] := x end; end;end;• Quick Sort* Giải thích:Nội dung của phương pháp này là chọn phần tử x ở giữa của dãy làm chuẩn để so sánh. Ta phân hoạch dãy này thành 3 dãy con liên tiếp nhau:- Dãy con thứ nhất gồm các phần tử có khóa nhỏ hơn x.key.- Dãy con thứ hai gồm các phần tử có khóa bằng x.key.- Dãy con thứ ba gồm các phần tử có khóa lớn hơn x.key.Sau đó áp dụng giải thuật phân hoạch này cho dãy con thứ nhất và dãy con thứ ba, nếu các dãy con này có nhiều hơn một phần tử (đệ qui).Cụ thể là xét một đoạn của dãy từ thành phần thứ L đến thành phần thứ R.- Lấy giá trị của thành phần thứ (L+R) dir 2 gán vào biến X.- Cho i ban đầu là L.- Cho J ban đầu là R.- Lặp lại.• Chừng nào còn A[i] < X thì tăng i• Chừng nào còn A[j] > X thì giảm j• Nếu i <= j thì+ Hoán vị A[i] và A[j]+ Tăng i+ Giảm j Cho đến khi i > j+ Sắp xếp đoạn từ A[L] đến A[j]+ Sắp xếp đoạn từ A[i] đến A[R]* Ví dụ:Sắp xếp dãy số:39 50 7 37 89X = 37Sau 2 lần đổi chỗ ta được dãy:1 13 7 37 89Xử lí dãy con 1 13 7Ta được: 1 7 13Xử lí dãy con89 50 39 62Ta được39 50 89 6239 50 62 89Vậy dãy đã sắp xếp là:1 7 13 37 39 50 62 89Ta nhận thấy ý tưởng chính ở đây là “chia để trị”.* Thể hiện hằng PASCAL:Để đơn giản ta viết thủ tục sắp một mảng số nguyên được truyền bằng tham biến.Procedure Quick_Sort (Var A: Array[1..n] of integer);Procedure Sort (L, R: integer); Var i, j, TG, X: integer Begin X:= A[(L + R div 2]; i := L; j := R; Repeat while (A[i] < X) do inc (i); while (A[j] > X) do dec(j); if i <= j then Begin TG:= A[i]; A[i]:= A[j]; A[j]:= TG; Inc(i); Dec(j); end; Until i > j; if L < j then sort (L, J); if i < R then sort [I, R];Begin sort (1, n);End. .... (Còn nữa) Bản quyền bài viết thuộc về Sachgiai.com. Ghi nguồn Sách giải.com khi đăng lại bài viết này.
Ý kiến bạn đọc
Sắp xếp theo bình luận mới Sắp xếp theo bình luận cũ Sắp xếp theo số lượt thích
muốn học thêm kiến thức về mảng 1 chiều AnhThikTin 27/02/2023 14:16
Trả lời
Thích 0
Không thích 3
Những tin mới hơn
Sắp xếp trong Pascal (tiếp theo)
Đệ qui trong Pascal
Những tin cũ hơn
Tìm kiếm trong Pascal
Giới thiệu phần mềm Turbo Pascal
Lớp 1
Kết nối tri thức
Tiếng Việt 1
Toán 1
Giáo dục thể chất 1
Mỹ thuật 1
Chân trời sáng tạo
Tiếng Việt 1
Toán 1
Cánh diều
Âm nhạc 1
Giáo dục thể chất 1
Hoạt động trải nghiệm 1
Toán 1
Tự nhiên và xã hội 1
Lớp 2
Kết nối tri thức
Toán 2
Tiếng Việt 2
Chân trời sáng tạo
Tiếng Việt 2
Toán 2
Cánh diều
Toán 2
Tiếng Việt 2
Lớp 3
Kết nối tri thức
Tiếng Việt 3
Toán 3
Cánh diều
Tiếng Việt 3
Toán 3
Chân trời sáng tạo
Tiếng Việt 3
Toán 3
Lớp 4
Kết nối tri thức
Tiếng Việt 4
Toán 4
Chân trời sáng tạo
Tiếng Việt 4
Toán 4
Cánh diều
Tiếng Việt 4
Toán 4
Lớp 5
Kết nối tri thức
Tiếng Việt 5
Toán 5
Cánh diều
Tiếng Việt 5
Toán 5
Chân trời sáng tạo
Tiếng Việt 5
Toán 5
Lớp 6
Kết nối tri thức
Ngữ Văn 6
Toán 6
Tiếng Anh 6 Global Success
Lịch sử và Địa lí 6
Giáo dục công dân 6
Tin học 6
Cánh diều
Giáo dục công dân 6
Ngữ Văn 6
Toán 6
Chân trời sáng tạo
Ngữ Văn 6
Toán 6
Giáo dục công dân 6
Lớp 7
Kết nối tri thức
Ngữ Văn 7
Toán 7
Tiếng Anh 7 Global Success
Giáo dục công dân 7
Lịch sử và Địa lí 7
Khoa học tự nhiên 7
Tin học 7
Công nghệ 7
Cánh Diều
Ngữ Văn 7
Toán 7
Khoa học tự nhiên 7
Chân trời sáng tạo
Ngữ Văn 7
Toán 7
Mĩ thuật 7
Âm nhạc 7
Lớp 8
Kết nối tri thức
Ngữ Văn 8
Toán 8
Khoa học tự nhiên 8
Giáo dục công dân 8
Tin học 8
Lịch sử và Địa lí 8
Công nghệ 8
Tiếng Anh 8 Global Success
Cánh Diều
Ngữ Văn 8
Toán 8
Công Dân 8
Chân trời sáng tạo
Ngữ Văn 8
Toán 8
Lớp 9
Kết nối tri thức
Ngữ Văn 9
Toán 9
Khoa học tự nhiên 9
Giáo dục công dân 9
Tin học 9
Lịch sử và Địa lí 9
Tiếng Anh 9 Global Success
Công nghệ 9
Cánh Diều
Ngữ Văn 9
Toán 9
Chân trời sáng tạo
Ngữ Văn 9
Toán 9
Lớp 10
Kết nối tri thức
Ngữ Văn 10
Toán 10
Kinh tế và Pháp luật 10
Tiếng Anh 10 Global Success
Lịch Sử 10
Địa Lí 10
Vật Lí 10
Hoá học 10
Sinh học 10
Công nghệ trồng trọt 10
Công nghệ thiết kế 10
Quốc Phòng và An Ninh 10
Tin học 10
Cánh Diều
Ngữ Văn 10
Toán 10
Kinh tế và Pháp luật 10
Tin học 10
Hoá học 10
Lịch sử 10
Địa Lí 10
Sinh học 10
Vật lí 10
Tiếng Anh 10 Explore New Worlds
Công nghệ trồng trọt 10
Công nghệ thiết kế 10
Chân trời sáng tạo
Ngữ Văn 10
Toán 10
Lịch Sử 10
Địa Lí 10
Sinh học 10
Vật Lí 10
Hoá học 10
Quốc Phòng và An Ninh 10
Kinh tế và Pháp luật 10
Tiếng Anh 10 Friends plus
Lớp 11
Kết nối tri thức
Ngữ Văn 11
Toán 11
Hoá học 11
Sinh học 11
Địa Lí 11
Lịch Sử 11
Vật Lí 11
Kinh tế và Pháp luật 11
Công nghệ 11 Chăn nuôi
Công nghệ 11 Cơ khí
Tin học 11 Ứng dụng
Tin học 11 Khoa học máy tính
Tiếng Anh 11 Global Success
Cánh Diều
Ngữ Văn 11
Toán 11
Hoá học 11
Lịch Sử 11
Địa Lí 11
Sinh học 11
Vật Lí 11
Tin học 11 Ứng dụng
Tin học 11 Khoa học máy tính
Tiếng Anh 11 Explore New Worlds
Quốc phòng và An ninh 11
Kinh tế và Pháp luật 11
Công nghệ 11 Chăn nuôi
Công nghệ 11 Cơ khí
Chân trời sáng tạo
Ngữ Văn 11
Toán 11
Địa Lí 11
Hoá học 11
Sinh học 11
Lịch Sử 11
Kinh tế và Pháp luật 11
Tiếng Anh 11 Friends plus
Vật Lí 11
Lớp 12
Kết nối tri thức
Ngữ Văn 12
Toán 12
Địa Lí 12
Hoá học 12
Lịch Sử 12
Sinh học 12
Vật Lí 12
Tiếng Anh 12 Global Success
Tin học 12 Ứng dụng
Tin học 12 Khoa học máy tính
Kinh tế và Pháp luật 12
Công nghệ 12 Chăn nuôi
Công nghệ 12 Cơ khí
Cánh Diều
Ngữ Văn 12
Toán 12
Chân trời sáng tạo
Ngữ Văn 12
Toán 12
THÀNH VIÊN
Hãy đăng nhập thành viên để trải nghiệm đầy đủ các tiện ích trên site Nhập mã do ứng dụng xác thực cung cấp Thử cách khác Nhập một trong các mã dự phòng bạn đã nhận được. Thử cách khác Đăng nhập Đăng ký