Number of sort operations

[Frogoten]

Hi!

I need help with displaying the number of sort operations

I will be very grateful if you help me!

#include <iostream> 
using namespace std; 
  
// A function to sort the algorithm using gnome sort 
void gnomeSort(int arr[], int n) 
{ 
    int index = 0; 
  
    while (index < n) { 
        if (index == 0) 
            index++; 
        if (arr[index] >= arr[index - 1]) 
            index++; 
        else { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 
    } 
    return; 
} 
  
// A utility function ot print an array of size n 
void printArray(int arr[], int n) 
{ 
    cout << "Sorted sequence after Gnome sort: "; 
    for (int i = 0; i < n; i++) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
  
// Driver program to test above functions. 
int main() 
{ 
    int arr[] = { 34, 2, 10, -9 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    gnomeSort(arr, n); 
    printArray(arr, n); 
  
    return (0); 
}

[keskiverto]

What is a "sort operation"? Answer to that is what you should count.

[Frogoten]

Sorry, I`m not an English speaker.

I meant how many operations sorting does with an array

[dhayden]

Usually a sort operation is expressed in terms of the number of comparisons. To do this:
- change gnomeSort to return the number of comparisons.
- add a new local variable ("count"?) to gnomeSort. Initialize it to zero and increment it each time you do a compare 2 elements (line 12).
- return "count" at line 19.
- Print the returned value at line 37.

[keskiverto]

What is "an operation"?

Is this one operation?

        if (arr[index] >= arr[index - 1]) 
            index++; 
        else { 
            swap(arr[index], arr[index - 1]); 
            index--; 
        } 

Are are these two separately counted operations?
[index] >= arr[index - 1] and swap(arr[index], arr[index - 1]);

[Frogoten]

I meant the complexity of sorting

[deleted account xyzzy]

Are you trying to count the number of times your while block loops?

#include <iostream>
#include <algorithm> // std::swap

int gnomeSort(int arr[], int n)
{
   int num_sorts { };

   int index     { };

   while (index < n)
   {
      if (index == 0)
      {
         index++;
      }

      if (arr[index] >= arr[index - 1])
      {
         index++;
      }
      else
      {
         std::swap(arr[index], arr[index - 1]);
         index--;
      }

      num_sorts++;
   }

   return num_sorts;
}

void printArray(int arr[], int n)
{
   for (int i { }; i < n; i++)
   {
      std::cout << arr[i] << " ";
   }
   std::cout << '\n';
}

int main()
{
   int arr[] { 34, 2, 10, -9 };
   int n     { sizeof(arr) / sizeof(arr[0]) };

   std::cout << "Sequence before Gnome sort:\n";
   printArray(arr, n);
   std::cout << '\n';

   int num_sorts { gnomeSort(arr, n) };

   std::cout << "Sequence after Gnome sort:\n";
   printArray(arr, n);
   std::cout << '\n';

   std::cout << "Number of sort operations needed: " << num_sorts << '\n';
}

Sequence before Gnome sort:
34 2 10 -9

Sequence after Gnome sort:
-9 2 10 34

Number of sort operations needed: 11

[dutch]

You can count various things: comparisons, swaps, iterations.

#include <iostream>
using namespace std;

struct Counts {
    int comparisons;
    int swaps;
    int loops;
} counts = { 0, 0, 0 };

void gnomeSort(int* arr, int n) {
    for (int index = 1; index < n; ) {
        if (arr[index] >= arr[index - 1]) {
            ++counts.comparisons;
            ++index;
        }
        else {
            ++counts.swaps;
            swap(arr[index], arr[index - 1]);
            if (index > 1) --index;
        }
        ++counts.loops;
    }
}

void printArray(int* a, int n) {
    while (n--) cout << *a++ << ' ';
    cout << '\n';
}

int main(int argc, char** argv) {
    int* a = nullptr;
    int size = 0;
    if (argc > 1) {
        size = argc - 1;
        a = new int[size];
        for (auto b = a; *++argv; ) *b++ = stoi(*argv);
    }
    else {
        size = 10;
        a = new int[size];
        auto b = a;
        for (auto x: { 9, 3, 6, 8, 0, 1, 4, 7, 2, 5 }) *b++ = x;
    }

    gnomeSort(a, size);
    cout << "After : ";
    printArray(a, size);
    cout << "comparisons: " << counts.comparisons << '\n';
    cout << "swaps: " << counts.swaps << '\n';
    cout << "loops: " << counts.loops << '\n';
}

$ ./a.out 9 8 7 6 5 4 3 2 1 0
After: 0 1 2 3 4 5 6 7 8 9 
comparisons: 45
swaps: 45
loops: 90
$ ./a.out 0 1 2 3 4 5 6 7 8 9
After: 0 1 2 3 4 5 6 7 8 9 
comparisons: 9
swaps: 0
loops: 9
$ ./a.out 9 3 6 8 0 1 4 7 2 5
After: 0 1 2 3 4 5 6 7 8 9 
comparisons: 33
swaps: 26
loops: 59