# 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:

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

Quiz

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.

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.

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 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.

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.

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

Quiz solutions

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

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

• KingFactotum

Hey Alex, first things first : a big thank you for creating and maintaining this amazing website (made my first donation today and I plan to do it again when I can - we really need to support efforts like yours).

On a side note, my motivation for learning c++ comes from making small and overcomplicated games with programs like Game Maker and wanting to get rid of the clunkyness by learning a bunch of elementary things - including proper programming. I hope that some far away day, when I reach a somewhat respectable level of craftsmanship in an area of game making people struggle to learn, I'll be able to build a site like this one to help them!)

In this lesson, we learn about sorting and it gives us indirect insight about the importance of knowing how to write efficient and elegant algorithms to solve various problems. Sooner or later, I'm sure we will be in situations we would have to write our own from scratch. And sometimes intuition and general problem solving skills won't suffice ; this is an art of it own that I know almost nothing about it. Do you have any personal recommandations (best books or websites) for learning to write good algorythms when you are a total beginner ?

• Alex

Thanks for visiting.

All of the algorithm books I've seen recently have been pretty awful for beginners.

A lot of good programming is knowing how and when to use the right tool or capability. Instead of learning how to write algorithms and data structures yourself, you'll get more value in less time by focusing on how and when to use what the standard library provides. When you run across a situation where a solution there doesn't fit, you can either try modifying them (via inheritance or encapsulation), or go on your own.

• KingFactotum

Thank you very much for your answer ; took time to reply because I had to explore things a bit by myself to (hopefully) understand the "hows" and "whys" of your advices! I think I see what you meant : by learning when and how to use what standard library provides I can actually focus on practicing what you teach on lesson 0.4 - Introduction to development.

I think the reason I struggled sometime to write something "new" is that I didn't understand I was kind of mixing-up step 2 and step 3 ("determine how to solved the problem" and "write the program").

Also, I noticed that drawing things helps a lot for me to clear my mind on what I want to do and how I can write it. I used this doodle tool when I was self studying kinematics and it actually works on programming too. Maybe it can  help some other people here. "When you struggle, you can doodle!"

• alex1997

Hey Alex, I've managed to do this. Is there any other faster method for sorting arrays?

• Alex

There are faster algorithms for sorting arrays in general, such as heapsort and quicksort, but they are more complicated. However, bubble sort can be very fast in practice when sorting an almost sorted array.

• bogdan

Hi. Thanks for this tutorial.
my sort is faster 🙂 :
#include <algorithm> // for std::swap, use <utility> instead if C++11
#include <iostream>

int main()
{
const int length(9);
int array[length] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };

for(int n=1;n<length;n++)
{

for(int i=0;i<(length-n);i++)
{
if(array[i]>array[i+1]) std::swap (array[i+1],array[i]);

}
}

for (int index = 0; index < length; ++index)
std::cout << array[index] << ' ';

return 0;

}

• Farrukh Zeb

How would we do the same sorting for 2D array?

• Alex

Depends on whether you want to sort each row, each column, or the whole array.

• Sethacre

This returns iteration 5. Is this a terrible code?

Hello

Yesterday a thought kept bugging me. Your optimizations for bubble sort are meant to reduce its computations from O(n^2) to at most O(n^2/2), and, sure enough, checking the link you provided about sorting algorithms, on wikipedia, the same bool temporary value is used to terminate early if no swaps are made.

But I modified the code to include a printout of the iteration number and the temporary sorting result, to see how it all works, and, to my surprise, with your initial array, it showed a single swap being performed at the beginning of iteration 5, then iteration 6 starts, goes all the way, and only then it stops. It makes sense: having even one swap in it.5 means that it isn't the end, then comes it.6 where there's no swap, at all, but it must be performed all the way to be sure, and only then it comes to a stop.

But this way you waste one whole iteration for checking, only. So I thought of a minor change that can correct that. Instead of a temporary bool value, an integer would be better:

This has the benefit that, if at most one and only one swap has been performed during a whole iteration, it can only be that that swap was the last one. You can't have it otherwise. No matter where you are in the array, if all values are sorted but two of them, x[k]-x[k-1] will only have one negative value:

and so, if

then it can only mean that the current iteration is the last one, so we can skip another run just for checking.

Note that if you have:

or similar, this will mean that more than one swap will be performed, so

.

