Bài giải - code các thuật toán sắp xếp | Trường Đại học CNTT Thành Phố Hồ Chí Minh

Bài giải - code các thuật toán sắp xếp | Trường Đại học CNTT Thành Phố Hồ Chí Minh được được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn sinh viên cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!

33 17 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Nhập môn lập trình

Trường: Trường Đại học Công nghệ Thông tin, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

11 trang 7 tháng trước

Tác giả:

Profile Mai Nguyệt
lOMoARcPSD| 40425501
CÁC THUẬT TOÁN SẮP XẾP
1. Thuật toán Interchange Sort
void InterchangeSort(int a[], int N )
{ int i, j;
for (i = 0 ; i<N-1 ; i++)
for (j =i+1; j < N ; j++)
if(a[j ]< a[i])
Swap(a[i], a[j]);
}
2. Thuật toán Selection Sort
void SelectionSort(int a[],int n)
{
int min,i,j; for
(i=0; i<n-1 ; i++)
{
min = i;
for(j = i+1; j < n ; j++)
if (a[j ] < a[min])
min = j;
Swap(a[min],a[i]);
}
}
3. Thuật toán Bubble Sort
void BubbleSort(int a[],int n)
{
int i, j;
lOMoARcPSD| 40425501
}
for (i = 0 ; i<n-1 ; i++)
for (j =n-1; j >i ; j --)
if(a[j]< a[j-1])
Swap(a[j], a[j-1]);
4. Thuật toán Insertion Sort
void InsertionSort(int a[],int n)
{
int pos,key;
for(int i=1;i<n;i++)
{
key = a[i];
pos = i - 1;
while((pos >= 0) && (a[pos] > key))
{
a[pos + 1] = a[pos];
pos--;
}
a[pos+1] = key;
}
}
5. Thuật toán Binary Insertion Sort
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++)
{
lOMoARcPSD| 40425501
x = a[i]; l = 0;
r = i-1;
while(l<=r) // tìm vị trí chèn x
{
m = (l+r)/2;
// tìm vị trí thích hợp m
if(x < a[m]) r = m-1; else
l = m+1;
}
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j];// dời các phần tử sẽ ứng sau x
a[l] = x; // chèn x vào dãy
}
}
lOMoARcPSD| 40425501
6. Thuật toán Shaker Sort
void ShakerSort(int a[], int n)
{
int i, j, left, right,
k; left = 0; right
= n - 1; k = n - 1;
while( left < right )
{
for ( i = right; i > left; i--)
{
if ( a[i] < a [i - 1] )
{
swap(a[i], a[i -1]);
k = i;
}
}
left = k;
for ( j = left; j < right; j++)
{
if ( a[j] > a[j + 1] )
{
swap(a[j], a[j + 1]);
k = j;
}
} right =
k;
}
}
lOMoARcPSD| 40425501
7. Thuật toán Shell Sort
void ShellSort(int a[],int n)
{
int h[10],k; // K=3 , h={5,3,1}
cout<<"\nNhap vao so phan tu cua mang h :";
cin>>k;
for(int i=0;i<k;i++)
{
printf("nhap vao h[%d] :",i);
scanf("%d",&h[i]);
}
int step,i,j, x,len; for (step = 0 ; step <k; step
++)
{
len = h[step];
{
}
for (i = len; i <n; i++)
x = a[i];
j = i-len;
while ((x<a[j])&&(j>=0))
{
a[j+len] = a[j];
j = j - len;
}
a[j+len] = x;
}
}
lOMoARcPSD| 40425501
8. Thuật toán Heap Sort
void shift(int a[],int l,int r)
{
int x,i,j;
i=l;
j=2*i+1;
x=a[i];
while(j<=r)
{
if(j<r)
if(a[j]<a[j+1]) //tim phan tu lon nhat a[j] va a[j+1]
j++; //luu chi so cua phan tu nho nhat trong hai phan tu
if(a[j]<=x) return; else {
a[i]=a[j];
a[j]=x;
lOMoARcPSD| 40425501
i=j;
j=2*i+1;
x=a[i];
}
}
}
void CreateHeap(int a[],int n)
{ int l;
l=n/2-1;
while(l>=0)
{
shift(a,l,n-1);
l=l-1;
}
}
void HeapSort(int a[],int n)
{
int r;
CreateHeap(a,n);
r=n-1;
while(r>0)
{
swap(a[0],a[r]);//a[0] la nút gốc
r--;
if(r>0)
shift(a,0,r);
}
}
lOMoARcPSD| 40425501
9. Thuật toán Quick Sort
void QuickSort(int a[], int left, int right)
{
int i, j, x; x =
a[(left+right)/2]; i =
left; j = right;
while(i < j)
{
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j)
{
Swap(a[i],a[j]);
i++ ;
j--;
}
}
if(left<j)
QuickSort(a, left, j);
if(i<right)
QuickSort(a, i, right);
}
lOMoARcPSD| 40425501
10. Thuật toán Merge Sort
void Merge (int a[], int l, int m, int r)
{
int i, length;
int l_end = m - 1;
i = l;
length = r - l;
lOMoARcPSD| 40425501
int temp[100];
while(l <= l_end && m <= r)
{ if (a[l] <= a[m]) {
temp[i++] = a[l++];
} else {
temp[i++] = a[m++];
}
}
while(l <= l_end) {
temp[i++] = a[l++];
}
while(m <= r) {
temp[i++] = a[m++];
}
for (i = 0; i <= length; i++, r--) {
a[r] = temp[r];
}
}
void MergeSort(int a[], int l, int r)
{ int m; if(l
< r) { m = (l
+ r) / 2;
MergeSort(a, l, m);
MergeSort(a, m + 1, r);
Merge(a, l, m + 1, r);
lOMoARcPSD| 40425501
}
}
11. Thuật toán Radix Sort
void RadixSort(int a[],int n)
{
int i,b[100],m=0,exp=1;
for(i=0;i<n;i++)
{
if(a[i]>m)
m=a[i];
}
while(m/exp>0)
{
int bucket[10]={0};
for(i=0;i<n;i++)
bucket[a[i]/exp%10]++;
for(i=1;i<10;i++)
bucket[i]+=bucket[i-1]; for(i=n-
1;i>=0;i--)
b[--bucket[a[i]/exp%10]]=a[i];
for(i=0;i<n;i++)
a[i]=b[i];
exp*=10;
}
}
| 1/11
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

