# 6.4 — Sorting an array using selection sort

A case for sorting

Sorting an array is the process of arranging all of the elements in the array in a particular order. There are many different cases in which sorting an array can be useful. For example, your email program generally displays emails in order of time received, because more recent emails are typically considered more relevant. When you go to your contact list, the names are typically in alphabetical order, because it’s easier to find the name you are looking for that way. Both of these presentations involve sorting data before presentation.

Sorting an array can make searching an array more efficient, not only for humans, but also for computers. For example, consider the case where we want to know whether a name appears in a list of names. In order to see whether a name was on the list, we’d have to check every element in the array to see if the name appears. For an array with many elements, searching through them all can be expensive.

However, now assume our array of names is sorted alphabetically. In this case, we only need to search up to the point where we encounter a name that is alphabetically greater than the one we are looking for. At that point, if we haven’t found the name, we know it doesn’t exist in the rest of the array, because all of the names we haven’t looked at in the array are guaranteed to be alphabetically greater!

It turns out that there are even better algorithms to search sorted arrays. Using a simple algorithm, we can search a sorted array containing 1,000,000 elements using only 20 comparisons! The downside is, of course, that sorting an array is comparatively expensive, and it often isn’t worth sorting an array in order to make searching fast unless you’re going to be searching it many times.

In some cases, sorting an array can make searching unnecessary. Consider another example where we want to find the best test score. If the array is unsorted, we have to look through every element in the array to find the greatest test score. If the list is sorted, the best test score will be in the first or last position (depending on whether we sorted in ascending or descending order), so we don’t need to search at all!

How sorting works

Sorting is generally performed by repeatedly comparing pairs of array elements, and swapping them if they meet some predefined criteria. The order in which these elements are compared differs depending on which sorting algorithm is used. The criteria depends on how the list will be sorted (e.g. in ascending or descending order).

To swap two elements, we can use the std::swap() function from the C++ standard library, which is defined in the algorithm header. For efficiency reasons, std::swap() was moved to the utility header in C++11.

This program prints:

```Before swap: x = 2, y = 4
After swap:  x = 4, y = 2
```

Note that after the swap, the values of x and y have been interchanged!

Selection sort

There are many ways to sort an array. Selection sort is probably the easiest sort to understand, which makes it a good candidate for teaching even though it is one of the slower sorts.

Selection sort performs the following steps to sort an array from smallest to largest:
1) Starting at array index 0, search the entire array to find the smallest value
2) Swap the smallest value found in the array with the value at index 0
3) Repeat steps 1 & 2 starting from the next index

In other words, we’re going to find the smallest element in the array, and swap it into the first position. Then we’re going to find the next smallest element, and swap it into the second position. This process will be repeated until we run out of elements.

Here is an example of this algorithm working on 5 elements. Let’s start with a sample array:

{ 30, 50, 20, 10, 40 }

First, we find the smallest element, starting from index 0:

{ 30, 50, 20, 10, 40 }

We then swap this with the element at index 0:

{ 10, 50, 20, 30, 40 }

Now that the first element is sorted, we can ignore it. Now, we find the smallest element, starting from index 1:

{ 10, 50, 20, 30, 40 }

And swap it with the element in index 1:

{ 10, 20, 50, 30, 40 }

Now we can ignore the first two elements. Find the smallest element starting at index 2:

{ 10, 20, 50, 30, 40 }

And swap it with the element in index 2:

{ 10, 20, 30, 50, 40 }

Find the smallest element starting at index 3:

{ 10, 20, 30, 50, 40 }

And swap it with the element in index 3:

{ 10, 20, 30, 40, 50 }

Finally, find the smallest element starting at index 4:

{ 10, 20, 30, 40, 50 }

And swap it with the element in index 4 (which doesn’t do anything):

{ 10, 20, 30, 40 50 }

Done!

{ 10, 20, 30, 40, 50 }

Note that the last comparison will always be with itself (which is redundant), so we can actually stop 1 element before the end of the array.

Selection sort in C++

Here’s how this algorithm is implemented in C++:

The most confusing part of this algorithm is the loop inside of another loop (called a nested loop). The outside loop (startIndex) iterates through each element one by one. For each iteration of the outer loop, the inner loop (currentIndex) is used to find the smallest element in the remaining array (starting from startIndex+1). smallestIndex keeps track of the index of the smallest element found by the inner loop. Then smallestIndex is swapped with startIndex. Finally, the outer loop (startIndex) advances one element, and the process is repeated.

