Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
4.1 kB
2
Indexable
Never
#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
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? noi ph?n t? này dã d?ng dú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 d? 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 select;
    int n;
    string data[100];
    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;
            a = new int[n];
            NhapMang(a,n);
            break;
        case 2:
            cout<<"\nNhap so luong phan tu n = ";
            cin>>n;
            a = new int[n];
            sinhSo(a,n);
            break;
        case 3:
        	std::ifstream fileInput("D:/dev/input.txt");
			std::vector<int> a;           // m?ng int ch?a các s? nguyên dòng 1
			std::string line;             // dòng 1
			std::getline(std::cin, line); // d?c dòng 1
			std::istringstream iss(line); // t?o 1 string stream t? dòng 1
			for (int n; iss >> n;)        // d?c s? nguyên t? stream vào m?ng a
    		a.push_back(n);
        }
    }
    while(select<=0);
    Menu();
    do {
        cout<<"lua chon cach sap xep (1-5):";
        cin>>select;
        switch(select){
        case 1:selectionSort(a,n);break;
        case 2:bubbleSort(a,n);break;
        case 3:quickSort(a, 0, n-1);break;
    }
    }while(select<=0);
    cout<<"1.In ra man hinh"<<"\n";
    cout<<"2.In ra van ban"<<"\n";
    do {
    	cout<<"chon phuong thuc in ra:";
    	cin>>select;
    	if (select==1)
    	{
    	cout << "Sorted array: \n";
        printArray(a,n); 
        }else{
        	ofstream myfile;
    		myfile.open ("D:/dev/output.txt");
    		myfile << "day so sap xep:";
    		printArray(a,n);
    		myfile.close();
    		return 0;
		}
	}while(select<=0);  	
}