Tuesday, 3 November 2020

Sorting revisited with C++17

Let's start with the original Bubble Sort

I posted this back in 2014, I have no idea if it's good code or not
but it did serve its purpose which was to demonstrate how the bubble
sort works in a simple enough fashion. 

char** bsort(const unsigned int count, char** values) {
  unsigned int i, j, moveCount = 0, swapCount = 0;
  char* tmp;
  printf("sorting a list of %i values\n", count);
  for(j=count; j > 0; j--) {
    for(i = 0; i < j - 1; i++) {
      printf("\n%i:\tcomparing %s to %s ", moveCount++, values[i], values[i+1]);
      if(strcmp(values[i], values[i + 1]) > 0) {
        swap((const char**) values, (const unsigned int) i);
        ++swapCount;
      }
    }
  }
  printf("\nsorting %i items required %i swaps",
    count, swapCount);
  return values;
}

/**
 * Swap the string at values[idx] with values[idx+1]
 */
void swap(const char** values, const unsigned int idx) {
  const char* tmp = (const char*)values[idx];
  values[idx] = values[idx + 1];
  values[idx + 1] = tmp;
  printf("swap made");
}

 

So I revisited this code and made it a little more C++17, again I don't
know if this is the best way to write it, but it does seem clearer to read

std::vector<int> bubble(std::vector<int> list) {
    int moveCount = 0, swapCount = 0;

    std::cout << "sorting a list of " << list.size() << "values" << std::endl;

    for (int j = list.size() - 1; j > 0; j--) {

        for (int i = 0; i < j; i++) {

            std::cout << moveCount++ <<
":\tcomparing " << list[i] <<
                " to "
<< list[i + 1] << std::endl;

            if
(list[i] > list[i + 1]) {

                std::swap(list[i], list[i + 1]);

                swapCount++;

            }

        }

    }

    std::cout << "\nsorting " << list.size() << " items required " <<

        swapCount << " swaps" << std::endl;

    return list;

}

int main(const int argc, char** argv) {
std::vector<int> sortlist = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
for (auto i: bubble(sortlist)) {
std::cout << i << " ";
}
}
































No comments:

Post a Comment