Hint: If you’re having trouble figuring out how the above program works, it can be helpful to work through a sample case on a piece of paper. Write the starting (unsorted) array elements horizontally at the top of the paper. Draw arrows indicating which elements startIndex, currentIndex, and smallestIndex are indexing. Manually trace through the program and redraw the arrows as the indices change. For each iteration of the outer loop, start a new line showing the current state of the array.

Sorting names works using the same algorithm. Just change the array type from int to std::string, and initialize with the appropriate values.

std::sort

Because sorting arrays is so common, the C++ standard library includes a sorting function named `std::sort`. `std::sort` lives in the <algorithm> header, and can be invoked on an array like so:

By default, std::sort sorts in ascending order using operator< to compare pairs of elements and swapping them if necessary (much like our selection sort example does above).

We’ll talk more about `std::sort` in a future chapter.

Quiz time

Question #1

Manually show how selection sort works on the following array: { 30, 60, 20, 50, 40, 10 }. Show the array after each swap that takes place.

Show Solution

Question #2

Rewrite the selection sort code above to sort in descending order (largest numbers first). Although this may seem complex, it is actually surprisingly simple.

Show Solution

Question #3

This one is going to be difficult, so put your game face on.

Another simple sort is called “bubble sort”. Bubble sort works by comparing adjacent pairs of elements, and swapping them if the criteria is met, so that elements “bubble” to the end of the array. Although there are quite a few ways to optimize bubble sort, in this quiz we’ll stick with the unoptimized version here because it’s simplest.

Unoptimized bubble sort performs the following steps to sort an array from smallest to largest:
A) Compare array element 0 with array element 1. If element 0 is larger, swap it with element 1.
B) Now do the same for elements 1 and 2, and every subsequent pair of elements until you hit the end of the array. At this point, the last element in the array will be sorted.
C) Repeat the first two steps again until the array is sorted.

Write code that bubble sorts the following array according to the rules above:

Print the sorted array elements at the end of your program.

Hint: If we’re able to sort one element per iteration, that means we’ll need to iterate roughly as many times as there are numbers in our array to guarantee that the whole array is sorted.
Hint: When comparing pairs of elements, be careful of your array’s range.

Show Solution

Question #4

Add two optimizations to the bubble sort algorithm you wrote in the previous quiz question:

• Notice how with each iteration of bubble sort, the biggest number remaining gets bubbled to the end of the array. After the first iteration, the last array element is sorted. After the second iteration, the second to last array element is sorted too. And so on… With each iteration, we don’t need to recheck elements that we know are already sorted. Change your loop to not re-check elements that are already sorted.
• If we go through an entire iteration without doing a swap, then we know the array must already be sorted. Implement a check to determine whether any swaps were made this iteration, and if not, terminate the loop early. If the loop was terminated early, print on which iteration the sort ended early.

Your output should match this:

```Early termination on iteration 6
1 2 3 4 5 6 7 8 9
```

Show Solution

 6.5 -- Multidimensional Arrays Index 6.3 -- Arrays and loops

### 558 comments to 6.4 — Sorting an array using selection sort

• Hrjrjfj

Show the steps need to sort a given array by using selection sort.
A[10] = { 10,2,1,6,5,12,3,0,7,4}

• yeokaiwei

I hope this is acceptable for Quiz 3 and 4.

• nascardriver

- List initialization
- Variable names
- ++prefix postfix++
I already mentioned these in my reply here https://www.learncpp.com/cpp-tutorial/57-for-statements/comment-page-4/#comment-480168
If you're unwilling to accept feedback, there's no point in asking for it. If you have any questions about these points, please ask.

• yeokaiwei

Apologies, I know about your replies only through email.

I've had to create a rule to filter the messages.

Most of the time, I just move from tutorial to tutorial in sequential order.

• nascardriver

I was afraid your email filters were the cause for this after you replied to all my other comments, sorry for being unfriendly.

• yeokaiwei

Oh, no offence taken.

Apologies for any offence given.

• yeokaiwei

1. My opinions on i-j-k Loops. These are my personal opinions and not best practices. I post it so that any mistakes in my understanding can be corrected.

a. Ease of readability. I use i-j-k because I think counters as single letter are less confusing.

b. Pedagogy.  i-j-k loops would serve as nice title for a standard teaching tool and it is easy to reference compared to "complexname" that changes between scenarios. Standard method could teach loops as a whole, rather than 1 loop at a time. Whenever newbies see i-j-k, they instantly go "Ah, it's a nested loop example". Newbies would naturally remember i-j-k as a set, like ABC.
E.g. In the i-loop, in the j-loop

c. Dangers of loop resets. In early versions of C. i-loop within an i-loop would trigger a loop reset from the nested loop (reference Daniel Bush). I think this has been fixed in C++17 as the compiler will give a C4456 error if it detects a repeat declaration.