This isn't that much of an improvement, since the iterations get incrementally smaller, but it is an improvement, nevertheless.

Actually, now that I think of it more, the check can be done to see if

If an iteration will last 3 steps and there were only 2 swaps, then there can't be any other swaps left.

• Darren

I think your code doesn't quite get things right. To explain, your code is saying is that if you have performed only one or no swaps this iteration then break from the sorting. However, consider the following array of integers:

No swap would occur until the last pair of integers {9,7}, i.e we have only performed one swap for the iteration. Your sorting loop code would break at this point leaving you with the array {1,2,3,4,5,6,8,7,9} which is not completely sorted; in this case it requires one more iteration.

You're right, when I scribbled it on paper I didn't count for this. I tried now with swapped<iteration-1, but that is very unstable (and also, my second comment was wrong). Still, it seems that only a case of one shifted number is the downside of this. Well, it was worth a try.

• Alex

Even though this one didn't work out, I applaud you creating a hypothesis and trying to support it. Stretching yourself is a great way to learn.

Well, today I have given it some more thought and I seem to have solved it. If, in the current iteration, there was one and only one swap AND if that swap was the first and only first time (between array[0] and array[1]), then what I said is true and the iteration can end without starting a new one. Else, if the swap occured at i=1..N (from i=0), then it's not clear and a new iteration is needed, as Darren's example clearly showed. So the change is now like this:

I have tried a few quirks and it seems to work. I don't think the additional values and the new boolean check counts as much, but then, neither does this "improvement". If you find this intriguing, let me know what you think.

• subh samal

I am executing the below code using codeblocks, without adding <utility> or <algorithm> header and the code produces the same result. What can be the reason?

#include <iostream>

int main()
{
int x = 2;
int y = 4;
std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
std::swap(x, y); // swap the values of x and y
std::cout << "After swap:  x = " << x << ", y = " << y << '\n';
}

• Alex

Not sure. Either iostream is including those itself, or your compiler is throwing them in on your behalf. Either way, you should not rely on this behavior.

• Alex

Just realized that by using the "bubble sort" method, one can find the largest number in an array by doing just one iteration (doing only part 1 and 2 of "bubble sort") and then printing the last index:

#include "stdafx.h"
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
const int size(9);
int array[size]{ 43, 76, 12, 85, 23, 54, 37, 73, 34 };

for (int i = 0; i < size - 1; i++) {
if (array[i] > array[i + 1]) {
swap(array[i], array[i + 1]);
}
}

cout << array[size - 1] << endl;

return 0;
}

Is this method the same as the one of the previous chapter?

• Alex

The largest OR smallest, depending on which way you're bubbling. But if all you're trying to do is search an array for the largest index, you can do that without spending time swapping elements.

Not sure what other method you're referring to.

• Akhil

Is this solution correct for 3rd question

Q4

• Amber

Regarding question #3 and the outer "for" loop: Mathematically speaking, a list with 9 terms will actually only ever take a maximum of 8 loops of bubble-sorting to get everything in the correct position (I've tried this out with different sized arrays and different arrangements - maximum number of loops is always one less than the number of terms). So, why do we make the loop go from 0 up to 8, which would make it loop 9 times? What is the point of that extra loop? If there is no point, then why even include it? Why not just make it go from 1 to 8, or from 0 to 7 (size - 1)?

• Amber

Another question regarding #4. I'm getting a bit stuck on the "if (!swapped)" part of the code and understanding what exactly that means since we defined "swapped" as a boolean variable and automatically set it as "false." I've been looking back over and found that when you have "if (boolean)" it is always checking if it is true and then performing that "if" statement if it is.

So, does that mean that each iteration where swapping occurs that swapped = true, so !swapped = false and then if(!swapped) would not run the "if" function? When swapping doesn't occur, then swapped = false, so !swapped = true. and then if(!swapped) would run the "if" function? It seems like a lot of back and forth and I am wondering if I am interpreting that correctly.

• Alex

Yes, you got it. "if (!swapped) ..." is simply a shorthand way of saying "if (swapped == false) ...".

• Alex

You're correct. There's no point in the extra loop. I've updated the example to loop through the size of the array - 1 to avoid a useless iteration.

• Rachel Murray

Only learning but what about doing it this way :

#include <iostream>

#include <utility>

using namespace std;

int main() {

const int size(9);

int array[size] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };

