# 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

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

• Which 52 Preston Brown Jersey do you ever buy? Now this
one site for sale: 57 Nick Sundberg Jersey

• Hello! Coach. This is my answer for question 3. I did not use **length3-1** in my program but it still works. I would like to know what is the mistake to not use **length3-1** even if  it runs correctly.

• Alex

You implemented a selection sort instead of a bubble sort. It works correctly because selection sort still sorts the array -- it’s just not what the quiz question asked you to do. 🙂

• Cris

Hello Alex,
This is my first post. I want to show you my code for question 3. It looks different than yours, so I want to know if is OK or if is not proper coding to do it this way. The list was sorted as expected.

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

int main()
{
const int length = 10;
int array[length] = {3,2,5,1,4,9,0,8,7,6};
for(int index = 0; index < length - 1; ++index)
{
for (int firstIndex = 0, secondIndex = 1; firstIndex < length - 1; ++firstIndex, ++secondIndex)
{
if (array[firstIndex] > array[secondIndex])
std::swap(array[firstIndex], array[secondIndex]);
}
}

for (int index = 0; index < length; ++index)
std::cout << array[index] << " ";
std::cout <<"n";
return 0;
}

• Alex

Looks fine to me.

• Hello again

I came up with this solution for question 4, I remember doing something similar for one of my PHP websites many moons ago, however I wasn’t aware of the redundancy you mentioned so never took into account the fact that the largest numbers bubble up to the top and never considered optimisation the way you described it, although it did do the job quickly enough, it would probably have been even faster had I added these optimisations.

Here is the code:-

I do have a question concerning the speed, would the bubble sort method run quicker than say the selection sort method (although it probably doesn’t really matter unless you are dealing with really large arrays), I keep forgetting just how fast compiled C++ runs. What are your thoughts

• Alex

It really depends on the arrays itself. Bubble sort can be one of the fastest sorts when sorting an almost sorted array. However, selection sort is probably more likely to perform better on a completely random array since it’s likely to do less swaps. If speed is really important (e.g. you’re sorting an array with a million elements) I’d probably favor some other sort altogether, like quicksort.

• Ah ok thank you, quicksort, that rings a bell from Basic programming back in the early days on my sinclair spectrum

• I thought I would see if I could build a variation of the selection sort program to demonstrate the solution to quiz question 1 and came up with this

• Anshul

I need some suggestion/critics on my answer to Q.3

• Alex

Not bad practice, just a slightly odd way of doing a bubble sort.

• c++ learner

why compiler says "expected unqualified-id before int
I think the size of an array in this problem means the length of it.

• Alex

The “int” before rightIndex is causing the issue. Remove it.

• Cory G.

Alex, can you explain why comparing two operands, such as:

doesn’t work when written this way with an increment operator:

or when used in a for-loop:

Thank you!

• Pashka2107

Good day. I’m apologising in advance if there are some mistakes in my English.

I’ve written the code to the 4th part of quiz, and most of times it works properly(Result:
Early termination at index 6
Element №1 : 1
Element №2 : 2
Element №3 : 3
Element №4 : 4
Element №5 : 5
Element №6 : 6
Element №7 : 7
Element №8 : 8
Element №9 : 9
)
, but sometimes it shows something like that:
Element №1 : -1671558400
Element №2 : 1
Element №3 : 2
Element №4 : 3
Element №5 : 4
Element №6 : 5
Element №7 : 6
Element №8 : 7
Element №9 : 8
*** stack smashing detected ***: ./a.out terminated

Here is my code. Could you explain, why it behave in that way?

• Alex

Your code is walking off the end of the array. Your j variable will go from 0 to length-1, but then inside the loop you index j+1. When j is length-1, j+1 is length, which means you’re one step off the end of the array.

• Pashka2107

Thanks! Now it works properly at each execution.
But now I cannot understand how it worked sometimes previously.

• Said

I may or may not have watched a certain video that inspired me to spend too much time on question 4

• James Ray

My solution for 4 is at the end of this comment. It was pretty similar to yours (I didn’t peek). I used debugging to figure out why it wasn’t terminating early. I have commented out the debugging code but left it in the solution for education purposes. It turned out that my if clause was wrong:

I removed

& voila! the code worked as expected.

