Exercise 6: Searching and Sorting

Prerequisite

You have completed Exercise 5.

Learning Outcomes

Be comfortable studying properties in the input and apply them to efficiently solve problems.

Deadline

This exercise is part of the CS1010 formative assessment. Submit your solution before 28 October 2024, 23:59 to receive feedback and earn your achievement badges.

Acceptance Link

The link to accept the exercise is not available publicly. Visit Canvas for the link.

Concepts and Difficulty

	Question	Sorting	Searching	Difficulty
1	Sort
2	Valley
3	Inversion
4	Marks

Question 1: Sort

A v-array is an array of integers with a special property. The array can be partitioned into two segments: in the first segment, the numbers are sorted in non-ascending order. In the second part, the numbers are sorted in non-descending order. For example, 9 4 2 5 5 8 is a v-array. 9 4 is in non-ascending order, while 2 5 5 8 are in non-descending order. On the other hand, 9 4 5 2 5 8 is not a v-array.

A v-array can be only non-ascending or non-descending. For instance, both 1 2 3, 8 8 8 8, and -2 -5 -10 are all valid v-arrays.

Write a program sort, that reads from standard input:

• a positive integer \(n\),
• followed by \(n\) numbers that form a v-array.

The program sort then sorts the numbers in the v-array in non-descending order and prints the numbers to the standard output, one number per line.

You must solve this problem with an \(O(n)\) algorithm. Solving this in \(O(n^2)\) or \(O(n \log{n})\) is trivial and such solution will be categorized as "Need Improvement"

Sample Runs

ooiwt@pe119:~/ex06-skeleton$ cat inputs/sort.1.in
5
5 4 2 1 3
ooiwt@pe119:~/ex06-skeleton$ ./sort < inputs/sort.1.in
1
2
3
4
5

Question 2: Valley

A strict v-array is a v-array where no two adjacent elements have the same value.

In this problem, we wish to find the minimum value of a strict v-array, known as a valley.

Write a program valley, that reads from standard input:

• a positive integer \(n\),
• followed by \(n\) numbers that form a strict v-array.

The program valley then prints the valley of the array to the standard output.

You must solve this problem with an \(O(\log{n})\) algorithm. Solving this in \(O(n)\) is trivial, and such solution will be marked as "Need Improvement."

Sample Runs

ooiwt@pe119:~/ex06-skeleton$ cat inputs/valley.1.in
5
5 4 2 1 3
ooiwt@pe119:~/ex06-skeleton$ ./sort < inputs/valley.1.in
1

Question 3: Inversion

In an array that is supposed to be sorted in some order, an inversion is a pair of numbers that is out of order. For instance, if we want to sort the array "1 3 4 2", in increasing order, the pair (3, 2) and (4, 2) are out of order. So there are two inversions in this array.

An array that is sorted has no inversion, while an array of size \(n\) that is inversely sort has \(n(n-1)/2\) inversions.

The concept of inversion is not new. In the problem kendall, you have counted the number of inversions. In bubble sort, every pass removes some number of inversions until no more inversion is left.

In this question, you are given an array of \(n\) integers where the elements are unique, i.e., there is no duplicate in the inputs. Furthermore, the input is the inverse of a v-array. There is some \(k\), \(0 \le k \le n\), where the first \(k\) elements in the array are in increasing order, and the remaining \(n - k\) elements are in decreasing order.

Write a program inversion that reads, from the standard input, the following:

• An integer \(n (n \ge 1)\), followed by
• \(n\) integers

You program should then prints, to the standard output, the number of inversions in the input.

You have already solved this problem in kendall in \(O(n^2)\) time, so, an \(O(n^2)\) solution would be marked as "Need Improvement". An \(O(n log n)\) solution would be "Good", while an \(O(n)\) solution would be "Excellent".

Sample Runs

ooiwt@pe119:~/ex06-weitsang$ cat inputs/inversion.1.in
5
1 3 5 4 2
ooiwt@pe119:~/ex06-weitsang$ ./inversion < inputs/inversion.1.in
4
ooiwt@pe119:~/ex06-weitsang$ cat inputs/inversion.2.in
3
1 20 300
ooiwt@pe119:~/ex06-weitsang$ ./inversion < inputs/inversion.2.in
0
ooiwt@pe119:~/ex06-weitsang$ cat inputs/inversion.3.in
1
-100
ooiwt@pe119:~/ex06-weitsang$ ./inversion < inputs/inversion.3.in
0

Question 4: Marks

Professor Elm has a list of students and their midterm marks. The list is sorted according to the names in increasing alphabetical order. Professor Elm wants to sort the list according to the marks. Students with the same marks should be ordered according to their names in increasing alphabetical order.

For example, if the list is:

Annie 80
Levi  90
Sasha 80
Zeke  90

The sorted list should be:

80 Annie
80 Sasha
90 Levi
90 Zeke

Annie and Sasha both have 80 marks, but "Annie" comes before "Sasha" in alphabetical order. Similarly, Levi and Zeke both have 90 marks, but "Levi" comes before "Zeke" in alphabetical order.

Write a program marks to help Professor Elm with this task. The program should reads from standard input:

• a positive integer \(n\),
• followed by \(n\) pairs of student names and marks. Each student name is a word. The name is followed by the marks, which is a non-negative integer ranging from 0 to 100 inclusive.

Print, to the standard output,

• the list of students, one student per line. Each line should start with the student marks, followed by a space, followed by the name of the student.

Solve this in \(O(n)\) time to obtain the "Excellent" badge. A solution slower than \(O(n)\) time would be marked as "Need Improvement".

Sample Runs

ooiwt@pe119:~/ex06-weitsang$ cat inputs/marks.1.in
3
Armin 70
Eren 80
Mikasa 60
ooiwt@pe119:~/ex06-weitsang$ ./marks < inputs/marks.1.in
60 Mikasa
70 Armin
80 Eren
ooiwt@pe119:~/ex06-weitsang$ cat inputs/marks.2.in
4
Annie 80
Levi  90
Sasha 80
Zeke  90
ooiwt@pe119:~/ex06-weitsang$ ./marks < inputs/marks.2.in
80 Annie
80 Sasha
90 Levi
90 Zeke