Tiểu luận Sắp xếp chèn (insertion sort)

BÀI XEMINA SẮP XẾP CHÈN NHÓM THỰC HIỆN: NHÓM 3 Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp bắt chước cách sắp xếp quân bài của những người chơi bài. Muốn sắp một bộ bài theo trật tự người chơi bài rút lần lượt từ quân thứ 2, so với các quân đứng trước nó để chèn vào vị trí thích hợp Sắp xếp chèn (insertion sort) là một thuật toán sắp xếp rất hiệu quả với các danh sách nhỏ. Nó lần lượt lấy các phần tử của danh sách chèn vào vị trí thích hợp trong một danh sách mới đã được sắp. Sắp xếp chèn (Insertion sort) Thuật toán sắp xếp chèn làm việc cũng giống như tên gọi - Nó thực hiện việc quét một tập dữ liệu, với mỗi phân tử, thủ tục kiểm tra và chèn phần tử đó vào vị trí thích hợp trong danh sách đích (chứa các phần tử đứng trước nó đã được sắp xếp) được tiến hành. Phương pháp dễ dàng nhất để thực hiện thuật toán này là dùng hai vùng chứa dữ liệu khác nhau - tập dữ liệu nguồn và tập dữ liệu mà các phần tử đã sắp xếp được chèn vào. Tuy nhiên để tiết kiệm bộ nhớ, hầu hết các ứng dụng đều chỉ sử dụng một tập dữ liệu duy nhất. Thuật toán được tiến hành bằng cách dịch chuyển phân tử hiện tại đang xét tuần tự qua những phân tử ở vùng dữ liệu phía trước đã được sắp xếp, phép hoán vị nó với phần tử liền kề được thực hiện một cách lặp lại cho tới khi tiến tới được vị trí thích hợp.Do với mỗi phân tử, insertion sort cần thực hiện so sánh với các phần tử trước nó nên tối đa số lần duyệt dữ liệu là !N. Vì vậy cũng giống như Bubble sort, Insertion sort được coi là có độ phức tạp O(n2). Mặc dù có cùng độ phức tạp, Insertion sort hiệu quả hơn gần như hai lần so với Bubble sort, tuy nhiên vẫn không hiệu quả với tập dữ liệu lớn. *.Mô tả Cơ sở lập luận của sắp xếp chèn có thể mô tả như sau: Xét danh sách con gồm k phần tử đầu a1,...,ak. Với k = 1, danh sách gồm một phần tử đã được sắp. Giả sử trong danh sách k-1 phần tử đầu a1,...,ak − 1 đã được sắp. Để sắp xếp phần tử ak = x ta tìm vị trí thích hợp của nó trong dãy a1,...,ak − 1. Vị trí thích hợp đó là đứng trước phần tử lớn hơn nó và sau phần tử nhỏ hơn hoặc bằng nó. Các phần tử ≤x Vị trí thích hợp Các phần tử>x Các phần tử chưa sắp A1 ... ai − 1 x ai + 1 ... ak − 1 ak + 1 ... an *.Ví dụ 1: Cho danh sách 1 3 7 - 6 4 2 5 Danh sách con gồm 3 phần tử bên trái 1,3,7 đã được sắp. Để tiếp tục sắp xếp phần tử thứ tư a4 = 6 vào danh sách con đó, ta tìm vị trí thích hợp của nó là sau 3 và trước 7. 1 3 6 7 - 4 2 5 Làm tiếp theo với a5 = 4 ta được 1 3 4 6 7 - 2 5 Làm tiếp theo với a6 = 2 ta được 1 2 3 4 6 7 - 5 Cuối cùng chèn a7 = 5 1 2 3 4 5 6 7 - VD 2: A = { 5 8 6 3 10 } Insertion sort làm như sau : Chia mảng A làm 2 phần sorted và unsorted Ban đầu sorted là B = { 5 } Unsorted là C = { 8 6 3 10 } Lần làm thứ nhất : Lấy phần tử đầu tiên của C là 8 ra---> C = { 6 3 10 } Tìm vị trí của số 8 trong mảng B ---> B = { 5 8 } Lần làm thứ hai : Lấy phần tử đầu tiên của C là 6 ra---> C = { 3 10 } Tìm vị trí của số 6 trong mảng B ---> B = { 5 6 8 } Lần làm thứ ba : Lấy phần tử đầu tiên của C là 3 ra---> C = { 10 } Tìm vị trí của số 3 trong mảng B ---> B = { 3 5 6 8 } Lần làm thứ tư : Lấy phần tử đầu tiên của C là 10 ra---> C = { } Tìm vị trí của số 10 trong mảng B ---> B = { 3 5 6 8 10} Kết thúc thuật toán   *.GIẢI THUẬT: program xemina; uses crt; type mang=array[1..100] of real; var a:mang; n:integer; x:real; procedure khoitao(var a:mang; var n:integer); var i:integer; begin write('nhap so phan tu cua mang: '); readln(n); for i:=1 to n do begin write('a[',i,']='); readln(a[i]); end; end; procedure sapxep(var a:mang;n:integer); var i,j:integer; tam:real; begin for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin tam:=a[i]; a[i]:=a[j]; a[j]:=tam; end; readln; end; procedure chen(var a:mang;var n:integer); var x:real; i,j:integer; begin write('nhap phan tu can chen: '); readln(x); i:=1; while ((x>a[i]) and (i<=n)) do i:=i+1; for j:=n+1 downto i do a[j]:=a[j-1]; a[i]:=x; n:=n+1; end; procedure ina(a:mang;n:integer); var i:integer; begin for i:=1 to n do write(a[i]:5:0); readln; end; BEGIN khoitao(a,n); sapxep(a,n); chen(a,n); ina(a,n); readln; END. Hoặc đoạn mã sau: program insertion(input,output);constMAX = 10;vara : array[1..MAX] of integer;i, n : integer;procedure insertion_sort;vari, pos : integer;value : integer;done : boolean;beginfor i := 2 to n dobeginvalue := a[i];pos := i;done := false;while not done dobeginif pos = a[pos-1] thendone := trueelsebegina[pos] := a[pos-1];pos := pos-1endend;a[pos] := value;endend;begin { main }writeln('How many number would you like to sort (max=',MAX:2,') ?');readln(n);writeln('Enter in ',n:1,' numbers:');for i := 1 to n doread(a[i]);insertion_sort;for i := 1 to n dowrite(a[i]:1,' ');writeln; readln;end. *. Ý nghĩa của insertion sort là lấy một phần tử của mảng ra và insert vào vị trí thích hợp trong mảng  *.ĐÁNH GIÁ GIẢI THUẬT: Ðối với giải thuật chèn trực tiếp, các phép so sánh xảy ra trong mỗi vòng lặp while tìm vị trí thích hợp pos, và mỗi lần xác định vị trí đang xét không thích  hợp, sẽ dời chỗ phần tử  a[pos] tương ứng. Giải thuật thực hiện tất cả N-1 vòng lặp while , do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ có thể ước lược trong từng trường hợp như sau : Trường hợp Số phép so sánh Số phép gán Tốt nhất Xấu nhất CÁC THÀNH VIÊN: 1.Dương Anh Vũ 2.Hồ Thanh Phong 3.Nguyễn Thị Thanh Tuyền 4.Ung Sĩ Cao Trân 5.Lê Văn Tình 6.Nguyễn Thị Mỹ Thu 7.Dương Công Thắng 8.Lê Thành Thương