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

Your output should match this:

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

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

• Fatih Türkmen

Hi Alex and Nascardriver! Thank you very much for these tutorials.
I came up with this solution, what do you think about it?

• NXPY123

I did the sorting alogrithm using while(true) . Are there any underlying problems to this method ?

• Hi!

* Line 13, 39: Should be ++prefix
* Variable names should be descriptive
* @b should be a bool
* @main: Missing return statement

By using a while-loop, you're loosing the ability to skip the last few elements, which are already sorted. You're checking up to @n every time.

• NXPY

Thanks for the tip !

• TheBeginer

Hi, can someone tell me why my code is producing unexpected results?

Some crazy numbers appear in the output I dunno why.

• Line 19: You're storing arr[i], not arr[j]

* Don't use "using namespace"
* Variable names should be descriptive
* Declare iterators in the for-loops header
* Magic number: 10
* Use ++prefix unless you need postfix++
* Declare variables with the smallest scope possible
* Declare one variable per line

• TheBeginer

I'll remember those points. And yes it works now, silly me. Thank you so much! :)
I had a question though, why shouldn't I use using namespace?

• It can lead to name collisions. There's an example about it somewhere, I can't find it right now.

• TheBeginer

Ok thanks

• It's useful.Thank u

• Thomas

This would be my idea, any better idea maybe?

• Hi Thomas!

* You're using 3 different kinds of initialization. Initialize your variables with uniform initialization
* Use ++prefix unless your need postfix++
* @main: Missing return statement

Your algorithm isn't bubble sort. It cycles through all indexes and swaps elements until all elements to the right of the element at the current index are larger than or equal to the element of the current index. Try running your code in your head, do the same for Alex' code.

• Thomas

Also, would it be smarter to define the wasSwapped boolean in the scope of the main function instead of the outer loop and just reset it to false in every iteration since it then would not needed to be destroyed and created for each iteration or does this not make any difference?

• There should be no difference. You can worry about this when you're in the same situation, but the variable is a large type that only needs to be partially reset.

• magaji::hussaini

my quiz 3&4 snippet

• * Line 8: Initialize to @length
* Line 15: @length == 1 causes undefined behavior
* Line 18: @isSwapped is a bool, 1 is an int
* Don't use goto

• magaji::hussaini

* Line 15: @length == 1 causes undefined behavior:  I tested the algorithm with various array sizes and it works fine.

* Line 18: @isSwapped is a bool, 1 is an int:  Explicit type type conversion will act on it

@goto : my mistake bcos I think the statement was inside the nested loop

• > Line 15
If @length == 1, then @length2 == 1. In line 15, @j is 0, array[j + 1] will execute. @array doesn't have an element at index 1. Behavior is undefined.

> Explicit type type conversion will act on it
Sure it will, you can write code ugly as hell in C++ without causing problems if you want to. You could also do it properly in an easy-to-read style.

• magaji::hussaini

Thanks nasCarDriver but also take a closer look at the expression

if length2 = 1 and j = 0,
[j + 1] -> [0 + 1] = 1,
so the expression becomes:

[1 < 1] is false and the expression will not execute.
Unless if I am confused.
I wait to hear from you....Thanks
Hussaini Magaji

• The conditions are executed left to right. array[1] is accessed before j+1 is compared to @length2.

If you change it to

there is no problem.

• magaji::hussaini

Thanks
Your expr provides short-circuit evaluation which is better.
but also with array[1] beign garbage, the entire expression will always evaluate to false preventing array[1] from beign used in the program (array[1] will not affect or modify it).
I will stick to yours...
All thanks

• This line alone causes undefined behavior. You don't need to write to it or use it for anything.

> the entire expression will always evaluate to false
Only if it finishes execution, it might crash before that happens.

> preventing array[1] from beign used in the program
You're using it

The only way to prevent this is checking the index before accessing the array.

• magaji::hussaini

@array[1], length2 is 1:
length2 means only array[0] is available and will always signifies the end.

• Rai

I made this sort that takes even and odd numbers, seperates them and then orders them from largest to smallest in  their odd or even group.

it works but wondering how could this be improved with more efficient / less code?

Also I tried it by taking a user input.

I know i is a non-const variable, but how would I get this to work - sortint out user inputs!!?
any help would be appreciated

• * Initialize your variables with uniform initialization
* Line 14-18 only need to run once to separate even and add numbers
* Line 19ff: You already know where your even numbers end. There's no need to check evenness again
*

