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

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; } }