Other than that, using int32_t, and two iteration counters (which is probably less efficient) the code is pretty much the same.

• James Ray

Solution for 3:

• James Ray

While your solution and mine have the same result, it was interesting to find this. It also made more sense to do it this way, since, as you say, the largest number for each iteration of the outer loop gets sent to the endIndex.

• James Ray

Solution for 2 (minor edits, e.g. using the replace all for larger vs smaller and largest vs smallers; and int32_t):

• James Ray

// then keep traack of it

Should say track.

Great explanation,  but i have a question. You’ve said that function std::sort lives in <algorithm> header file. Does that means that only the function declaration is there and the funct. definition is in some run time lib, or….?

• Alex

Yes, the declaration is in the algorithm header, and the definition is in the C++ runtimes that get linked into your program.

tnx:)

• Zachary Gibbs

Hi this is my first time commenting so i might be doing it wrong. For question 4 is the solution I came up with. I put in a iteration check to see how many times the second for loop ran. With my solution it ran 36 times and with your suggested solution it ran 33 times and with the question 3 answer it ran 70+ times.I thought it was the early termination check in your program so I tried to add one to mine and failed. I know my way is not a elegant as yours but i think it should still work. Am i way off with this solution or is there something i could add to get it down to 33 iterations.

• Alex

The difference between 33 and 36 iterations is insubstantial. I wouldn’t worry about it.

• TS

Does anyone know how to do selection sort with swapping 2 elements (the smallet value and the second smallest)?

• How come this doesn’t work in question 3?

Doesn’t it compare a given index of an array with the next one, and if the first one is greater than the second one, it puts the first one ahead? When I run this in my program the numbers are not sorted correctly.

• Alex

Your algorithm only does one pass. Bubble sorting or selection sorting an array requires multiple passes to sort the array. So you need a loop inside a loop, which you don’t have.

• Not sure where to post this, so I’ll just post it here since it’s where I’m at currently.

Will this tutorial series go over how to make programs with clickable buttons, essentially not just a console window? Or simple 2D games? I’d like to learn how to do those.

• Alex

No. Clickable buttons and UI elements are not part of the C++ standard. You have to use 3rd party libraries for those, and thus, they are outside the scope of this tutorial.

• Ok.

• nikos-13

How about that solution for quiz #4:

Maybe I’m not following this quite right, but I’ve made an observation. In solution 4, the lines that read:

The FOR (condition-expression) uses "length", but your comment says "array - 1". I think "length - 1" is still more appropriate here. If we follow the logic through on a 9th iteration (instead of only 8):
1.

(9th iteration would have an index of 8)
"endOfArrayIndex(9 - 8)" results in a value of 1

2.

which would result in "currentIndex < endOfArrayIndex - 1" to equate to "0 < 1 - 1" or "0 < 0" so then the for loop block would not execute at all, and that causes the "swapped" variable to be false, and "Early termination on iteration 9" to print (and a wasted 9th iteration).

That doesn’t sound like early termination to me 🙂 hehe. You can test it using a completely reversed set of numbers so the bubble sort needs to run every single iteration to complete the sort. As far as a performance impact, not much really, since the final iteration isn’t running the inner loop at all. I suppose if the bubble sort in entirety was being called by another loop, that extra iteration could add up quickly.

Thanks for the great tutorials! Also, speaking of sorting, I feel like the comments on each page should be "sorted" with the latest posts at the top, oldest at the bottom (just my preference, probably because all the social networks sort things that way). Have a good day!

• Alex

I agree with you. I’ve updated both the comment and added a -1 to the length to avoid trying to sort a single element. Thanks!

I’ll look into the comment ordering issue.

• anshita

hello how can we display total no of passes or no. of sorts in program,

• Alex

Initialize an integer counter with value 0, and then increment that counter with each iteration.

• Satwant

quiz 4(part A solution)

Instead of creating a new variable endOfArray,is it okay to write ‘for loop’ like below?

• Alex

Yes, it’s fine.

• Son

I think the loop variable in the outer loop(startIndex) should be: startIndex < (length-1) because the loop variable in the inner loop(currentIndex) is set to (startIndex+1)

• Alex

