как подсчитать количество перестановок и сравнений, выполняемых при работе?
#include <iostream>
#include <cstdlib>
#include "windows.h"
#include <time.h>
#define N 10
using namespace std;
int main(){
srand(time(NULL));
int array[N];
for (int i = 0; i < N; i++) {
array[i] = 12 + rand();
cout << array[i] << " ";
}
cout << endl;
cout << "Sorted massiv" << endl;
for (int startIndex = 0; startIndex < N - 1; ++startIndex)
{
int smallestIndex = startIndex;
for (int currentIndex = startIndex + 1; currentIndex < N; ++currentIndex)
{
if (array[currentIndex] < array[smallestIndex])
smallestIndex = currentIndex;
cout << array[currentIndex] << " ";
}
swap(array[startIndex], array[smallestIndex]);
cout << endl;
}
for (int index = 0; index < N; ++index)
cout << array[index] << ' ';
return 0;
}
14456 17207 21123 30523 11692 1849 997 12826 14912
17207 21123 30523 11692 1849 6117 12826 14912
21123 30523 11692 14456 6117 12826 14912
30523 11692 14456 17207 12826 14912
21123 14456 17207 12826 14912
14456 17207 30523 14912
17207 30523 14912
30523 21123
21123
{ 30, 50, 20, 10, 40 }
{ 30, 50, 20, 10, 40 }
{ 10, 50, 20, 30, 40 }
{ 10, 50, 20, 30, 40 }
{ 10, 20, 50, 30, 40 }
{ 10, 20, 50, 30, 40 }
{ 10, 20, 30, 50, 40 }
{ 10, 20, 30, 50, 40 }
{ 10, 20, 30, 40, 50 }
{ 10, 20, 30, 40, 50 }
{ 10, 20, 30, 40 50 }
Ответы (1 шт):
#include <iostream>
#include <cstdlib>
#include "windows.h"
#include <time.h>
#define N 10
using namespace std;
int main(){
srand(time(NULL));
int array[N];
for (int i = 0; i < N; i++) {
array[i] = 12 + rand();
cout << array[i] << " ";
}
cout << endl;
cout << "Sorted massiv" << endl;
int swaps = 0, compares = 0;
for (int startIndex = 0; startIndex < N - 1; ++startIndex)
{
int smallestIndex = startIndex;
for (int currentIndex = startIndex + 1; currentIndex < N; ++currentIndex)
{
compares++;
if (array[currentIndex] < array[smallestIndex])
smallestIndex = currentIndex;
cout << array[currentIndex] << " ";
}
swaps++;
swap(array[startIndex], array[smallestIndex]);
cout << endl;
}
for (int index = 0; index < N; ++index)
cout << array[index] << ' ';
cout << "swaps: " << swaps << "\ncompares: " << compares;
return 0;
}
Хотя в нашем универе просили считать swap за 3 перестановки (т.к. перестановка в массиве делается в 3 шага), но это уже на вкус и цвет.
UPD: правки с учетом комментариев
#include <iostream>
#include <cstdlib>
#include <time.h>
#define N 10
using namespace std;
void print(int arr[], int size)
{
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main(){
srand(time(NULL));
int array[N];
for (int i = 0; i < N; i++) {
array[i] = 12 + rand();
cout << array[i] << " ";
}
cout << endl;
cout << "Sorted massiv" << endl;
int swaps = 0, compares = 0;
for (int startIndex = 0; startIndex < N - 1; ++startIndex)
{
int smallestIndex = startIndex;
for (int currentIndex = startIndex + 1; currentIndex < N; ++currentIndex)
{
compares++;
if (array[currentIndex] < array[smallestIndex])
smallestIndex = currentIndex;
}
swaps++;
swap(array[startIndex], array[smallestIndex]);
cout << "swap #" << swaps << ": ";
print(array, N);
}
print(array, N);
cout << "\nswaps: " << swaps << "\ncompares: " << compares;
return 0;
}