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

275 comments to 6.4 — Sorting an array using selection sort

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