Sắp Xếp

Sắp Xếp Chọn ( Selection Sort)

ý tưởng : làm theo ngôn ngữ lập trình C nha, chọn phần tử nhỏ nhất đem ra đầu danh sách.

Bước 1 : chọn từ phần tử thứ 0 đến n-1 lấy phần nhỏ nhất gán vào vị trí đầu tiên thứ 0
Bước 2 : chọn từ phần tử thứ 1 đến n-1 lấy phần tử nhỏ nhất gán vào vị trí thứ 1
v.v...
sau n-1 bước thì dãy được sắp xếp xong

Thí dụ :
cho dãy số : 5 6 2 2 10 12 9 10 9 3
mình lập bảng :

địa chỉ	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]
Bước đầu	5	6	2	2	10	12	9	10	9	3
Bước 1	2	6	5	2	10	12	9	10	9	3
Bước 2		2	5	6	10	12	9	10	9	3
Bước 3			3	6	10	12	9	10	9	5
Bước 4				5	10	12	9	10	9	6
Bước 5					6	12	9	10	9	10
Bước 6						9	12	10	9	10
Bước 7							9	10	12	10
Bước 8								10	12	10
Bước 9									10	12
Kết Quả	2	2	3	5	6	9	9	10	10	12

Chương Trình :

Code:

void Select(){
   int i, j, k, temp ;
   for( i = 0; i < n; i ++ ){
      k = i ;
      for( j = i + 1 ; j < n ; j ++)
         if(a[j] < a[k])
            k = j ;
      temp = a[i] ;
      a[i] = a[k] ;
      a[k] = temp ;
   }
}

Sắp Xếp Xen (Insertion Sort)

Ý tưởng : giống như mình quánh bài 13 lá. lấy lá đầu lên xem như danh sách đã có thứ tự.
lấy lá thứ 2 lên so sánh với lá thứ 1 rồi sắp xếp, tương tự cho các lá bài còn lại.

Bước 1: lấy phần tử a[1] xen vào danh sách đã có thứ tự là phần tử a[0] thành một danh sách có thứ tự
Bước 2 : lấy phần tử a[3] xen vào danh sách a[1], a[2] sao cho a[1], a[2], a[3] là danh sách có thứ tự.
.........
sau n-1 bước thì dãy được sắp xếp xong

Thí dụ :
cho dãy số : 5 6 2 2 10 12 9 10 9 3
lập bảng :

Địa chỉ	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]
Bước đầu	5	6	2	2	10	12	9	10	9	3
Bước 1	5	6
Bước 2	2	5	6
Bước 3	2	2	5	6
Bước 4	2	2	5	6	10
Bước 5	2	2	5	6	10	12
Bước 6	2	2	5	6	9	10	12
Bước 7	2	2	5	6	9	10	10	12
Bước 8	2	2	5	6	9	9	10	10	12
Bước 9	2	2	3	5	6	9	9	10	10	12

Chương Trình :

Code:

void InSert(){
   int k, j ;
   for( int i = 1; i < n ; i ++){
      k = a[i] ;
      j = i - 1 ;
      while(a[j] > k && j >= 0){
         a[j+1] = a[j] ;
         j -- ;
      }
      a[j+1] = k ;
   }
}

Sắp Xếp Nổi Bọt ( Bubble Sort)

Ý Tưởng : cho 1 dãy số. ta lấy phần tử cuối cùng của dãy so sánh với phần tử trước nó nếu nó nhỏ hơn thì
hóan đổi vị trí cho nhau và tiếp tục so sánh với phần tử trước nó.

Bước 1 : xét phần tử a[n-1] đến a[1] . phần tử a[n-1] sẽ so sánh với phần tử a[n-2] nếu nhỏ hơn sẽ hóan đổi vị trí
của 2 phần tử cho nhau rồi tiếp tục so sánh với phần tử a[n-3] v.v... đến phần tử a[1] thì ta so sánh với phần tử
a[0]. nếu nhỏ hơn thì ta hóan đổi vị trí với nhau.

Bước 2 : xét phần tử a[n-1] đến a[2]. là vì phần tử a[0] đã là nhỏ nhất giờ tìm phần tử nhỏ nhất từ a[n-1] đến a[1].
làm tương tự như Bước 1.
.........

sau n-1 bước thì kết thúc


Thí dụ :
cho dãy số : 5 6 2 2 10 12 9 10 9 3
lập bảng :

	Địa Chỉ	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]
	Bước Đầu	5	6	2	2	10	12	9	10	9	3
	Bước 1	2	5	6	2	3	10	12	9	10	9
	Bước 2		2	5	6	3	9	10	12	9	10
	Bước 3			3	5	6	9	9	10	12	10
	Bước 4				5	6	9	9	10	10	12
	Bước 5					6	9	9	10	10	12
	Bước 6						9	9	10	10	12
	Bước 7							9	10	10	12
	Bước 8								10	10	12
	Bước 9									10	12
	Kết Quả	2	2	3	5	6	9	9	10	10	12

Chương Trình

Code:

void Bubble(){
   int temp ;
   for(int i = 0; i < n; i ++)
      for( int j = 0; j < n-1 ; j ++)
         if(a[j] > a[j+1] ){
            temp = a[j] ;
            a[j] = a[j+1] ;
            a[j+1] = temp ;
         }
}

hôm nào làm tiếp buồn ngủ òi