These check if the element is not 0. This is unnecessary
* The failure of line 22 implies the success of line 28

This lesson was about implementing the sorting algorithm yourself. In practice this is unnecessary and you should use @std::sort

> how would I get this to work
This is covered in lesson 6.9a

• Boteomap2

Hi,

How to use std::sort to sort an array of struct like solution 2?

• See http://www.cplusplus.com/reference/algorithm/sort/

• Boteomap2

Thank you!!

• Boteomap2

Hi nascardriver

Can you tell me this " [] " do what?
And can i rewrite like this?

It Work, but I want to hear you

• Yes, it's the same.
[](){} is the syntax used for lambda functions (Anonymous functions (Functions without names)).

• Clapfish

Hi Alex!

In the solution for question 2, you have a misleading comment:

"// If the current element is smaller than our previously found largest"

(Should be '...is larger than...')

• Alex

Thanks! Fixed.

• hoon

Hi
can you check my code?

• Hi Hoon!

* Initialize your variables with uniform initialization (Lesson 2.1)
* Missing trailing line feed in @stdout. Your program's output will look weird when run from the command line.

• NPR

So I tried writing my own selection sorting before checking his example and game up with this:

And I noticed he made a new variable to hold the lowest index until the end of the main iteration before he swapped the elements,
is there any particular reason for this? Something I should make a habit of or is my version fine?

• You wrote bubble sort, not selection sort.

• Sir i am electrical engineering student but i have problems in c++ and now our data structure subject is started i need your thoughts....i know practice will make perfect....

• Gizmo

I did things a little differently. (disclaimer: I am only using "using namespace std;" because that is what my coworkers use, and I want to be consistent with them.)

Here is my code:

Based on the way I made my code, are there any improvements that I could make?

• Hi Gizmo!

> Function variables with the subscript "_fin" [...]
Those are called parameters. @printArray could be called from anywhere. It's parameter names shouldn't be based on a callers variables.

> are there any improvements that I could make?
* Line 10, 18, 19, 21, 23, 36, 38: Initialize your variables with uniform initialization
* Line 52: Don't compare to false/true. Use the not-operator (!endLoop).

• Gizmo

Thanks for the feedback, nascardriver.

>Those are called parameters. @printArray could be called from anywhere.
I am horrible with terminology. I should've gone back and reviewed the basics.

>It's parameter names shouldn't be based on a callers variables.
I didn't take that into account when I came up with that naming convention (only a few programs ago.) I won't make that same mistake again.

>Line 10, 18, 19, 21, 23, 36, 38: Initialize your variables with uniform initialization
I changed all of my initialization to the "variableName{value}" format, but how would you go about doing that with line 18?

>Line 52: Don't compare to false/true. Use the not-operator (!endLoop).
Totally forgot about that. I'll use that format for all my bool expressions in the future.

• > how would you go about doing that with line 18?

• Gabriel

I've done it like that:

It did work, but I think it's kinda messy
actually, my code variables are quite different from yours.
Where were my "errors"? (or awkward logics hahaha)

• Gabriel

obvsly I had those variables above the loop

• Hi Gabriel!

* Don't use "using namespace"
* Line 1, 7: Use uniform initialization
* Line 1, 7: Use ++prefix unless you need postfix++
* Line 11: Use @std::swap

• Josh

I wrote this for questions 3/4 and it seems to have worked but I'm not really sure why.

Is this correct?

• Hi Josh!

> I'm not really sure why
Do quiz 1 for bubble sort

> Is this correct?
Yes

+ Uniform initialization
+ Array initialization and length calculation
+ Logic

Suggestions
* Line 16, 32: Initialize to a specific value
* Line 17-21: Wrap in curly brackets, because the for's body exceeds one line. This doesn't change anything, but it's easier to read.
* @main Missing final line feed. This will produce ugly output

• Josh

Alright, thanks for the feedback!

• I'm in love with alex's tutor

Dear Great Teachers Mr Alex,Nas!
I have done  quiz  number 3. I am so happy that it is much closer with yours. But I have got 2 problems with the out put and IDE error.
1) My out put have garbage value. I need to execute my numbers with the prefect order 1,2,3,4....9. But I have gotten the output
like 1,858993660,2,3,4,5,6,7,8. What is wrong with my code.
2) My IDE(Visual studio 2017) turns an error that says "Run-Time check Failure #2 stack around the variable 'sortingNum 'was
corrupted"
3)  How can i attach the picture to this post box? If i do, it'll  better to attach what i have seen in my IDE.
4) i cant compile with std::get.cin(). Don i have somthing missed?

