Selection Sort in C++

Question

I wanted feedback/review on my implementation of a selection sort in c++ (for ints only, no templates). This is my first attempt in c++ making anything beyond simple projects/hello world!

Q: Should my for loops use uniform initialization like for(int i { 0 }; ... ?

Q: Should everything else use uniform initialization like I have below?

Q: I read selection is n^2 however I don't loop every field, I loop through only the unsorted portion, is this still n^2 or better?

#include <iostream>

void selectionSort(int arr[], int start, int size);
void printArr(int arr[], int size);

int main()
{
  const int size { 11 };
  int arr[size] { 1,9,2,3,4,1,6,6,5,3,8 };
  selectionSort(arr, 0, size);
  return 0;
}

void selectionSort(int arr[], int start, int size)
{
  printArr(arr, size);

  for (int i = start; i < size; i++)
  {
    int min_pos { i };
    for (int x = i; x < size; x++)
    {
      if (arr[x] < arr[min_pos])
      {
        min_pos = x;
      }
    }
    int temp { arr[i] };
    arr[i] = arr[min_pos];
    arr[min_pos] = temp;
    printArr(arr, size);
  }

  printArr(arr, size);
}

void printArr(int arr[], int size)
{
  for (int i = 0; i < size; i++)
  {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
}

output:

1 9 2 3 4 1 6 6 5 3 8
1 9 2 3 4 1 6 6 5 3 8
1 1 2 3 4 9 6 6 5 3 8
1 1 2 3 4 9 6 6 5 3 8
1 1 2 3 4 9 6 6 5 3 8
1 1 2 3 3 9 6 6 5 4 8
1 1 2 3 3 4 6 6 5 9 8
1 1 2 3 3 4 5 6 6 9 8
1 1 2 3 3 4 5 6 6 9 8
1 1 2 3 3 4 5 6 6 9 8
1 1 2 3 3 4 5 6 6 8 9
1 1 2 3 3 4 5 6 6 8 9
1 1 2 3 3 4 5 6 6 8 9

Answer 1

It is advisable to use the standard library as much as possible. I'll give you an idea how to implement selection sort using standard functions below. Consider the following.

#include <iostream>
#include <algorithm>
#include <vector>

void selection_sort(std::vector<int>& v)
{
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        std::iter_swap(it, std::min_element(it, v.end()));
    }
}

int main()
{
    std::vector<int> v = { 9, 8, 4, 0, 19, 271, 1 };
    selection_sort(v);

    for (auto elem : v)
        std::cout << elem << " ";
}

I would argue the above is actually more readable than what you have wrote, since the functions are well-named and the logic easy to follow. So what the selection_sort function does is that it iterates through the vector of integers. It swaps each element with the smallest element in the remaining array, just like we want it to.

Answer 2

Style

At the moment, this is C with iostream. The style obliterates the point in using C++ at all.

Code Review

• Almost complete absence of standard library

  The code does not leverage the functionality standard library provides. On top of that, the code is not better in any ways than standard library functionality

• Using int for size of objects in memory

  Indexable memory is very big nowadays. int is guaranteed to be only 16 bits, so it might not be enough to index all of the available memory on the system. Use std::size_t for that.

• C style swapping

  C++ has std::swap() located in <utility>. It will probably be as good as your version, if not better (it might invoke some assembly).

• Using std::endl

  std::endl does not only put a newline, but also flushes the buffer. Flushing is a very expensive operation, and can hinder performance of the code in tight loops.

What is done right

• No using namespace std

  This is good step forward. Do not use it, in any IDE/text editor code highlighting and completion will be available, if not, find a plugin for your text editor. By grabbing everything in std, you will overwhelm the ability of the IDE/text editor to give you real-time code completion suggestions.

• Uniform initialization

  Using uniform initialization avoids all of the vexing parse issues. Do note though, that sometimes they might invoke std::initializer_list constructor, which might not be what you need.

tl;dr

Use Standard library. Use concepts and idioms. Any decent C++ programmer knows that to reimplement standard library one must have a very good reason to do so.