1Лабораториялық жұмыс №4 Біріктіру арқылы сұрыптау

1Лабораториялық жұмыс №4
Біріктіру арқылы сұрыптау

Біріктіру арқылы сұрыптау (ағылш. merge sort) — белгілі бір ретпен тізімдерді (немесе элементтерге тек дәйекті түрде қол жеткізуге болатын басқа деректер құрылымдарын, мысалы-ағындарды) реттейтін сұрыптау алгоритмі. Бұл сұрыптау «Разделяй и властвуй» принципін қолданудың жақсы мысалы болып табылады. Алдымен тапсырма бірнеше кіші тапсырмаларға бөлінеді. Содан кейін бұл тапсырмалар рекурсив арқылы немесе олардың мөлшері жеткілікті кішкентай болса, тікелей шешіледі. Соңында, олардың шешімдері біріктіріліп, бастапқы мәселенің шешімі алынады. Орындалу алгоритмі келесідей:

1. 
   Массив рекурсивті түрде екіге бөлінеді және жартысының әрқайсысы келесі ішкі массивтің өлшемі бір болғанша бөлінеді;
   
2. 
   Әрі қарай, біріктіру деп аталатын алгоритм операциясы орындалады. Екі бірлік массив жалпы алынған массивке біріктіріледі, олардың әрқайсысынан кішірек элемент таңдалады (өсу бойынша сұрыптау) және алынған массивтің бос сол жақ ұяшығына жазылады. Осыдан кейін алынған екі массивтен үшінші жалпы сұрыпталған массив жиналады. Егер массивтердің біреуі аяқталса, екіншісінің элементтері жиналатын массивке қосылады;
   
3. 
   Біріктіру операциясының соңында элементтер алынған массивтен түпнұсқаға қайта жазылады.
   

#include
using namespace std;
void merge(int *,int, int , int );
void merge_sort(int *arr, int low, int high)
{
int mid;
if (low < high){
mid=(low+high)/2;
merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
merge(arr,low,high,mid);
}
}
// Merge sort
void merge(int *arr, int low, int high, int mid)
{
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
c[k] = arr[i];
k++;
i++;
}
else {
c[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) {
c[k] = arr[i];
k++;
i++;
}
while (j <= high) {
c[k] = arr[j];
k++;
j++;
}
for (i = low; i < k; i++) {
arr[i] = c[i];
}
}
int main()
{
int myarray[30], num;
cout<<"Enter number of elements to be sorted:";
cin>>num;
cout<<"Enter "<for (int i = 0; i < num; i++) {
cin>>myarray[i];
}
merge_sort(myarray, 0, num-1);
cout<<"Sorted array\n";
for (int i = 0; i < num; i++)
{
cout<}
}
Тапсырма:

1. 
   Merge sort сұрыптау әдісінің күрделілігін анықтаныз және алгоритмін түсіндірініз.
   

#include
using namespace std;
void merge(int*, int, int, int);
void merge_sort(int* arr, int low, int high)
{
int mid;
if (low < high) {
mid = (low + high) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid + 1, high);
merge(arr, low, high, mid);
}
}
// Merge sort
void merge(int* arr, int low, int high, int mid)
{
int i, j, k, c[50];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
c[k] = arr[i];
k++;
i++;
}
else {
c[k] = arr[j];
k++;
j++;
}
}
while (i <= mid) {
c[k] = arr[i];
k++;
i++;
}
while (j <= high) {
c[k] = arr[j];
k++;
j++;
}
for (i = low; i < k; i++) {
arr[i] = c[i];
}
}
int main()
{
srand(time(NULL);
int myarray[30], num;
cout << "Enter number of elements to be sorted:";
cin >> num;
cout << "Enter " << num << " elements to be sorted:";
for (int i = 0; i < num; i++) {
myarray[i] = rand() % 10;
}
merge_sort(myarray, 0, num - 1);
cout << "Sorted array\n";
for (int i = 0; i < num; i++)
{
cout << myarray[i] << "\t";
}
}

2. 
   Сізге қандай да бір сөз берілген. Осы сөзге Merge sort сұрыптау әдісін қолданып алфавит боыйнша сұрыптаныз.
   

#include
#include
#include
using namespace std;
void m(int*, int, int, int);
void mS(int* a, int b, int c)
{
int d;
if (b < c) {
d = (b + c) / 2;
mS(a, b, d);
mS(a, d + 1, c);
m(a, b, c, d);
}
}
void m(int* a, int b, int c, int d)
{
int i, j, k, h[50];
i = b;
k = b;
j = d + 1;
while (i <= d && j <= c) {
if (a[i] < a[j]) {
h[k] = a[i];
k++;
i++;
}
else {
h[k] = a[j];
k++;
j++;
}
}
while (i <= d) {
h[k] = a[i];
k++;
i++;
}
while (j <= c) {
h[k] = a[j];
k++;
j++;
}
for (i = b; i < k; i++) {
a[i] = h[i];
}
}
int main() {
string a;
getline(cin, a);
int b = a.length(), c[b];
for (int i = 0; i < b; i++) {
c[i] = a[i];
}
mS(c, 0, b - 1);
cout << "\n";
for (int i = 0; i < b; i++)
{
a[i] = c[i];
cout << a[i] << " ";
}
}