Yes, this would be slightly more efficient, as it avoids doing an unnecessary iteration on the last element. I’ve updated the code.

• Jonas

My solution for Quiz #3:

• inam

Guys some one solve this please Thanks

Qus1
The programming teacher at your University needs help in grading a True/False test. The students test answers are stored in an array. The array contains answers to the test in the form:

TFFTFFTTTTFFTFTFTFTT or 010101011111011

For example, the entry:

TFTFTFTT TFTFTFFTTFT or 10101011-110101001101

Qus 2
Write a program that inputs 10 integers and a key from the user, and then search if the key found in an array or not. If found then delete the values. After deletion array should look like this.
12 3 6 11 7 21 32 9 2 8
Key = 32
After deleting the key 12 3 6 11 7 21 9 2 8 0

• Ville-Pekka

Hi Alex,

This tutorial has been an amazing resource and I’ve learned more and faster from you in a few weeks than I could ever learn at a university C++ course.

I had one question here about selection sort, but as I wrote a long explanation of what I was doing and tried to figure out how to ask about it, I realized what the answer was!

Merry Christmas and thanks for the tutorial!

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

• Gio

I may have done things differently without realizing, but my program keeps telling me it went through 5 iterations instead of 6. I did the swaps by paper and they seem to check out:

original:{ 6, 3, 2, 9, 7, 1, 5, 4, 8 }
1st {3, 2, 6, 7, 1, 5, 4, 8 , 9}
2nd {2, 3, 6, 1, 5, 4, 7, 8 , 9}
3rd {2, 3, 1, 5, 4, 6, 7, 8, 9}
4th {2, 1, 3, 4, 5, 6, 7, 8, 9}
5th {1, 2, 3, 4, 5, 6, 7, 8, 9}

Did I do something off, or am I thinking about this in a weird way? Or are we also counting the original form of the array as  an iteration?

• Peter

The task was to print in "which iteration the sort ended early" it means to print the number of iteration that did nothing.
As you correctly found there are 5 iterations swapping some array elements. The 6th iteration is the first one that did nothing.

• Gio

Ah ok. I knew I missed something. That makes sense. Thanks!

• Quang

Thank you for this tutorial. I just wonder how do i know if my program is optimized or not, is it based on the time the compiler runs the program or there are more different aspects to let me know that???

• Alex

When we use the word optimized in reference to programs, we usually mean in terms of either speed or memory usage. So an optimized program is one in which the developer (or developers) have worked to reduce the memory usage or increase the speed at which the program runs.

There are programs called profilers that can help identify where bottlenecks exist in your code (places where your code is taking lots of time). However, removing bottlenecks is beyond the scope of this tutorial!

• Pablo

Hi Alex,

Great site, you really are doing a great job! Know that it is much appreciated.

Regarding question 3, I have a performance doubt. Below you have my code, with a logic almost matching that of the given answer. However, I tried to follow the principle of modularity and put the sorting code in a function. The result is that my code takes around 8 seconds (!) to finish, while yours is almost instantaneous.

Am I doing something terribly wrong here?

Thanks for the help!

• Alex

Your loop termination condition is wrong:

indexfin is always less than size until it goes so negative it overflows into a huge positive number.

• Pablo

Of course! I changed the logic behind the loop and forgot to fix that. Shame on me -_-

Thanks a lot!

PS: It’s a pity you don’t get an error message when variables are overflowed!

• When trying to blindly right the bubble sort, I wrote (the code below)
and it sorted perfectly. however, that wasn’t how you wrote it in the answer section (question 3).

Is this a bubble sort, or an entirely different sort?
EDIT: Actually I see they arent that differently wrote now, besides me doing (index + 1) and you doing (size -1).

• Typo:
"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)"

currentIndex is started from startIndex+1

“Then smallestIndex is then swapped with startIndex”
“then” used twice 🙂

• Alex

Fixed. Thanks for the note.

• Hi Alex,

Wonderful lessons I appreciate your effort, I was just wondering in the quiz solution 3 you wrote

for (int currentIndex = 0; currentIndex < endOfArray-1; ++currentIndex)

since endofArray is not defined did you mean size here?

• Alex

Yup, fixed now. Thanks for catching.

• Shijian

Hi,

