Selection Sort | c++

Question

Hi I'm new to c++ I've written a selection sorting program can you help me and say in swap function why we put the stars(*), and in selectionSort we should use & in <<swap(&arr[min], &arr[i]);>> i mean cant we just say:

int newint = a;
  a = b;
  b = newint;

instead of:

int newint = *a;
  *a = *b;
  *b = newint;

main code:

using namespace std;
void swap(int *a, int *b);
void selectionSort(int arr[], int size);
void printArray(int arr[], int size);

int main() {
    int arr[] = {20, 12, 10, 15, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, size);
    cout << "Sorted array in Acsending Order:\n";
    printArray(arr, size);
}
// ================================================
// swap function to swap two element of the array
void swap(int *a, int *b){
  int newint = *a;
  *a = *b;
  *b = newint;
}
// ================================================
// the selection function made of two main loop
void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; i++) {
        int min = i;
        for (int j = i + 1; j < size; j++) {
            if (arr[j] < arr[min])
                min = j;
            }
        swap(&arr[min], &arr[i]);
        }
    }
// ================================================
// print function to show the final result
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

Learn what pointers are and how to dereference them to get the value they point to. — Jesper Juhl, Jul 18 '20 at 13:09
`using namespace std;` and defining your own `swap()` function might not be the best combination. — Shawn, Jul 18 '20 at 13:28

score 1 · Accepted Answer · answered Jul 18 '20 at 13:17

Pointers are passed by reference, that means, that if you change it in a function, it will be changed after the function call, too. Like:

int a=5;
setTo6(&a);//Implementation: *a=6
//a=6

On the other hand, all other parameters, that are not pointers are passed by value. This means, if you change them in the function, it won't be changed on the caller side.

int a=5;
setTo6ByValue(a);//Implementation: a=6
//a=5

So, consider this two swap functions: (1)

void swap(int *a, int *b){
  int newint = *a;
  *a = *b;
  *b = newint;
}

and (2)

void swap(int a, int b){
  int newint = a;
  a = b;
  b = newint;
}

What will happen in the first one?

int a=5;//Address=0x1000
int b=6;//Address=0x1004
swap(&a,&b);

The pointers are passed to the function, after that, the content at the address 0x1000(Pointer to a) is stored in newint.

*a = *b;

Set the int at address 0x1000 to the value at the address of b (0x1004).

*b = newint;

Set the int at address 0x1004 to the value of newint.

What will the second do?

int a=5;//Maybe in the r8 register
int b=6;//r9 register
swap(a,b);

We will have following assembly code (really unoptimized):

mov $5, %r8 //int a = 5
mov $6, %r9 //int b = 6
//Setup registers (https://stackoverflow.com/a/2538212/13912132)
mov %r8, %rdi
mov %r9, %rsi
call swap // swap(a,b)
....



swap:
     mov %rdi, %rax //int newint=a
     mov %rsi, %rdi //a=b
     mov %rax, %rsi //b=newint
     ret //Return to caller

They won't be changed, as you only change the variable.

These two concepts are known as Call-by-value and Call-by-reference. Here it is further explained: https://www.guru99.com/call-by-value-vs-call-by-reference.html

score 0 · Answer 2 · answered Jul 18 '20 at 13:14

a and b are pointers, received as parameters, their address is passed. They are like fingers. For example, you point to a value with your finger and I point to another value with my finger. When you intend to swap the content we are pointing to, then you will need to point to where I pointed to earlier and I will need to point to where you pointed to earlier. What you suggest instead is to exchange our fingers.

Or, more technically: you need to swap the values where the pointers are pointing to instead of switching the memory locations of the pointers.

Another analogy could be about addresses. You live at a certain address and I live at another address. If we swap our addresses, then you move into my former address and I move into your former address. But we do not physically move the houses we lived in to our new addresses.

Selection Sort | c++

2 Answers2