BÀI 1 SẮP XẾP DÙNG THUẬT TOÁN SELECTION SORT
/* Sap xep chon - Selection Sort*/
#include <stdio.h>
/*Khai bao*/
typedef int keytype;
typedef float othertype;
typedef struct {
keytype key;
othertype otherfields;
} recordtype;
/*Doi cho*/
void Swap(recordtype &x, recordtype &y){
recordtype temp;
temp = x;
x = y;
y = temp;
}
/*Selection Sort*/
void SelectionSort(recordtype a[], int n){
int i,j, lowindex;
keytype lowkey;
for (i=0; i<=n-2; i++){
lowkey = a[i].key;
lowindex = i;
for (j=i+1; j<=n-1; j++){
if (a[j].key < lowkey){
lowkey = a[j].key;
lowindex = j;
}
}
Swap(a[i],a[lowindex]);
}
}
main(){
int n,i;
recordtype a[100];
FILE* file = fopen("dayso.inp", "r");
fscanf(file, "%d",&n);
for (i = 0; i <= n-1; i++) {
fscanf(file, "%d", &a[i]);
}
printf("\n");
printf("Thuat toan Selection_Sort\n\n");
printf("Day so truoc khi sap xep : ");
for(i=0; i<=n-1; i++){
printf("%d ",a[i]);
}
printf("\n\n");
SelectionSort(a,n);
printf("Day so sau khi sap xep : ");
for(i=0; i<=n-1; i++){
printf("%d ",a[i]);
}
printf("\n");
}
BÀI 2: SẮP XẾP DÙNG THUẬT TOÁN QUICK SORT
/* Sap xep nhanh - QuickSort*/
#include <stdio.h>
/*Khai bao*/
typedef int keytype;
typedef float othertype;
typedef struct {
keytype key;
othertype otherfields;
} recordtype;
/*Doi cho*/
void Swap(recordtype &x, recordtype &y){
recordtype temp;
temp = x;
x = y;
y = temp;
}
/*----------QuickSort----------*/
/*FindPivot*/
int FindPivot(recordtype a[], int i, int j){
keytype firstkey;
int k;
k = i+1;
firstkey = a[i].key;
while((k<=j) && (a[k].key == firstkey)) k++;
if (k>j) return -1;
if (a[k].key > firstkey) return k;
return i;
}
/*Partition*/
int Partition(recordtype a[], int i, int j, keytype pivot){
int L,R;
L = i;
R = j;
while (L<=R){
while (a[L].key < pivot) L++;
while (a[R].key >= pivot) R--;
if (L<R) Swap(a[L],a[R]);
}
return L;
}
void QuickSort(recordtype a[], int i, int j){
keytype pivot;
int pivotindex, k;
pivotindex = FindPivot(a,i,j);
if (pivotindex != -1){
pivot = a[pivotindex].key;
k = Partition(a,i,j,pivot);
QuickSort(a,i,k-1);
QuickSort(a,k,j);
}
}
main(){
int n,i;
recordtype a[100];
FILE* file = fopen("dayso.inp", "r");
fscanf(file, "%d",&n);
for (i = 0; i <= n-1; i++) {
fscanf(file, "%d", &a[i]);
}
printf("\n");
printf("Thuat toan Quick_Sort\n\n");
printf("Day so truoc khi sap xep : ");
for(i=0; i<=n-1; i++){
printf("%d ",a[i]);
}
printf("\n\n");
QuickSort(a,0,n-1);
printf("Day so sau khi sap xep : ");
for(i=0; i<=n-1; i++){
printf("%d ",a[i]);
}
printf("\n");
}
BÀI 3 XẮP SẾP DÙNG THUẬT TOÁN HEAP SORT
/* Sap xep vun dong - Heap Sort*/
#include <stdio.h>
/*Khai bao*/
typedef int keytype;
typedef float othertype;
typedef struct {
keytype key;
othertype otherfields;
} recordtype;
/*Doi cho*/
void Swap(recordtype &x, recordtype &y){
recordtype temp;
temp = x;
x = y;
y = temp;
}
/*----------HeapSort----------*/
/*PushDown*/
void PushDown(recordtype a[], int first, int last){
int r = first;
while (r <= (last-1)/2)
if (last == 2*r+1){
if (a[r].key > a[last].key) Swap(a[r],a[last]);
r = last;
}
else
if ((a[r].key>a[2*r+1].key) && (a[2*r+1].key < a[2*r+2].key)){
Swap(a[r],a[2*r+1]);
r = 2*r+1;
}
else
if ((a[r].key>a[2*r+2].key) && (a[2*r+2].key < a[2*r+1].key)){
Swap(a[r],a[2*r+2]);
r = 2*r+2;
}
else r = last;
}
/*HeapSort*/
void HeapSort(recordtype a[], int n){
int i;
for (i = (n-2)/2; i>=0; i--)
PushDown(a,i,n-1);
for (i= n-1; i>=2; i--){
Swap(a[0],a[i]);
PushDown(a,0,i-1);
}
Swap(a[0],a[1]);
}
main(){
int n, i;
recordtype a[100];
FILE* file = fopen("dayso.inp", "r");
fscanf(file, "%d",&n);
for (i = 0; i <= n-1; i++) {
fscanf(file, "%d", &a[i]);
}
HeapSort(a,n);
printf("Day sau khi sap xep theo kieu Heap_Sort la:\n\n");
for(i=0; i<=n-1; i++){
printf("%d ",a[i]);
}
}