ETH_Informatik/Informatik_I/Exercise_6/Task_3

Task 3: [Hidden tests] Sorting by Swapping

• Task
• Input
• Output
• Hidden test cases
• Persistent input
• Solution

Task

Write a program that performs the following:

1. Read a non-negative integer
2. Read \(n\) integers

3. Sort the \(n\) integers read in (2) in decreasing order. To that end, we suggest the following method:

   1. Store the \(n\) integers in a vector
   2. Iterate through the vector, compare each pair of adjacent values and swap them if they are in the wrong order (i.e increasing order)
   3. Repeat step (2) as long as swap are performed.
4. Output the sorted values.

Your solution must isolate the sorting functionality of the program into a separate function, using a reference parameter with the right constness to access the vector. Other sub-tasks of the program may be isolated as well.

Note: We consider solutions as incorrect if they use library functions (or data structures) beyond the ones discussed in the lectures so far to perform the actual computation. In particular, library sorting functions are forbidden as they defeat the purpose of the exercise.

Note: The function you implement must use pass by reference.

Input

A sequence of integers, preceded by its length.

Example:

7 3 8 6 3 4 6 5

Output

The input sequence, minus the length, in decreasing order. The integers are separated by a single space.

8 6 6 5 4 3 3

Hidden test cases

This exercise has some hidden test cases. You will see whether these tests passed or failed, but you will not see the test input or the expected output.

Persistent input

To help you in testing your code, you can enter your custom test input in input.txt. When running the program, you can let CodeExpert read the input from the file.

Write some program input in input.txt. Run the program as usual. Type f (no spaces) in the terminal window and press Enter. The program will use the contents of input.txt as input. Using this feature is entirely optional and does not affect your score.

Solution

#include <iostream>
// Enable vectors
#include <vector>

void readvec(std::vector<int>& vec, int& length) {
    for (int j = 0; j < length; ++j) {
        int i;
        std::cin >> i;
        vec[j] = i;
    }
}

void sortvec(std::vector<int>& vec, int& length) {
    for (int j = length - 1; j > 0; --j) {
        for (int i = 0; i < j; ++i) {
            if (vec[i] < vec[i+1]) {
                int prev = vec[i+1];
                int next = vec[i];
                vec[i] = prev;
                vec[i+1] = next;
            }
        }
    }
}

void printvec(std::vector<int>& vec, int& length) {
    for (int j = 0; j < length; ++j)
        std::cout << vec[j] << " ";
}

int main() {
    int length;
    std::cin >> length;

    std::vector<int> values(length);

    readvec(values, length);

    sortvec(values, length);

    printvec(values, length);

    return 0;
}

---

Made by JirR02 in Switzerland 🇨🇭