SLIDE1

Saturday, January 24, 2015

thuật toán selection sort

/*thuật toán selection sort
Ý tưởng:
Chọn phần tử nhỏ nhất trong N phần tử trong dãy hiện hành ban đầu.
Đưa phần tử này về vị trí đầu dãy hiện hành
Xem dãy hiện hành chỉ còn N-1 phần tử của dãy hiện hành ban đầu
Bắt đầu từ vị trí thứ 2;
Lặp lại quá trình trên cho dãy hiện hành... đến khi dãy hiện hành chỉ còn 1 phần tử
Bước 1:   i = 0;
Bước 2:  Tìm phần tử a[min] nhỏ nhất trong    dãy hiện hành từ a[i] đến a[N]
Bước 3 :  Đổi chỗ a[min] và a[i]
Bước 4 :  Nếu  i < N-1 thì
i = i+1; Lặp lại Bước 2;                Ngược lại: Dừng.

*/
#include<iostream>
using namespace std;
void xep(int a[], int n)
{
int i, j, m,t;
for (i = 0; i < n - 1; i++)
{
m = i;
for (j = i + 1; j < n; j++) if (a[m]>a[j]) m = j;
t = a[i]; a[i] = a[m]; a[m] = t;
}
}
void main()
{
int a[10] = { 5, 4, 7, 8, 2, 3, 1, 9, 6, 10 };
xep(a, 10);
for (int i = 0; i < 10; i++) cout << " " << a[i];
}

Related Posts:

  • thuật toán heap sort - sắp xếp vun đống, (cây) thuật toán heap sort - sắp xếp vun đống, (cây) Heap Sort tận dụng được các phép so sánh ở bước i-1 mà thuật toán sắp xếp chọn trực tiếp không tận dụng được Để làm được điều này Heap sort thao tác dựa trên cây. Ở cây trê… Read More
  • thuật toán insertion sort - chèn trực tiếp thuật toán insertion sort - chèn trực tiếp Giả sử có một dãy a0 , a1 ,... ,an-1 trong đó i phần tử đầu tiên a0 , a1 ,... ,ai-1 đã có thứ tự. Tìm cách chèn phần tử  ai vào vị trí thích hợp của đoạn đã được sắp để có dãy… Read More
  • thuật toán shell sort - cải tiến của chèn trực tiếp thuật toán shell sort - cải tiến của chèn trực tiếp shell sort là Cải tiến của phương pháp chèn trực tiếp Ý tưởng: Phân hoạch dãy thành các dãy con Sắp xếp các dãy con theo phương pháp chèn trực tiếp Dùng phương pháp… Read More
  • thuật toán binary insertion sort - chèn nhị phân thuật toán binary insertion sort - chèn nhị phân void BInsertionSort(int a[],int n ) { int l,r,m,i; int x;//lưu giá trị a[i] tránh bị ghi đè khi dời chỗ các phần tử. for(int i=1 ; i<n ; i++) { x = a… Read More
  • thuật toán quick sort - sắp xếp nhanh Giải thuật QuickSort sắp xếp dãy a1, a2 ..., aN dựa trên việc phân hoạch dãy ban đầu thành 3 phần : Phần 1: Gồm các phần tử  có giá trị bé hơn x Phần 2: Gồm các phần tử  có giá trị bằng  x Phần 3: Gồm các phần… Read More