I have a question about how to pass an array as a parameter to a function. For example, a function named doSomething, it takes an integer array as input, and return void. How to declare that function?

void doSomething(int array[ ])?

it seems the array size depends on the actual array we passed. So how to define the array size in [ ]?

Thanks.

• Eric Jones

I don’t fully understand it yet, but the way I understand it so far is:  you have to use a pointer to pass a function to an array.  section 6.10 at the bottom says that that will be covered in functions.  Hope this helped.

• Alex

The answer to this question is slightly complicated. 🙂 There are two syntaxes you can use.

If you’re passing a fixed array with a known size, you can do this:

(where ARRAY_SIZE is some constant representing the known size of the array).

However, if you want to pass arrays where the size of the array is not known in advance, you have to use the pointer syntax (along with a separate size parameter):

We discuss pointers and their relationship to arrays in upcoming lessons.

• Eric Jones

My Solution was in a slightly different order:

30 60 20 50 40 10
10 60 30 50 40 20
10 20 60 50 40 30
10 20 30 60 50 40
10 20 30 40 60 50
10 20 30 40 50 60
10 20 30 40 50 60

I didn’t initialize new variables within the statements but just used the loop counts.
Is there a good reason to use those variables instead?  Here is my code:
--------------------
#include "stdafx.h"
#include <iostream>
#include <algorithm>

int const arraySize = 6;
int anArray[arraySize] = { 30,60,20,50,40,10 };

void printArray()
{
for (int indexCount = 0; indexCount < arraySize; ++indexCount)
std::cout << " " << anArray[indexCount];
std::cout << "\n";
}

void assendSort()
{
using namespace std;
for (int outCount = 0; outCount < arraySize; ++outCount)
{
for (int inCount = outCount + 1; inCount < arraySize; ++inCount)
{
if (anArray[outCount] > anArray[inCount])
swap(anArray[outCount], anArray[inCount]);
}
printArray();
}
}

int _tmain(int argc, _TCHAR* argv[])
{
std::cout << "Starting Array\n\n";
printArray();
std::cout << "\n";

assendSort();

return 0;
}

• Alex

This is a bubble sort, not a selection sort. 🙂

Selection sort can be more efficient than bubble sort if swaps are expensive.

• Samirax

// If the current element is smaller than our previously found smallest

in Solution to Question 2 should be changed to:

//If the current element is larger than our previously found largest

P.S.
Sorry for being "picky" 😉

BTW
I enjoy your tutorials so much. They’re the best I’ve seen so far 🙂

• Alex

Fixed. Thanks for pointing that out.

• C++ newbie

Code isn’t performing how I expect it to perform.  I was wondering if someone could help me out.

Upon printing out a[0], each time I do it, it prints out 30.  Obviously, I want it to print out 10, and then 60 (the lowest and highest numbers respectively).

• Todd

Your two functions, sortAscending() and sortDescending(), are only printing to the terminal; they are not affecting array a[] as defined in main(). Hence, your calls in main() always grab from your original a[] defined in main.

I don’t know how to make a function return a new array. I think you need pointers for that (which Alex covers in future sessions).

• Alex

Arrays are funny things in C++.

When you try to pass an array to a function in C++, the array “decays” into a pointer to the array. And while that pointer still points to the array, it no longer remembers what size the array was. Consequently this line:

will not do what you want because a is no longer an array, it’s a pointer. In your case, sizeof(a) and sizeof(a[0]) probably both evaluated to 4, which means this evaluated to 1 instead of the actual length of your array. So your algorithms are likely sorting just the first element of your array!

This could be fixed by passing the array size as a second parameter and using that instead.

• Cody Blaucks

Great tutorial web-site!  This is the first quiz I found somewhat challenging.  My code was similar to yours, yet a little different.  People have posted enough code, so I won't bother with mine.  I did do it without using the nSmallestIndex variable, which made quiz 2 even easier.

I had errors, so I went into debug mode.  I know you haven't covered that yet, but it wasn't hard to figure out.  I really like the Code::Blocks interface, expecially when combined with certain Linux windows environment features.  Coding in Linux is awesome!!!

• papagym177

At the beginning of this lesson Alex says “The swap() function from the C++ standard library. Swap is defined in the algorithm header, and lives in the std namespace.”

