Search

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

1) Show Solution

2) Show Solution

3) Show Solution

4) Show Solution

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

336 comments to 6.4 — Sorting an array using selection sort

  • Senso

    hello, for question 3, i made a really different solution comparing to the model you showed in your example, i just want to know if my answer works as well for this case,and if possible, what can i change in order to improve my code. Thanks in advance, the amount of work you have put into these tutorials is impressive,keep you the good work.

    • Hi Senso!

      * Line 13, 15, 17, 23: Initialize your variables with brace initializers. You used copy initialization.
      * Line 10: Initialize your variables with brace initializers. You used direct initialization.
      * Use ++prefix unless you need postfix++.
      * Line 18 can be removed by looping to (length - 1).
      * @length should be initialized based on the length of @array. @Alex, you updated this in the solution, but not in the task.

      You implemented bubble sort, it's a lot slower than selection sort.

  • Matt

    Once upon a time I used to frequent this website, then life happened!

    Happy to be back learning again - currently revisiting all the old lessons I have completed in the past but forgotten.  Here's my take on quiz 4:

    • Welcome back Matt!

      * Line 41: Initialize your variables with brace initializers. You used copy initialization.

      In line 31, @count is equal to ((length - outer) + 1). Doing this calculation once when it's necessary is faster than incrementing @count in every iteration (Unless your array is really short).

  • Arthur

    I didn't quite stick to the quiz parameters and made the array larger for testing the results. I tried a third optimization and sorted both sides of the array. it took me a while to see how I was losing a number to an 'off by one' mistake. the first iteration needed to skip moving small numbers down because the math swapped to an index 1> than the array length. moving numbers in one direction took 26 iterations with this set of numbers , moving them both directions took 9. numbers from the quiz took 4 iterations.

    • Hi Arthur!

      * Line 6: Initialize your variables with brace initializers.
      * Line 29: Limit your lines to 80 characters in length for better readability on small displays.
      * @checkSwap could be a bool, since you don't care about how many swaps happened. Done that, you might see that you don't need it at all (Because @check can replace it).
      * As always, inconsistent formatting.

      • Arthur

        thanks nascardriver, I appreciate the feedback. I thought getting the numbers 'bubbling' in both directions would be a good exercise , was a bit surprised at the result. I imagine mapping the number moves on paper would also be a good exercise to learn to see exactly what the program did.

        • Arthur

          realized line 28 is not needed...

          • Yes it is. On the first iteration, @newLength is 30 and @innerLoop is 0. 30 - 0 = 30. You're accessing @arrayOne[30], which doesn't exist. Behavior is undefined.

            • Arthur

              if I move the offset from line 20 into newLength @ initialization should fix that
              line 11

              line 20

              line 28...

  • Kol

    Can someone please help with this code! I keep getting  10 10 10 10 40

    • whoon

      You're swapping the value of array[iii] with the smallestNum, not with array[jjj]. array[jjj], which value is 10 according to the log above, is unchanged. Thus making 10 always the smallest number compared to those before it.

  • 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 ?

  • TheBeginer

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

    Some crazy numbers appear in the output I dunno why.

  • 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?

  • 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

        Thanks in advance...

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

  • 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

        Hi nascardriver

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

        It Work, but I want to hear you

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

  • hoon

    Hi
    can you check my code?

  • 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?

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

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

  • 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
      + Comments

      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

  • 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?

  • Nguyen

    Hi nascardriver,

    Could you please help me with my code?

    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!

  • varad

    this works just fine!
    am i wrong?

  • Samira Ferdi

    This is the ascendent order.
    How about this? I don't know to prevent redundant after swap 13 (please run the code first)

Leave a Comment

Put all code inside code tags: [code]your code here[/code]