Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
3.2 kB
5
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
void Menu() {
	cout <<"1.SelectionSort"<<"\n";
	cout <<"2.BubbleSort"<<"\n";
	cout <<"3.QuickSort"<<"\n";
	cout <<"4.MergeSort"<<"\n";
	cout <<"5.Heapsort"<<"\n";
}
void sinhSo(int *a,int n)
{
    srand(time(NULL));
    for(int i = 0; i < n;i++)
    a[i] = rand();
}

void NhapMang(int a[], int n){
    for(int i = 0; i < n; i++){
        cout<<"\nNhap a["<<i<<"] = ";
        cin>>a[i];
    }
}
 
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
void selectionSort(int arr[], int n)
{
    int i, j, min;
 
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min = i;
        for (j = i+1; j < n; j++)
        if (arr[j] < arr[min])
            min = j;
 
        // Swap the found minimum element with the first element
        swap(&arr[min], &arr[i]);
    }
}
void bubbleSort(int arr[], int n)
{
    int i, j;
    for (i = 0; i < n-1; i++)    
     
    // Last i elements are already in place
    for (j = 0; j < n-i-1; j++)
        if (arr[j] > arr[j+1])
            swap(&arr[j], &arr[j+1]);
}
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int left = low;
    int right = high - 1;
    while(true){
        while(left <= right && arr[left] < pivot) left++;
        while(right >= left && arr[right] > pivot) right--;
        if (left >= right) break;
        swap(arr[left], arr[right]);
        left++;
        right--;
    }
    swap(arr[left], arr[high]);
    return left;
}
 
/* Hàm thực hiện giải thuật quick sort */
void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        /* pi là chỉ số nơi phần tử này đã đứng đúng vị trí
         và là phần tử chia mảng làm 2 mảng con trái & phải */
        int pi = partition(arr, low, high);
 
        // Gọi đệ quy sắp xếp 2 mảng con trái và phải
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
int main()
{
    int *a;
    int choice;
    int select;
    int n;
    cout <<"1.Nhap tu ban phim"<<"\n";
	cout <<"2.Sinh n so ngau nhien"<<"\n";
	cout <<"3.Nhap tu van ban"<<"\n";
    do {
        cout<<"Chon cach nhap so (1-3):";
        cin>>select;
    switch(select){
        case 1:
        cout<<"\nNhap so luong phan tu n = ";
        cin>>n;
        NhapMang(a,n);
        break;
        case 2:
               cout<<"\nNhap so luong phan tu n = ";
               cin>>n;
               sinhSo(a,n);
               break;
        }
    }
    while(select<=0);
    Menu();
    do {
        cout<<"lua chon cach sap xep (1-5):";
        cin>>choice;
    switch(choice){
        case 1:selectionSort(a,n);break;
        case 2:bubbleSort(a,n);break;
        case 3:quickSort(a, 0, n-1);break;
    }
    cout << "Sorted array: \n";
    printArray(a,n);
    }while(choice<=0);
    return 0;
}