lOMoAR cPSD| 40425501
CÁC THUẬT TOÁN SẮP XẾP
1. Thuật toán Interchange Sort
void InterchangeSort(int a[], int N ) { int i, j;
for (i = 0 ; i for (j =i+1; j < N ; j++) if(a[j ]< a[i]) Swap(a[i], a[j]); }
2. Thuật toán Selection Sort
void SelectionSort(int a[],int n) { int min,i,j; for (i=0; i { min = i; for(j = i+1; j < n ; j++) if (a[j ] < a[min]) min = j; Swap(a[min],a[i]); } }
3. Thuật toán Bubble Sort
void BubbleSort(int a[],int n) { int i, j; lOMoAR cPSD| 40425501 for (i = 0 ; i for (j =n-1; j >i ; j --) } if(a[j]< a[j-1]) Swap(a[j], a[j-1]);
4. Thuật toán Insertion Sort
void InsertionSort(int a[],int n) { int pos,key; for(int i=1;i { key = a[i]; pos = i - 1;
while((pos >= 0) && (a[pos] > key)) { a[pos + 1] = a[pos]; pos--; } a[pos+1] = key; } }
5. Thuật toán Binary Insertion Sort
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 { lOMoAR cPSD| 40425501 x = a[i]; l = 0; r = i-1;
while(l<=r) // tìm vị trí chèn x { m = (l+r)/2;
// tìm vị trí thích hợp m if(x < a[m]) r = m-1; else l = m+1; }
for(int j = i-1 ; j >=l ; j--)
a[j+1] = a[j];// dời các phần tử sẽ ứng sau x
a[l] = x; // chèn x vào dãy } } lOMoAR cPSD| 40425501
6. Thuật toán Shaker Sort
void ShakerSort(int a[], int n) { int i, j, left, right, k; left = 0; right = n - 1; k = n - 1; while( left < right ) {
for ( i = right; i > left; i--) { if ( a[i] < a [i - 1] ) { swap(a[i], a[i -1]); k = i; } } left = k;
for ( j = left; j < right; j++) { if ( a[j] > a[j + 1] ) { swap(a[j], a[j + 1]); k = j; } } right = k; } } lOMoAR cPSD| 40425501
7. Thuật toán Shell Sort void ShellSort(int a[],int n) {
int h[10],k; // K=3 , h={5,3,1}
cout<<"\nNhap vao so phan tu cua mang h :"; cin>>k; for(int i=0;i { printf("nhap vao h[%d] :",i); scanf("%d",&h[i]); }
int step,i,j, x,len; for (step = 0 ; step ++) { len = h[step]; for (i = len; i x = a[i]; j = i-len; { while ((x=0)) { a[j+len] = a[j]; j = j - len; } a[j+len] = x; } } } lOMoAR cPSD| 40425501
8. Thuật toán Heap Sort
void shift(int a[],int l,int r) { int x,i,j; i=l; j=2*i+1; x=a[i]; while(j<=r) {
if(j if(a[j]j++; //luu chi so cua phan tu nho nhat trong hai phan tu if(a[j]<=x) return; else { a[i]=a[j]; a[j]=x; lOMoAR cPSD| 40425501 i=j; j=2*i+1; x=a[i]; } } }
void CreateHeap(int a[],int n) { int l; l=n/2-1; while(l>=0) { shift(a,l,n-1); l=l-1; } } void HeapSort(int a[],int n) { int r; CreateHeap(a,n); r=n-1; while(r>0) {
swap(a[0],a[r]);//a[0] la nút gốc r--; if(r>0) shift(a,0,r); } } lOMoAR cPSD| 40425501
9. Thuật toán Quick Sort
void QuickSort(int a[], int left, int right) { int i, j, x; x = a[(left+right)/2]; i = left; j = right; while(i < j) { while(a[i] < x) i++; while(a[j] > x) j--; if(i <= j) { Swap(a[i],a[j]); i++ ; j--; } } if(left QuickSort(a, left, j); if(i QuickSort(a, i, right); } lOMoAR cPSD| 40425501
10. Thuật toán Merge Sort
void Merge (int a[], int l, int m, int r) { int i, length; int l_end = m - 1; i = l; length = r - l; lOMoAR cPSD| 40425501 int temp[100];
while(l <= l_end && m <= r) { if (a[l] <= a[m]) { temp[i++] = a[l++]; } else { temp[i++] = a[m++]; } } while(l <= l_end) { temp[i++] = a[l++]; } while(m <= r) { temp[i++] = a[m++]; }
for (i = 0; i <= length; i++, r--) { a[r] = temp[r]; } }
void MergeSort(int a[], int l, int r) { int m; if(l < r) { m = (l + r) / 2; MergeSort(a, l, m); MergeSort(a, m + 1, r); Merge(a, l, m + 1, r); lOMoAR cPSD| 40425501 } }
11. Thuật toán Radix Sort void RadixSort(int a[],int n) { int i,b[100],m=0,exp=1; for(i=0;i { if(a[i]>m) m=a[i]; } while(m/exp>0) { int bucket[10]={0}; for(i=0;i bucket[a[i]/exp%10]++; for(i=1;i<10;i++) bucket[i]+=bucket[i-1]; for(i=n- 1;i>=0;i--)
b[--bucket[a[i]/exp%10]]=a[i]; for(i=0;i a[i]=b[i]; exp*=10; } }