Here is my code my dears!

May prayer to be blessed always!!!!

• Hi!

1,2. @firstindex can be (length - 1), this @seconindex can be (length), which is an invalid index.
3. You can't. You can upload the picture somewhere else and share the link.
4. It's @std::cin.get()

• I'm in love with alex's tutor

Dear Mr Nas!!!
Thank You so much!
Sorry for my negligence to forget what i should have to not forget.
Its so painful  making you busy(taking your golden time) with such type of easy questions.
stay Blessed sir!

• Sam

My solution for question 3/4:

• Hi Sam!

* Initialize your variables with uniform initialization
* Line 7: You don't need to specify the length of the array when you initialize it
* Line 12: Magic number
* Line 20: Comparison of int to bool
* @main~end: Missing line feed

• Harsh

I can't understand your code, please elaborate it sir. Thank you....

• Why does having the outer iteration for loop make the program work? Why can't you just use the for loop inside. It logically doesn't make sense to me. Here is the code with the "iteration" variable for the for loop.

Here is the code without the, "iteration" variable for the for loop.

• Alex

Did you try running your proposed algorithm? It only sorts the last number.

• KitsuekiDC

You need 2 loops because it isn't a linear action

Outer Loop: Go through each element
Inner Loop: For each iteration of outer loop, check if the closest adjacent elements can be swapped, if so swap them.
Repeat outer loop to check consequent pairs.

• Haider

Std::sort has 2 parameters so what arguments does it take?

• Hi Haider!

Have a look at the documentation

References
* std::sort - http://www.cplusplus.com/reference/algorithm/sort/
* std::sort - https://en.cppreference.com/w/cpp/algorithm/sort

• Haider

Thank-you nascardriver.

• Nguyen

Hi nascardriver,

For example, here is what I'd like to see:

Pick any 3 numbers
3
4
5
The numbers you picked are: Three, Four, Five

• Hi Nguyen!

Nice idea to practice. What exactly do you need help with? Your program works as you described. Do you want me to suggest changes?

• Nguyen

Hi nascardriver,

It does not show the last statement on the screen.  The last statement is "The numbers you picked are: Three, Four, Five"
I still don't know why.  Everything I tested seems to work all the way to line 39.

Thanks, Have a great day.

• Output

after the last line and run your code with the debugger and set breakpoints after the loop.

• Nguyen

I found an error in line 8.

it should be

• I'm surprised Visual Studio didn't catch that, but now you know what to look out for.

Suggestions:
* Line 7, 8, 9, 11, 12, 14, 15, 16, 30: Initialize your variables with uniform initialization. See lesson 2.1.
* Line 21, 27: Don't use goto, cpp has enough other, easier to understand, ways of achieving the same results.
* @numbers can be removed
* @tempt_length can be removed
* @m can be removed
* Line 19: Should be a for-loop, because you know how often it's supposed to run

Here's what I came up with (without separation into functions and input validation), feel free to ask any questions that might come up.

• Nguyen

Hi nascardriver,

I really appreciate your suggestions, above all is your time, kindness and dedication to others.
I really enjoyed your program, it helps me see different ways of coming up with better solutions.  For now, as a beginner, I just want to practise what I have learned so far even it is less desirable.  Sometime, it is my purposes to make something more complicated to see how they work.  For example, I had never used "goto" before, so I wanted to use it this time to see if I learned anything about it.  Once I have learned more things, I will learn how to make my programs less complicated and more desirable.

Thanks, Have a great day.

• Nguyen

Hi,

I modified the last example.  Here is my code:

On online C++ compiler, it works perfectly; however, it does not work in MS Studio (Ok, I know why because it is mentioned in the lesson 6.1:  Fixed arrays cannot have a length based on either user input or some other value calculated at runtime.)

But I really want to keep this code, is there anyway to work around with it?

Thanks, have a great day.

• Hi Nguyen!

This is covered in lesson 6.9, you'll need the lessons before it to understand that lesson.

References
Lesson 6.9 - Dynamic memory allocation with new and delete
Lesson 6.9a - Dynamically allocating arrays

• _RryanT

My attempt at Quiz 3:

• nascardriver

Hi Ryan!

Line 6 and 7 were supplied by Alex, but you modified them so I might as well comment on them:

The rest looks good, good job!

• _RryanT

Hey nascardriver!
Your replies are helping me alot to improve my codes. Thank you!