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

302 comments to 6.4 — Sorting an array using selection sort

  • Angmar

    Hi, In the following snippet I left an uninitialized value, does this mean the compiler might initialize it to a random value? Should I assign it to null? If so, how?

    • Alex

      Yes, in this case, you're using a variable before it's given a value, so the result will be random. You can just initialize size_t to 0 (or whatever value makes sense for your algorithm).

  • codenoob

    When I solve a quiz without looking at the correct answer, I first feel proud to have made something work. Then I look at your example and I feel like an idiot. 😀

    It seems I have trouble realizing I could use existing variables and I'm tempted to create new ones for minor stuff.

    (I have a shitton of includes, but that's just laziness on my part since I'm doing all these quizzes on the same file.)

    • Alex

      Getting it working is the hardest and most important step. Once you get it working, then you can optimize and make it nice.

      Sometimes you have to write something once to realize how you should have written it the first time. My first iterations of a program are often ugly. Then a bit of polish and refinement (and documentation) can be applied to make it nice.

  • Hello Alex,

    Thank you for such a great tutorial! Please, I just have a question about quiz question number 3. I understand why we have to use a nested loop in the selection sort example but not with this one. But when I try to not use a nested loop the code doesn't work. Here is the code for the for loop:

    • Alex

      Each iteration of the loop moves one number to the correct location. You need to run the loop as many times as there are numbers in the array, which requires another loop.

      Your code only does one iteration -- and thus, it only sorts one number.

      • Hello,

        I am not entirely sure what you mean. Excuse me for my my ignorance but I thought my loop loops through the whole array not just once.
        Again sorry if there's anything I'm missing.

        • codenoob

          I had trouble getting my mind wrapped around this too at first so I'll try to explain if I can:

          Let's say you have an array[] = {4, 5, 3, 2, 1}

          First the loop checks if 4 is larger than five. Nope.
          Then is 5 larger than 3. Yes, and they are swapped so now you have {4, 3, 5, 2, 1}
          Then is 5 larger than 2. Yes and swap. {4, 3, 2, 5, 1}
          Is 5 larger than 1. Yes, swap. {4, 3, 2, 1, 5}

          And now the loop has finished. And it only managed to move the largest number (5) to the last index.
          So that's why you have to have this loop nested inside another loop that will make the inside loop go again.
          So that next time after the inside loop finishes, you will have {3, 2, 1, 4, 5}.

          And so on, until the array is sorted. I'm sorry if this is still too confusing. Maybe Alex can explain it better.

          • Thank you so much! You have explained it perfectly! You should consider teaching this. You are very good at giving examples. Thank you very much

            • codenoob

              Haha! Thank you for the kind words. I think I'll leave the teaching to Alex though because I'm still only learning myself. 😀

              Currently in chapter 6.9 and I feel like I haven't understood a word in the last few chapters. 😀
              Might have to read them a few more times. 🙂

  • Anshuman Singh

    Dear Alex, isn't this a better solution for quiz question 3, since you have mentioned  that the swapping of adjacent numbers should take place until the array is sorted only.

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

  • 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;
    }

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

  • 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

    Is this a bad practice?
    I need some suggestion/critics on my answer to Q.3

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

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

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

  • Advokat Hadzitonic

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

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

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

  • nikos-13

    How about that solution for quiz #4:

  • Brad

    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,

  • Satwant

    quiz 4(part A solution)

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

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

  • 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

    Indicates that the student „s answer to question 1 is True, the answer to question 2 is False, and so on. Or 1 means answer is true 0 means answer choice is false. This student did not answer question 9.So in character array unattempt question will be store a space and in integer type unattemted question will store -1. The Quiz has 25 questions. Each correct answer is awarded two points, each wrong answer gets one point deducted, and no answer gets zero points. Write a program that processes the test data. The output should be an answer key, followed by the answers, followed by the test score, followed by the test grade. Assume the following grade scale: 90%–100%, A; 80%–89.99%, B; 70%–79.99%, C; 60%–69.99%, D; and 0%–59.99%, F.

    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!

Leave a Comment

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