d. Matrix. I understand naming the loops i-j-k used to refer to matrices from FORTRAN. The loops have mathematical value for optimization E.g. ijk algorithm vs ikj algorithm.

e. "Notice how with each iteration of bubble sort,". I'm not sure which loop it was referring to. However, so I printed the results and I think it was the iteration of the external loop. Was it the external loop?

Thank you for the tutorial.

• yeokaiwei

Could you explain what you mean by "For an array with many elements, searching through them all can be expensive."?

What do you mean by expensive?

Are you talking about the electricity bill?

• nascardriver

"expensive" in programming terms refers to your computers resource usage. It can mean
- using a lot of memory
- using a lot of CPU time (ie. slow)
- using a lot of power (The electricity bill, but more commonly battery usage of mobile devices)

• yeokaiwei

I get it. Expensive does directly translate to \$\$\$.

• chosik

This is my take on the question 4 instead of making variable for keeping track of the last position to swap i used first for loop to keep track of it.

• Fleske

Hi! Coming from R, and really loving this site so far!

In my attempt for exercise 3 I used a do while instead of a double for loop. This worked fine, although I believe the improvements in #4 might be a bit clumsily implemented.

Does this way of doing it perform worse than the solution? I guess it might, because it has to loop over the entire array each time arraySorted() is run?

• nascardriver

- Use ++prefix unless you need postfix++

For an array with N elements, the quiz's solution iterates around N*N times (Outer loop times inner loop). Your solution iterates around N*(N+N) times (That's half as fast). You know that the array is sorted if your line 29 isn't executed, so there's no need to loop through the entire array again to check if it's sorted.

• Fleske

Thanks a lot for your reply! Imagined that it was slower, but didn't think it would be by that much (aka. I didn't do the math, I guess).

(thanks for the operator tip as well, still working on getting to know the c++ operators)

• Jorge Mouta

is there any particular reason to use 2 loops?

• Vaklin Donchev

Hello there.  Is my solution to task 4 correct,and if it is,is there any significant difference in performance from yours,where you are assigning value each itteration, insteod of decrementing it as i did and if yes which i better? Thank you !

• nascardriver

I don't see any mistakes in your code and there should be no performance difference compared to the quiz's solution.

• Rico Groth

tried a very different approach for question #4 but i like the one in the solution way more:

• Rishi

This should work as per your function rules but the array doesn't change after it is passed to the function. I coded the right answer the first time. But I wanted to make the complex part as a function and ran into this problem. You said passing arrays to a function and modifying it inside the function will affect it. But here it didn't. Kindly explain this.

• nascardriver

You cannot use `sizeof` on arrays that were passed to a function. Your compiler would have aborted if you had used `std::size`, which is the recommended way of getting an array's size.

• Rishi

Yeah it worked. But one thing's confusing. Why does the compiler just "abort" it? It should throw a compiler error. Or it should allow it. Just aborting it is not fine. Explain me why does the compiler abort it and won't allow it. Tell me 'cause I'll be stuck if I don't know why. And my edited code is below just for reference. Maybe that'll make your more clear of my question.

• nascardriver

By "abort" I meant cause a compiler error

• Rishi

But my compiler compiled it just fine. But it worked like I never called the sorting function for sorting ie. It prints the sorted array same as the initial array. Is it because I used an Android compiler (Cxxdroid) for this program? Is that the compilers mistake? And do you mean using std::size() will work, or that too produces a compiler error?

• nascardriver

`sizeof` compiles but doesn't do what you want. It returns the size of a pointer, not the size of the entire array.
If you had used `std::size()`, it would have caused a compiler error, causing you to notice that something is wrong.

• Rishi

Oh 'kay. Now it's clear ✌

• Oran

Hi, I can't seem to implement your early termination solution without breaking my function.
If I checked right , the solution's if statement @lines 26-29 repeat the same times as mine ( int countRepeat )
does it necessarily mean that both functions iterated the same amount of times?

• CC

It seems more natural to think of the outer loop in terms of the index that each iteration sorts, like so:

Of course, this makes thinking about the last requirement of Q4 a little trickier, sadly.

Thanks for the fun exercise!

• sergey

How does this even work?
std::swap() accepts two parameters by value and changes them?
what exactly is happening here?

• nascardriver

`std::swap` takes the parameters by reference, which allows it to modify the arguments. We cover reference parameters later.

• Cameron

This was my attempt of selection sort before the example was given. What went wrong here. It sorts correctly after the first index. but the first number is not sorting.
output: 60 10 20 30 40 50

• Cameron

