Untitled

unknown
c_cpp
2 years ago
4.1 kB
2
Indexable
Never
```#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
using namespace std;
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);
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);
}```