Thuật toán sắp xếp

Thuật toán sắp xếp nổi bọt (hubble sort)

Giả sử dãy a cần sắp xếp có n phần tử (a₁èa_n) theo thứ tự tăng. 
+Sắp xếp từ trên xuống

Khi tiến hành từ trên xuống, ta so sánh hai phần tử đầu, nếu phần tử đứng trước lớn hơn phần tử đứng sau thì đổi chỗ chúng cho nhau. Tiếp tục làm như vậy với cặp phần tử thứ hai và thứ ba và tiếp tục cho đến cuối tập hợp dữ liệu, nghĩa là so sánh (và đổi chỗ nếu cần) phần tử thứ n-1 với phần tử thứ n. Sau bước này phần tử cuối cùng chính là phần tử lớn nhất của dãy.

Sau đó, quay lại so sánh (và đổi chố nếu cần) hai phần tử đầu cho đến khi gặp phần tử thứ n-2....

For i:=n down to 2 do

For j:=1 to i-1 do

if a[j] > a[j+1] then đổichỗ(a[j],a[j+1]) 

+Sắp xếp từ dưới lên

Sắp xếp từ dưới lên so sánh (và đổi chỗ nếu cần) bắt đầu từ việc so sánh cặp phần tử thứ n-1 và n. Tiếp theo là so sánh cặp phần tử thứ n-2 và n-1,... cho đến khi so sánh và đổi chỗ cặp phần tử thứ nhất và thứ hai. Sau bước này phần tử nhỏ nhất đã được nổi lên vị trí trên cùng (nó giống như hình ảnh của các "bọt" khí nhẹ hơn được nổi lên trên). Tiếp theo tiến hành với các phần tử từ thứ 2 đến thứ n.

For i:=2 to n do

For j:=n downto i do

if a[j]<a[j-1] then đổichỗ(a[i],a[j]);

+độ phức tạp của bài toán là O(n2).

Một cách cài đặt khác
For i:= 1 to n-1 do

          For j:= i+1 to n do
                  if (a[i] > a[j]) then
                  đổichỗ(a[i],a[j]);

Thuật toán sắp xếp nhanh (Quick Sort)

Procedure sxnhanh(l,r:integer);

Var i,j,x,tg:integer;

Begin

x:=a[(l+r) div 2];

  i:=l;j:=r;

  Repeat

    While(a[i]<x) do i:=i+1;

     While (x<a[j]) do j:=j-1;

      if i<=j then

        Begin

          tg:=a[i];a[i]:=a[j];a[j]:=tg;

          i:=i+1;j:=j-1;

        End;

 until i>j;

 if l<j then sxnhanh(l,j);

 if i<r then sxnhanh(i,r);

End;

Chú ý: Thuật toán sắp xếp nhanh phải tổ chức dưới dạng một thủ tục để gọi đệ quy