for(int i = size; i>0; i--)

{

for(int start = 0; start < size-1; start++)

{

int current = start +1;

if(array[start] > array[current])

{

swap(array[start], array[current]);

}

}

}

for(int i = 0; i<size; i++)

{

cout << array[i] <<" ";

}

return 0;

}

• Alex

Seems okay, though this is a bubble sort, not a selection sort.

• Amin Ashofteh Yazdi

In the name of God
Hi Teacher,
Mr Alex,
I use my algorithm and write this code for sorting , but i don't understand that this method is a selection method or ...

Bye
Hope to God

• Alex

It is a bubble sort.

• Amin Ashofteh Yazdi

Thanks

• Joshua Richards

Hi Alex,

I was curious what you though about my solution to #3. It works, does a little less work in the inner loop with each iteration of the outer loop, and is extremly modular and simple:

int main()
{
const int size( 9 );
int array[size] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };

for (int lastIndex = 8; lastIndex > 0; --lastIndex)
{
for (int firstIndex = 0,  secondIndex = 1; firstIndex  < lastIndex; ++firstIndex, ++secondIndex)
{
if (array[firstIndex] > array[secondIndex])
{
std::swap(array[firstIndex], array[secondIndex]);
}
}
}
for (int index = 0; index < size; ++index)
{
std::cout << array[index] << " ";
}
return 0;
}

• Alex

Two critiques here:
1) You define size as a variable, but then use a hardcoded constant (8) in your loop rather than size. You should use size instead. That way if the size changes, you won't have to update the loop as well.
2) Since secondindex always equals firstIndex+1, it's pretty redundant. It would be simpler and more efficient to just use firstIndex+1.

• Aymen

Hey Alex, I understand the majority of the bubble sort technique but I'm stuck at one point,

What happens when count is 3??? or in your case when iteration is 3, that means that 3+1 is 4 and there isnt a fourth array index and if there was i would presume it would be zero and so X would get swapped with zero.

Iv been trying to think of reasons and I can only possibly imagine that the compiler knows there isnt a fourth index so just breaks out of the for loop.

Could you explain and cheers 🙂

I'm a novice and please prove me wrong - there's nothing better than learning from your mistakes and learning why its done that way

But wouldnt it be better coding if we did

As this would mean we wouldn't have this problem. As count would never go up to three so the three + 1 expression wouldn't be called.

Thanks again

• Alex

If there isn't a fourth array index, and you try to access the fourth array index, C++ will let you, and will return garbage.

So yes, the way to avoid this is ensure you use size-1 in the array loop to avoid accessing array elements that are out of range.

• george

#include <iostream>
#include <algorithm>

int main()

{
const int size = 5;
int array[size] = {30, 60, 20, 50, 40, 10};

for (int startIndex = 0; startIndex < size; ++startIndex)
{
int smallestIndex = startIndex;

for(int currentIndex = startIndex + 1; currentIndex < size; ++currentIndex)
{
if (array[currentIndex] < array[smallestIndex])
currentIndex = smallestIndex;

}
std::swap(array[startIndex], array[smallestIndex]);
}

for (int index = 0; index < size; ++index)
std::cout << array[index] <<' ';
return 0;

}
after compiling i get this error..
too many initializing for 'int [5]'

• Alex

You've set an array size of 5, but then tried to initialize the array with 6 values. Either change your array size to 6, or remove one of the values.

• Gemparks

Is it a cheat if i do it this way instead?

• Alex

Not really, it's not good modularity because you have one function doing multiple things (sorting and printing output).

• Hey the tutorials are very good and each time i visit this tutorial i always click on the advertisment as a return gift from me but the examples you use especially the variable names are quite complicated;
I would like to suggest you that please reduce the characters in your variable name so it become somewhat  easy to read the code and understand it

• Chris

there is 2 question on my mind:

1. at the example of selection sort. why you didn't directly swap the element at inner loop instead assign smallestIndex and swap at outer loop? is it better(we don't need declare smallestIndex variable) or there is something we must avoided so we must use your way?

2. for the answer of number 4, i think it is better if we initialize the swapped boolean to true, then at the if statement inside inner loop we assign the boolean to false so at if statement in outer loop we don't need the "!" operator. am i right it is better or not?

sorry for my bad English, thank you.

• Alex