Excuse me for asking but I’m confused about why a function would be defined in one place and it lives in another.

When we are programming how are we supposed to know what, when, and where,& why to include: using namespace std, which #include , or a function name from a library?

• I am not a pro but you probably have to use a reference. For example, http://www.cplusplus.com/reference/ is a good place. Learncpp says swap(a, b) is in algorithm header file but in C++11 it’s in the utility header file. These things changes and you have to have a updated reference to follow.

• Alex

Swap used to be declared in the algorithm header. As yes23 mentioned, it was moved to the utility header in C++11.

My use of the word “lives” was poor wording on my part. I simply meant to indicate that it was part of the std namespace (as all standard library functionality is).

yes23 is also correct: if you want to use a bit of functionality, you need to know what header to include, and that typically means using a reference. It’s a good thing that search engines exist. 🙂

• 3000blasters

sir just a simple doubt
i am using turboo C++ and i guess this headerfile
ALGORITHM.H is not available there
soo can you please suggest me an alternative for swap function

• Alex

But honestly, if you’re using Turbo C++, you should update your compiler. There are plenty of free, modern alternatives available.

Can’t seem to get the following to work in bloodshed C++. The output just brings me the unsorted list.

#include
#include
#include

int main(){
using namespace std;
const int size=6;
int array[size]={30, 60, 20, 50, 40, 10};

for(int outer; outer<size; outer++)
{

int smallest=outer;

for(int inner=outer+1;inner<size;inner++)
{if(array[inner] < array[smallest])
smallest=inner;}

swap(array[outer], array[smallest]);

}

for (int nIndex=0; nIndex < size; nIndex++){
cout << array[nIndex] << endl;

}
cin.clear();
cin.ignore(255, '\n');
cin.get();
}

anyone see where this went wrong?

needed to make that outerloop’s loop variable = to zero… silly me.

• Ahmed Gurie

move swap(array[outer], array[smallest]); from the nested loop

// swap(array[outer], array[smallest]);

}
swap(array[outer], array[smallest]); // Here is the right place

