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

254 comments to 6.4 — Sorting an array using selection sort

  • RelearningCGuy

    Is there anything wrong in a case like this to sort without using any tracking variables? My solution just uses a shrinking outer loop counter since max values are sorted each pass:

    • Alex

      You've implemented a bubble sort. There's nothing wrong with that, it's just a different type of sort than selection sort.

      • RelearningCGuy

        I was referring to the solution for question (4) which is for a bubble sort. However, I just realized I missed part of the spec and did not incorporate a check to see if the entire list was already sorted. That's were my issue was. Careless reading on my part.

        • Alex

          Aha, without any context I thought when you said "tracking variables" I thought you meant the variable that holds the index of the smallest/largest element. Glad you got it sorted.

  • Sahil Khandelwal

    /*EASY APPROACH FOR BUBBLE SORT*/
    #include<iostream>
    #include<algorithm>

    int main()
    {   const int length = 5;
        int array[length] = { 30, 50, 20, 10, 40 };
        
        for(int round=1;round<=length-1;round++)
        {    for(int i=0;i<=length-1-round;i++)
            {
                if(array[i]>array[i+1])
                std::swap(array[i],array[i+1]);
            }
            
            
            
        }
        for(int print=0;print<length;print++)
        std::cout<<array[print]<<" ";
        
        return 0;
    }

  • Brandon

    If anyone is interested, here is a version of bubble sort that does not use the swap() function. This is how you manually sort the array!

  • Benjamin

    I used a while & for loop for #3 and #4. Is that still ok? It does do the job.

    Output:

    • nascardriver

      Hi Benjamin!

      Good job solving the quiz, interesting swap (But slower than a temporary)!

      Suggestions:
      * Initialize your variables with uniform initialization.
      * Move @mySwap above @main to avoid the forward declaration. Forward declarations add extra work when you decide to update a function header.

      • Benjamin

        So this below is faster?

        I actually thought the xor would be faster, but it was more of just an interesting thing.

        • nascardriver

          There's not creation/destruction happening because of the way computers work. Declaring @tmp static could cause problems with multi-threading and might be slower than not declaring it static. If @tmp was a more complex data type then declaring it static might improve performance.

  • J Gahr

    Once again, thanks for these great tutorials. Here is my solution to quiz 3.... If the array were something like {3,2,1}, it would go from {3,2,1} to {3,1,2} to {1,2,3} as opposed to {3,2,1} to {2,1,3} to {1,2,3}. I know it doesn't quite follow the instructions, and that it'll be harder to optimize for quiz 4,  but barring that would doing it this way ever be more efficient than the actual solution to quiz 3?

    (edit: for example, if the array is initialized at something like {3,2,4,1}, my solution makes much fewer comparisons, as far as I can tell)

  • Dave

    Hi,
    This is my attempt at problem 3. I was missing the following for loop

    [code]
    for (int iteration = 0; iteration < length-1; ++iteration)
    [\code]

    I do not understand why it was necessary. Clearly it is, as my results showed an odd and incomplete resorting.

    thanks

    [code]
    #include <iostream>

    int main()
    {
        const int length(9);
    int array[length] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };

    for(int currentIndex = 0; currentIndex< length-1; ++currentIndex)
    {

        if(array[currentIndex]> array[currentIndex+1])
        {std::swap(array[currentIndex], array[currentIndex+1]);
        }
    }
        for(int current = 0; current< length; current++)
            std::cout<< array[current]<< " ";
        return 0;
    }
    [\code]

    • nascardriver

      Hi Dave!

      Closing code tags use a forward slash(/), not a backslash(\).

      If you walk through your code line by line in your head you should be able to figure out why you need two loops. Try it with { 9, 1, 2, 1 }.

  • quiz1:

    quiz2:

    • nascardriver

      Hi Ali!

      You submitted the same code twice and it doesn't work. Reply to my comment after you've edited your post or just submit a new one.

  • Donlod

    i compared the runtime of bubble sort vs selection sort using 50k array entries.
    These were the results:
    in debug mode selection sort is a lot faster than bubble sort (2.8s vs. 62s) even though both are considered O(n²). But in release mode selection sort is slightly slower than bubble sort (3.5s vs. 3.2s). Looking at the numbers in release mode selection sort is even slower than in debug mode.

    What is this O(x) for when its not accurate in practice?
    Why is bubble sort faster than selection sort in release mode but slower than selection sort in debug mode?
    Why is selection sort slower in release mode than in debug mode?
    Would be nice if someone can explain this.

    • nascardriver

      Hi Donlod!

      I can't help you a lot, because I don't know what your compiler is doing in Debug/Release mode and apparently I forgot how Big-O works. Make sure you're using the same array for both functions to guarantee a fair comparison.

      • Donlod

        Thanks for your reply! Well i also do not know what the compiler is doing on release/debug but i think its strange that the code runs slower (for selection sort) when in release mode. And im indeed not using exactly the same array because once its sorted im going to shuffle it randomly. But i run the program multiple times and it was always the same behavior.
        Used your code to test it and in release mode its bubble sort: 3.94s and selection sort: 3.51s.
        While in debug mode its bubble sort: 65s and selection sort: 2.85s.
        So behavior is the same: bubblesort is faster than selection sort in release mode while in debug its vice versa. And selection sort runs slower in release mode than in debug mode.

        Thats the code i used:

  • Peter Baum

    Regarding the code in the "Selection sort" example:

    if

    is placed within (but at the end of) the first FOR loop we simplify things and don't need the separate FOR loop for output.  We also have to put

    after the first FOR loop to get the last element of the array.  That isn't a bad thing to do since the way the example stands now, an extra "  " is unnecessarily output at the end.

    Also, if anyone tries the sort with strings, don't forget to include

    or else std::cout will get upset with trying to output the string elements.

  • radu f

    Hello,

    below is my code for the third problem.
    I haven't look to your solution yet, because I want to avoid the situation where I think I did it properly but, in fact, I did wrong.
    Also, I want to mention that my first solution was to use a new array (bool type - 'cause it seems much proper to me than int) where I keep all the 'check_sort_success' values, then using a function in the end of outside loop which return (after doing a loop) to 'check_sort_success' the value true/false.
    Because it's less code, I presume the variant without the second array is better? but, to be honest, using a new array was funnier.

    Anyway, here's my code; a feedback would be very appreciated.

    LE: damn, I just look to your solution. Now I feel silly for the k-variable (at least) :))

    • nascardriver

      Hi Radu!

      I can't think of a scenario in which you modification (To loop until sorted) is worse than Alex' solution, good job (Unless someone else finds this problematic)!

      • radu f

        Thanks Nascardriver!

        Going from this code to problem No. 4  with true/false, was no problem.
        However, I was trying to change the approach: instead of validating the pairs from the first to the last index and then start again from the beginning with the validation, I keep tracking the number of consecutive valid pairs. If it reach the length of the total pairs from the loop (thus reevaluating the last swapped values), at the end of current loop, it stop.
        I also noticed that, at least in this particular case (for the given array value distribution), because the last swap is made at the beginning of the loop, we don't need an extra loop (we made only 5, not 6).
        Can you see something "fishy" in it?
        Thanks!

        • nascardriver

          Apart from the formatting your code looks good to me.
          I think you could have replaced that while-loop with a for-loop. I don't like sorting algorithms so I'll leave figuring this out up to you.

  • Chetan

  • Matt

    After writing this code, I'm comparing it to Alex's and his seems cleaner but this works..  I thought about using a boolean check but figured it would be neat to see how many swaps were made throughout the sorting process so I left it like this.

    @nascardriver I can't find any setting in Visual Studio 2017 to display a reference line showing where 80 characters is (you mentioned this on a previous quiz)  I'll have to do some Googling..

    6.4 Quiz 4:

    • nascardriver

      Hi Matt!

      Seems like VS can only do this with an extension or registry modifications. MS is lazy again.

      You code is fine, but add some curly brackets to the for loop in line 26. It doesn't make a difference, but whenever you have more than one line you should use curly brackets for clarity.

  • Matt

    >1) Manually...

    What!?

    I may or may not have manually derived this:
    Iteration 0: 30 60 20 50 40 10 (This is how the array started)
    Iteration 1: 10 60 20 50 40 30
    Iteration 2: 10 20 60 50 40 30
    Iteration 3: 10 20 30 50 40 60
    Iteration 4: 10 20 30 40 50 60
    Iteration 5: 10 20 30 40 50 60

    🙂 Matt

  • Silviu

    In the first program with the selection sort :
    So i have a little problem understanding the second loop.
    The smallestIndex=0  (length being 5-1=4),
    {
    then will enter the second loop currentIndex=1 ;1<4 ;++currentIndex ok.
    now it's testing
    if(currentIndex=50<smallestIndex=30) only if it's true (in this case no)
    then currentIndex=2 and goes again
    smallestIndex= will take the value of currentIndex;

    my question here it will go out of the blocks -  to the swap instruction  every time when it finds in the if condition a smaller value like 20<30 (true),
    or it remains in the blocks of the loop until the for reaches 4<4 and tests all values in the array and smallIndex will keep the smallest value that was find.

    In the second loop it shouldn't be currentIndex "<= " length, how it's gonna tests the last position if is strictly "<" ?
    }
    Thank you.

    • nascardriver

      Hi Silviu!

      I'm not into sorting algorithms, so I'll leave the first part of your question for someone else.

      > shouldn't be currentIndex "<= " length
      No, let's look at an example

      • Silviu

        I know what happens in the first loop , i know it has 4 numbers and in the array  and we count from '0'.
        The second loop was the problem for me , but know i understand what happens in the second loop for{ goes trough the length of the array and with the condition finds the smallestIndex  } then here swaps the smallestIndex with the startIndex. startIndex is in the outerloop . After the outerloop(innerloop doing the job) finishes counting the length, all the array is well-arranged. Selection sort i understand no problem now. Thank you.
        In quiz number 3 sincerely i would never thought that array[currentlyIndex'+1'(this +1)] means the neighbor  of the currentlyIndex. The 'length-1' in the second loop was a bit weird for me because now i know the last elements was already sorted and that is why it was set like this.Yeah i wished to resolve it myself, sadly i didn't know how to, but i'm here to learn. Thank you and keep up the good work.

  • Hi Alex:

    This is for Q1. I'm posting because of the strange thing happening at Index 8. I can replace the "\t" at line 45 with "       " and it works. I just can't figure out why the "\t" is messing up the output at Index 8?

    *****************
    Linux Mint 18.3
    Code::Blocks svn
    GCC 7.1.0

    • I just did Q2 and the same thing is happening at Index 8 using descending order. It isn't tabbing there like it's suppose to. I can't figure this out. Please advise.

    • nascardriver

      Hi Chandler!

      It's up to your terminal how tabs are displayed.
      Running your code with \t produces

      Running your code with 6 spaces produces

      on my machine.

      • Mine shows this using tab:

        https://imgur.com/cMt7MY7

        https://imgur.com/ZFbY60c

        Why is my Index 8 not cooperating with the call for a tab? That's what I don't understand. I know I don't have to use tabs. But since they were presented in an earlier lesson, I thought I'd throw them in. And when I saw this result (please view the above URLs), it confused me. You told me it was up to the terminal regarding tab display. But my screenshots show Index 8 iteration isn't even being tabbed. Just trying to understand. That's all.

        In the first sacreenshot, if you look at Passes 5-8, Index 8 has a double digit there (34). Before and after Index 8 holds a single digit. That's when it's messing up, when it holds a single digit. The number (10) doesn't get tabbed to Index 9. And that's what I'm trying to understand.

  • Jacob Mine

    Answer n 4, is it worst?

    int main()
    {
      int scores[] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };
      int const num = sizeof(scores) / sizeof(scores[0]);
      
      for (int giro=0; giro<num-1;)
      {
        for (giro=0; giro<num-1;++giro)
        {
          if (scores[giro]>scores[giro+1])
          {
            swap (scores[giro],scores[giro+1]);
            break;
          }
        }
      }  
      
      for (int ind=0;ind<num;++ind)
        cout << scores[ind] << "\n";
      re

  • Sam

    I did it this way:

    int main()
        {
            int scores[] = { 6, 3, 2, 9, 7, 1, 5, 4, 8 };
            const int numStudents = 9;
            bool swap = true;
            for (int i=0; i < numStudents; i++){
                if (swap == false) {
                    std::cout << "Early termination at iteration: " << i << "\n";
                    break;
                }
                int smallestIndex=0;
                swap = false;
                for (int currentIndex = smallestIndex + 1; currentIndex < numStudents - i; currentIndex++)
                {
                    if (scores[currentIndex] < scores [smallestIndex]) {
                        std::swap(scores[currentIndex], scores[smallestIndex]);
                        swap = true;
                    }
                    smallestIndex++;
                }
                }
            
            for (int index = 0; index < numStudents; ++index)
                std::cout << scores[index] << ' ';
                return 0;
    }

  • xjuggy

    I did #3/4 working the outer loop backwards from point where we know the array is sorted.  Are there any potential problems (including efficiency) with this approach or are both equally valid?

  • anthony

    I tried something a bit different for number 3 could you check it out ?

    • nascardriver

      Hi anthony!
      Good job solving the quiz, using early termination is a good idea!
      Line 11: That for loop sure looks weird and I've never seen one with multiple iterators other than on learncpp. Since you're basically iterating over one variable and the other one is one step ahead I'd go with a single iterator. That's just personal preference I guess.

      Same loop: You hardcoded the length of the array although you have a constant for it, this is a big no go!
      Line 17: early is a bool already, the if statement expects a bool, there's no need to compare it to true.

      Line 9, 11, 22: You're inconsistent in your use of ++i and i++.
      Line 7, 8, 9, 10, 11, 22: You're using three different kinds of initialization, choose one and stick to it. (I know 7,8 were supplied by Alex, but it's your submission).
      I suggest curly brackets, because they will cause a compiler warning when you're passing a wrong type that will be casted.

      Personal opinion
      Your code is too compact (line-wise).
      I don't like curly brackets on the end of a line.
      Get some empty lines in there.

    • Alex

      Responding half to the parent comment and half to nascardriver:

      There's nothing inherently wrong with having multiple iterators in a single for loop, and there are occasionally cases where it's useful and more readable to do so.

      However, in this case, it's unnecessary because i and j are essentially interrelated (just offset by 1). Thus, I think it's more confusing to have two interrelated variables than using a single one with an offset.

      Additionally, having a conditional that looks like this: i < 8, j < 9 is wrong (at the very least, it should be i < 8 && j < 9, but this could be compacted to i < 8 since i and j are interrelated). You could also use the array length trick to get the length:

  • MyName

    Hello.
    Please comment if this is any good, or if I am missing something.
    Seems to work in both directions and with multiple equal values.
    With length and values given in quiz, number of iterations is the same.

  • Val

  • Ian

    This could help you figure this out:
    https://www.youtube.com/watch?v=59D6i60zqrg

  • Liam

    Hello Alex

    Here's the code I wrote to solve #2 (which already has the first optimization point built in):

    This looks fairly similar to your solution; however, I get two unexpected results.

    1. If I change line five from "int arrayLength = ..." to "const int arrayLength =..", the algorithm prints out an incorrect result.

    2. If I add further terms to the array, it only works if the numbers are contiguous. Ie. adding "10" to the end works; adding "12" doesn't.

    Can you explain either of these two problems?

    • Alex

      Yes -- your algorithm is wrong, and it's walking off the end of the array. Consider:
      The array length is 9. That means the valid element set has indices 0 through 8.
      When variable iterate is 8, iterate2 (which goes from 0 to iterate) could be 8 also, which means your swap will swap elements 8 and 9. That's off the end of the array.

      It's very odd that making the array length const impacts your results (I see that happen too in VS 2017), but that must be the compiler optimizing the const away and changing the layout of memory immediately after your array.

  • Imre B.

    Hi Alex! I did it with a while loop. How does it compare to the for looped one?

  • Critty

    So i wrote this to try and answer the bubble sort question and came up with ... well , that ! Which seems to produce the correct results , but the path to achieve them is slightly different .
    My question is - is this still considered a bubble sorting algorithm ? Does it have its own name or is this just a random thing i came up with (Maybe still a bubble sort , but with a twist ?) ? Is it more efficient than the bubble sort you implemented ? Less so ? Thanks for any clarification you can provide !

    • Alex

      You implemented a selection sort with an attempt at terminating early. But I don't think selection sort can ever terminate early so I wouldn't expect the early termination to execute.

  • 32Smooth

    Why does swap() even work? I thought the integers are passed by value to funtions ...

    • Alex

      std::swap uses a different kind of parameter called a reference. References don't make a copy of the argument -- they are treated identically to the argument. We cover references later in this chapter, and talk about reference parameters more next chapter.

  • hello from china

    Hi, alex, thanks for the great tutorial. I am your student from china, and i am learning from your website with my class in college together! You help me a lot. however, i am having a problem from my class's hw, my hw wants me to implement a sorting array, if the array size if more than 100, i use merge sort, if the array is less than 100 i use insertion sort. I dont know why i compile my program successfully but i am getting a segmentation fault in the end. would you please look at my program? thanks. however, i only doing insertion sort, i haven implement the merge sort yet. thanks

    Below is the actual problem:
    e combine two sorting algorithms, insertion-sort and merge-sort as follows:
    when the input size is less than 100, we use insertion-sort; otherwise, we use merge-sort. More
    specifically, we replace line 1 in Merge-Sort (page 34) with “if r − p >= 100”, and add line 6
    “else Insertion-Sort(A, p, r)”. Insertion-Sort(A, p, r) implies performing insertion sort on the
    subarray A[p · · · r].

  • John

    how to implement selection sort, consider array A have n no. and find the smallest element in A and put that element in array B. then do same for second smallest element in A

  • Lamont Peterson

    Too many comments to read through all of them at this hour of the morning, so if someone else already posted this "optimization", so be it.

    My code for answering #4 (funny, I called my variable "swapped" before looking at your "solution" section .. great minds and all that?):

    ... and the output matches the quiz's expected result perfectly.

    But as I finished it (and before checking against the "solution" here) I had a little thought and made this version of it:

    The only output difference is this one ends on iteration 5 instead of 6.

    Also note that in both of my versions, instead of using a separate endOfArrayIndex variable, I've simply taken the simple calculation in creating my for loops.  Posting them here, I did "arraySize - (I + 1)" in one and "arraySize - I -1" in the other, but both are equivalent.  Seems a little more efficient that way, too (the compiled programs were slightly smaller with my code than with the solution code, but only about 100 bytes or so).

    I have to wonder why "length" is being specified in all of this?  After all, the lessons already covered finding the "length" on your own. I find it much easier to let the compiler do it for me, which is why I create the array, then calculate the arraySize like this.  Helped with testing, too, making it easier to put in different arrays.

    Thanks for the quiz.  I like engaging brain for thinking and problem solving like this.

    • Alex

      I've updated the answers to calculate the array length automatically. I agree this is better.

    • Bouke285

      Hi,

      Could you clarify why you check if(... swapped == 0)?

      I don't see when that condition would ever be true, other than the array only having 2 elements in it; is that the case you're handling? Thanks!

      • Lamont Peterson

        Note that swapped is initialized to arraySize, but in the inner loop, it will be set to whatever value j holds.  Thus, as we reach the end of the loop, if swapped has either reached the end of the array (e.g., is equal to arraySize) or has become zero (because there's nothing left to process in the inner loop, following a swap at element [0]), this indicates that we have no further need to iterate through the array.

        Think of it this way:  we have two nested loops; the outer loop covers the whole array on the first iteration, then moves us in (forward) one element on each iteration, until we reach one less than arraySize; the inner loop covers the whole array from element 0 to the end, compares adjacent elements, and moves things if needed.  If we complete the inner loop and it set swapped == 0, then that means the last swap that was needed was at the very beginning of the array, and no other swaps were found to be needed later in the array.  In this case, another trip through would not result in any swaps happening at all, thus we know we need not bother looking through it again.

  • Ryan

    Alex,
    How do you find the exact element number that the values lie instead of directly typing out the number? (Use it to replace the question marks). Thanks!

Leave a Comment

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