1
$\begingroup$

Code:

a=10
b=5
temp=a
a=b
b=temp

I am studying Python and I stumbled upon the classic program: The Swapping Program.

It is simple:

temp binds to a.

a binds to b.

b binds to temp.

I can decode what is happening in memory as well. I will show it here:

enter image description here

But sadly, I can't wrap my head around how we got to this program? What was the problem solving part of this problem. How did we decide that this would be our program? What logic was used to build this program? The reason is simple while I might not come across swapping 3 variables, but if I learn the basics programs properly, I make sure that I learn the complex topics as well.

$\endgroup$
5
  • $\begingroup$ Your initial program raise a syntax error in Python. You should switch the , with a ; or write a, b = 10, 5. $\endgroup$
    – Nathaniel
    Nov 26 '21 at 10:38
  • $\begingroup$ Also, since you understand what happens memory-wise, it is difficult to explain it more clearly… $\endgroup$
    – Nathaniel
    Nov 26 '21 at 10:39
  • $\begingroup$ I want to understand how we come up with this code? I don't want to reverse learn but to forward learn i.e learn without knowing the code. Then learn sth so that I know "yeah that's the code". $\endgroup$
    – zemvua
    Nov 26 '21 at 10:43
  • $\begingroup$ The best way to learn is to try and fail. The obvious choice for swapping would be something like a = b; b = a. If you try to do this, you will realize that there is an error in the resulting values, and having the memory point of view will help you understand why. The third temporary variable will come naturaly. $\endgroup$
    – Nathaniel
    Nov 26 '21 at 10:47
  • $\begingroup$ Actually, a more natural solution involves 4 variables: a, b, a_old, b_old. After you write a_old = a; b_old = b; a = b_old; b = a_old, you’ll notice that you don’t actually need b_old. $\endgroup$
    – Dmitry
    Nov 26 '21 at 12:50
1
$\begingroup$

Problem: Implement selection sort.

Solution:

def sort(a):
    """Sort the table a using the selection sort algorithm."""
    for i in range(0, len(a)-1):
        k = i
        for j in range(i+1, len(a)):
            if a[j] < a[k]:
                k = j
        # swap a[i] and [k]
        temp = a[i]
        a[i] = a[k]
        a[k] = temp

Note that the last three lines could be implemented without temp as a[i], a[k] = a[k], a[i].

$\endgroup$
0
$\begingroup$

TLDR; see Answer below.


Explanation

Before anything, there are something need to be clarified:

I can decode what is happening in memory as well. I will show it here: ...

While the process on your draft indeed show the essence of swapping (i.e., just an process of exchange), it is NOT what actually happened in memory. There are a plenty of materials that provide rather adequate resources for the internals of a computer program, such as CS Books, Wikipedia, Online Courses, etc. For the sake of convenience, it suffices to quote some statements from Wikipedia:

While this is conceptually simple and in many cases the only convenient way to swap two variables, it uses extra memory.

If I understand it correctly, the swapping process as you described is as follows:

Phase1:
a -> 10
b -> 5

Phase2:
a -> 10 <- temp 
b -> 5 

...

The problem here is that, when a new variable comes up and being assigned for a value, it does not obey the rules that mentioned above, that is, consuming extra memory.

In fact, when this program is running on your computer, your program in Phase 2, shall behave like this:

Phase1:
a -> 10
b -> 5

Phase2:
a -> 10
b -> 5 
temp -> 10

...

You might be surprised by this somewhat inefficient behavior. But Sadly (taking your words), it is true for any one of computer programs, no matter generated by Python, Java, C, C++, etc. The reason why the program does this kind of things is relating to its underlying working mechanism, which is designed for interacting with Operating System. More concretely, they are essentially a bunch of operations of manipulating the operating system's Memory and CPU Registers. Hence the things that you are interested in might more likely be interpreted as following phases:

  1. Phase 1: a got a value 10 in memory address addr_for_var_a, b got a value 5 in memory address addr_for_var_b;

  2. Phase 2: temp take the value from addr_for_var_a into its memory address addr_for_var_temp.

  3. ...

You see, when temp got a value 10, it is essentially an effect of the operation of copying the value from a. This is exactly what happened when your Swapping Program running. And there is no such thing like: making up a new variable then letting it point to others' value so that it need not to have its own value. Each variable has its own value, note that the term "value" here might refer to an actual value, or a memory address.

If you want to check whether what I'm saying here is correct or not, you just need some simple works: Compile Your Swapping Program Into Assembly Form. Assembly form is very close to the form that can be understood by your computer hardware directly. In your assembly output, you must see something like this:

...
MOVE   Value@X   Value@Y     # copy the X's value to Y
...

Answer

If you can understand the things mentioned above, you might not have the doubts about

  1. How we got to this program?
  2. What was the problem solving part of this problem?
  3. What logic was used to build this program?
  4. How was swapping program born?

Because the answer to those questions might be too simple to understand: Nowadays if you want to exchange the values between two variables, the normal computers just work in this way, that is, with the help of the third new variable. If you still cannot understand it properly, check this or this for more details.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.