for (int nIndex=0; nIndex < size; nIndex++){
cout << array[nIndex] << endl;

• Divyank

Can anyone tell me what is wrong with this code ?

It outputs -

3 5 237 34 264 234 767 656 786

• Because you don’t need to compare if current number is bigger than the ‘start’, you need to compare it to the smallest index (small).

• octavsly

@Divyank

You need to change the
``` if(anarray[current]<anarray[start]) ```
with
``` if(anarray[current]<anarray[small]) ```

• Divyank

Thanks for the help guys
I was so puzzled by the problem that I even tried another compiler.
AWSOME tutorials, Alex

• AUASP

a single statement can swap 2 values.
a^=b^=a^=b;//swaps a and b

• Alex

This is clever, but it only works for integers.

You’re better off using std::swap since it works for all types.

• My 2ct:

• Zach

I am definitely new to programming, but so far I’m understanding everything reasonably well. I do have one question though. If you are re-initializing “nSmallestIndex” to a value of “nStartIndex” each time, why do you use “nSmallestIndex” in this part of your loop?

If the purpose of “nSmallestIndex” is just to temporarily hold the smallest index whilst you search the rest, wouldn’t it make more sense just to use “nStartIndex” and not bother giving “nSmallestIndex” a value of anything when it’s initialized, thus using “nSmallestIndex” Only as a temp holding place? I hope this is clear, I’m not a C++ pro like some of you. It just took me a while to understand it because of this seemingly unnecessary assignment. Please let me know if there is a good reason for doing so. Thanks -Zach

• Zach

Disregard that. I figured it out. Upon further examination I realized that if you don’t continually check against your hold value, the last value that evaluated as “true” gets swapped, in this case 40. Had it been checking against nSmallestIndex, which gets incrementally smaller with each check, the loop would be checking 40 < 10 rather than 40 < 50. For the record, this is a hard concept to grab when your asked to write one off the top of your head lol. I hope I get quicker with this stuff.

• Petey

hello, i was wondering how swap works since you’re passing an argument by value, not reference, or am i missing something? just wondering, that’s all. great tutorials by the way

• GrantSolar

After following your lessons (Awesome, by the way) I always enjoy the quiz’s however I’ve been having some difficulty with this one. I tried the first question without out-right copying what you did but repeatedly got the same results. I compared yours against mine and changed my variable names to make the differences more obvious. I couldn’t see where I’d gone wrong. I opened a new project and copied your code (and added #include etc.) Yours worked fine.

My other issue is that, whilst yours works straight off, mine refuses to compile unless nStartIndex is declared earlier whilst you don’t. Any ideas why that might be?

• baldo

That is because you put ; after the for statement.

This is a usual mistake that begginers do.

• GrantSolar

Thanks! Man, that’s had me stumped for weeks!

• skyler

nevermind now i understand perfectly, just had to write out what was happening on paper so my brain could fathom it.

• Skyler

Two questions, when the outerloop runs the first time nCurrentIndex is set to 1. If the nested loop runs all of its iterations before the outerloop can run again, then nCurrentIndex would get keep getting incremented by 1 until (nCurrentIndex < nSize) wasnt true. So does it then proceed to the swap() command?

Second, if thats true, then on the second round of the outerloop, does the nested loop reiterate (int nCurrentIndex = nStartIndex + 1)? I thought that ‘for loops’ only use the initializing statement once??? I have the program working, i am just not understanding how exactly it is working.

• Alex

The inner for loop initializes currentIndex once per iteration of the outer loop.

• FuturePixstar

im just lost completely here, i ran through the code the first time, everything when fine, smallest to largest. then to switch it to largest to smallest i did exactly what the solution showed (before looking at it) and well… see for yourself

• rawr

You wait until you have found the smallest, THEN swap(). I commented out the old swap function, then located it outside the internal for loop.

• FuturePixstar

*sigh* this padawan has much to learn yet still. Thanks alot for the help 🙂

• runner

I’m using Selection Sort as a function. Can I get the function to return the sorted array, or do I have to use it to change a global variable?

• I think the best answer to your question is to pass your input array to the selection sort function by reference, which we cover in chapter 7.3.

• Mat

Who ever wrote this post thank you. The book i’m using gave me a horrible example for sorting. Great job who ever put this up.

• Jeffey

attach the loop statement from the last lesson to the end of the for statement and see this program work through the sorting. Thought it was kinda neat how it works.

C++ is definitely harder than MATLAB, but better in some ways.

• Allen01

In the sort example/problem, it would seem that the output statement should read:

`  cout < < anArray << endl; `
But this yields a funky output. The only thing that yields the output below 10 20 30 40 50 Press any key to conitiue… is this output statement:
`  cout < < anArray[nStartIndex] << endl; `
Can you elaborate on this a little more? Thanks.
• anArray refers to the array itself, and the array variable is really just a pointer. So when you do this:

You’re printing out the address held in anArray pointer (which as you say “yields funky output”)

When you really want is to print the value of the ELEMENTS of anArray. To do that, you need to index the array using the [] operator -- in this case, the index is the value of nStartIndex.

Generally speaking, it’s a better idea to sort your array and THEN re-loop through it to print out the sorted result. You could do this by adding the following lines:

By the way, the issue with the disappearing + symbols should be fixed now.

• I didn’t compile this, so I could be wrong, but on line 5, shouldn’t the for loop expression be:

`nStartIndex < (nSize - 1)`
would that be a one off error?
• The code was written to follow the 5-element example that proceeds it. You will note the last step in the example is redundant because it will always swap the last element with itself. Similarly, the last iteration of the outer loop will always cause the last element to be swapped with itself!

This doesn’t affect the correctness of the algorithm, it’s just non-optimal. As you note, changing the loop to `nStartIndex < (nSize - 1)` removes this non-optimality.

Generally when we talk about "off by one" errors, we're talking about errors that make the algorithm perform incorrectly because the loop executes one too many or too few times. In this case, the algorithm is correct, it just has a redundant step that can be removed by changing that loop condition.

• ah, very clear. thanks

• Abhishek

Then what’s the faster and difficult to understand sort?
Will my small mind be able to understand that?

• There are a large number of faster sorting algorithms. Two of the more popular faster sorts are quicksort and mergesort. However, sorting algorithms are really the topic for a data structures/algorithms class or tutorial (since they can be implemented in any language), not a C one. 🙂