ok. So i figured out the problem by seeing what i did vs the example.

this works

but this doesnt? I'm not understanding the problem of why I can't initialize it to 0 if iIndex equals 0 too.

• nascardriver

In the first iteration, `20` and `10` are swapped and you get

In the next iteration (`iIndex=1`), no element is found that is less than `array[smallestIndex]` (which is 10), but you run line 17, which breaks the already sorted portion of your array. Once you moved an element to the front, you should never touch it again, because you know it's in the correct place.

• My answer to Question 3, is this okay?

• nascardriver

Yes

• Imagine

I did this for Question #3:

the array is sorted, so is this fine to use?

• Imagine

Also what is the point of using static_cast in size(array) if the value is already returned in integer??

• nascardriver

`std::size` returns `std::size_t`, which is not an `int` but some unsigned integer. It works without the cast, because `arraySize` is `constexpr`, which allows the compiler to perform the conversion (Because the compiler can know if the conversion causes loss of information).

• Knight

Hello, Alex and nascardriver. I have a question:
Did the inner loop solve all the inner elements then turn to outside loop? Or only solve one element then turn to outside loop?

• Knight

I used the stepping in the Visual Studio that I can see how the progress going.

• Prex

Is this ok?

• nascardriver

yes :)

• SOTC

Assume two unsorted arrays of 10 elements, first sort the array using selection sort and
then merge it into single list. Write the detailed steps and show the state of array at every
step. Write an algorithm for this operation and also find the complexity.
Can you please provide the solution for this question?

• Question No.3

• samivagyok

Would this be a correct solution for q4?

• nascardriver

- Initialize variables with list initialization
- Use ++prefix unless you need postfix++
- Use single quotation marks for characters
- Use `std::size` instead of `sizeof`

It's working, it's correct

• samivagyok

Thank you! A long time ago I was taught in school with postfix, namespace std, etc., old habits die hard :D

• sims7564

I chose to use a "do/while" to loop through iterations rather than a "for" loop. Is this equivalent or would there be a specific reason to favor the "for" loop? I wrote it this way so that we do not query indexes which we already know are properly sorted (which I now realize was the aim of Quiz #4!).

Thanks
Simon

• nascardriver

There's a tiny difference. Assume an array of length 1. Your code will enter the outer loop, whereas a for-loop wouldn't even start.
You're using the do-while-loop exactly like a for-loop, only with the first iteration being unconditional.

• It's+Me

I actually did not understand the example about the selection sort! But the function sort is pretty easy. Do I have to understand the example? Because the function is easy and understandable at the same time!

• nascardriver

If you understand the function, you should understand the example. If you don't understand the example, you probably didn't understand the function. If you're having trouble understanding it, looking at a video of someone doing the sort step by step can help.

• Shivu

Is this not correct for question 3? Because I get the same result. So is this a better version than the one with inclusion of int iteration or not and if not, then why?

• nascardriver

You wrote selection sort with more swaps (There's probably a name for this).
What you're doing is searching for the smallest element in the unsorted part of the array and moving it to the current index. You're doing a bunch of swaps in between, which hides what is happening.

• goiu

Is this version of the quiz #4 correct?

• nascardriver

yes :)

• Jimmy

I have a questions about solution to question 4.
1)Why is it necessary to static_cast std::size array? Can't {std::size(array)} work as just as well.

• goiu

I guess because std::size doesn't return an int but a size_t type

• avaster

It's not necessary Jimmy, std::size returns an unsigned value, there are 2 solutions for that. Use std::ssize (C++20 only) or use a type cast.

• Joshua

Maybe I misunderstood the algorithm. I cannot understand why the outer for loop is necessary. The loop variable is never used. To my extremely new coding abilities, it looks like unnecessary complexity. Is that more efficient than just... Resetting the loop with an assignment?

• Dylan

From looking at your code, yours does not need the second for loop because you are resetting the for loops iterator variable every time you swap something. I'm not anywhere near an expert but I would be worried that altering the for loops iterator variable from inside the variable could be a bad habit to get into. In a more complex for loop, something could go wrong that would throw it for an infinite loop. Which could be a major pain to get into and debug, especially if it would take a major overhaul to fix the for loop.

• Joshua

I ran some tests, and the way that the author's algorithm is configured allows for that neat optimization trick. I'm still working out a way to optimize my implementation. The solution to Q3 would run a much greater number of iterations with arrays of greater length than mine, making it less efficient with larger datasets, but the optimized version just trashes mine. lol.

• Jan Michael

could you not just drop the endofIndex variable, and just adjust the end of loop index in the nested loop so that it decreases by 1 every time?

something like this