1) Doing the swap in the outer loop is how selection sort works. If you do it in the inner loop like you propose, that's a bubble sort. 🙂
2) Debatable. It's better to write code that's easier to understand than to optimize where it isn't required. If you switched the true and false, then your variable has the opposite meaning of its name, and that's definitely bad. If you rename the variable to something like notSwapped, then at least the logic is correct. But personally, I always find "notX" variable harder to follow than "X" variables, because you have to apply a mental negation (and you get double negatives). So personally, I'd say it's better to leave it as is.

• Cunni

For the quiz question #3, i may have stumbled on an 'optimized' bubble sort? It's neat so follow along the debugger to see these work

• Mike

Hi Alex!

At the beginning of the page, in the second paragraph, you write: "For example, in the previous quiz, we used a for each loop...", but as far as I remember, "for each" loop hasn't been explained or used yet.

Also, I'm using MS Visual Studio Community 2015, and std::swap() somehow works even without <utility> header. I haven't found a setting in Visual Studio where <utility> header can be included be default. Why does swap() work?

Thank you!

• Alex

Aah, I moved the lesson on for each loops to later, but forgot to update this reference. Thanks for pointing that out.

It looks like on Visual Studio, the header #includes itself, so if you #include , you get as well. This isn't something you should rely on though.

• Rob G.

Break worked fine. So did setting the outer loop condition to false: (repeat_scan = size) for (repeat_scan<size)

When my array iteration returned that there were "no swaps" I set the outer loop condition to false (repeat_scan = size) for (repeat_scan < size). It stopped as was expected.

• Rob G.

Alex, I have a question. Below is an answer to un-optimized bubble sort. I sometimes geet mired in 1-off scenarios like I did below. I "made it work" by subtracting 1 from size. Is my resolution to the 1-off in that example considered good or undesirable programming?

• Alex

It's not only fine, it's what I do in my reference solution.

• Jim

Alex,
I'm using code blocks 13-12 with the g++ compiler and C++ 11 add on, so I didn't include the #include <algorithm>.

When you remember that the computer has to read and translate the code. The sort worked that 5 element array in .515 seconds, I added 5 more elements and it sorted {30, 50, 20, 10, 40, 60, 80,70,100,90} in .562 seconds. That's still pretty darned fast.

• Jim

Alex,  I forgot to add that I didn't use #include <utility> either in the message above. But it worked.

• bio

This is my solution for exercise 4).But i like Alex's way better ,i think i schould work more with Boolean variables.

• Gopal

I understand the nested loop in section "Selection sort in C++" but not understand the Hint you have provided....:)

Surprisingly i have solved quiz #3 & #4 easily, though i didn't expect this from me...:) It was quite a fun.

• Alex

What hint do you not understand?

• Gopal

This hint:

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.

• Alex

What part of this are you having issue with? I'd like to make it clearer, but I'm still not sure where you're getting stuck.

• !coder

"A) Compare array element 0 with array element 1. If element 0 is smaller, swap it with element 1."

shouldn't that be "If element 0 is greater, swap it with element 1." /

• Alex

Yup. Fixed. Thanks!

• Sid

can someone help me. i need to write a C++ program in which create an array to hold climate data- specifically temperature data.
climate database
----------------
1- enter a new data set
2- print the data set unsorted
3- print the data set
4- change a data element
5-quit
if a person enter <1> the following should occur:
how many days? 10
day 1 temp? 87
day 2 temp? 65
......

if a person enter <2> neatly print the data sett.

if a person enter <3> print the temperatures sorted.(but do not lose track of which day was which temperature)
if a person enter <4> the following should occur:
which day to correct? 3
what was the correct temperature? 62

• Mr D

OK, i've been going over this all afternoon, and now i see the difference between your method and the method i posted.....i guess my method is a bit like the bubble sorting, right?
The devil is in the details!

• Alex

The purpose of the smallest index is so that you can hold the index of the smallest number, so that it can be swapped at the end of the iteration. That's how selection sort is defined.

The algorithm you wrote works -- but it’s not a selection sort algorithm. It’s a bubble sort!

• Mr D

Hi Alex,

In the "Selection sort in C++" part of the tutorial, I'm having a hard time understanding the purpose of the
smallestIndex int. I've modified the code (my version below) and it seems to get the job done just fine, so the smallestIndex int seems (to me at the moment) an unnecessary complication!
(i've also modified the code to show the sorting progress after each iteration).