Search

6.4 — Sorting an array using selection sort

A case for sorting

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.

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

121 comments to 6.4 — Sorting an array using selection sort

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

      See wikipedia for more information.

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

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

  • Chad

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

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

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

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

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

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

  • skyler

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

  • 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 code reads:

    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?

  • 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

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

  • My 2ct:

  • AUASP

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

  • Divyank

    Can anyone tell me what is wrong with this code ?

    It outputs -

    3 5 237 34 264 234 767 656 786

  • lampshade

    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?

    • lampshade

      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;

  • 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

      You can write your own:

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

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

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

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

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

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

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

  • Ali

    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?

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

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

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

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

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

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

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

  • Sid

    can someone help me. i need to write a C++ program in which create an array to hold climate data- specifically temperature data.
    have the following menu presented:
    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
    ……
    [then return to the main menu]

    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

    after all menu option (except <5> ) control should return to the main menu

    please help me with this assignment.

  • !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." /

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

  • bio

    This is my solution for exercise 4).But i like Alex’s way better ,i think i schould work more with Boolean variables.

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

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

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

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

  • 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

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

  • 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

  • Gemparks

    Is it a cheat if i do it this way instead?

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

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

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

  • Amin Ashofteh Yazdi

    In the name of God
    Hi Teacher,
    Very Thanks for your lessons,
    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 …
    please check it and give me your idea ,

    Bye
    Hope to God

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

    }

  • 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

      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.

  • Akhil

    Is this solution correct for 3rd question

    Q4

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

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

  • Vlad

    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.

    • Vlad

      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.

      But I’m not sure about this, I’ll test it and get back.

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

      • Vlad

        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.

          • Vlad

            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.

  • Sethacre

    This returns iteration 5. Is this a terrible code?

  • Farrukh Zeb

    How would we do the same sorting for 2D 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;

    }

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

Leave a Comment

Put C++ code inside [code][/code] tags to use the syntax highlighter