Sort by moving elements to start or end with fewest moves

Getting started

You may be familiar with quick-sort, but when you stumble across this problem, it turns out to be a lot more complex. Since you need to determine the method that involves the fewest moves possible, you will have to take another approach. The given problem can be re-stated into this problem:

Problem statement

Hien is the class monitor and he wants his classmates to form a line, in which the height of every students is in ascending order. He needs to form that line by moving his classmates from the line to the start or end of it and it has to be a quick process, since Hien is very lazy and needs to play Age Of Empires right away. Write an algorithm to help him.

Input format

First line: n.

Second line: numbers indicating the height of every student in the class, each seperated by a space.

Constraints

n ≤ 100; H[i] ≤ 100000 (H[i] is the height of an individual).

Output format

An integer indicating the fewest moves possible.

Sample input

4

2 1 3 5

Sample output

1

Explanation

The student with height 1 is moved to the start of the line.

Let’s not pay attention to the ‘fewest moves’ for a while. Normally, when you see these types of ‘moving’ elements to start or end of an array, you can take a look at a basic approach.

Let’s take the Sample input as an example. With the basic approach, we search for the smallest element in the array, which is now 1. After that, we move it to the far right of the array. Then, we search for the next smallest element, which is 2, and we keep doing it until 5 is moved to the far right of the array. We come to the conclusion that for this approach, the number of moves that are taken is exactly equal to the number of elements present in the array itself. But let’s have a closer look. We can see that 2, 3 and 5 are contiguous, meaning that the relative order between them is not changed at all when sorting is completed. So, we can know that in the required algorithm, we need to conserve the order of contiguous integers. That is when std::pair comes to use.

Basic approach illustration

What is std::pair, exactly?

Std::pair is a pre-defined class in C++. A pair element is consisted of 2 other sub-elements, which can be classified as first and second. In the algorithm we are searching for, as stated earlier, we can utilise std::pair to get the job done by assigning the input elements to first and its index to second.

Get the job done

After that, quick-sort comes in handy. We then use it to sort the array in ascending order. Because std::pair is used, when sorting the elements, each index is carried along with the data. Then, we can just compare the indexes of every subsequent element. Job done!

Final approach illustration

Source code (C++)

Review một số sách tôi đọc gần đây

Theo số liệu thống kê báo Tuổi Trẻ đưa năm 2018 thì người Việt đọc 1,2 cuốn sách/năm. Hơi ít, không biết thống kê có sai không, hy vọng là sai. Review vài cuốn để các bạn có thời gian tìm đọc cũng như né để khỏi tốn thời gian. Mong rằng sang năm 2019 cái số thống kê nó cao hơn.

Đọc sách là rất tốt nhé.

Cuốn What The French! nói về Pháp rất là hài, nhiều thông tin nửa khen nửa chê nước Pháp nhưng vẫn rất lịch sự, không thiên vị chút nào. Đọc để biết dân Pháp giáo dục con cái như thế nào, dân Pháp họ nhảy nhót như thế nào, apero là cái quái gì v.v… ai thích học một cái gì đó về Pháp cũng như giải trí rất tốt. Đọc từ cách đây 2 năm nhưng thỉnh thoảng vẫn đem ra đọc lại.

Cuốn Sympathizer thì mấy năm trước đã được giải sách ở Mỹ, không bàn nhiều, nên mua về, để đấy đọc sau (tui cũng chưa đọc haha mặc dù trên kệ đã mấy năm).

Ai thích có một cái nhìn vui vui về cuộc đời dân nghiên cứu khoa học (làm thí nghiệm, mặc áo blouse trắng, đo đạc chính xác…) thì cuốn Lab Girl phải nói cực hay. Tác giả khởi đầu sách bằng việc nói về bố mình là một giáo sư trong trường đại học và hồi cô còn bé ông hay dẫn cô đến lab. Có những thứ phức tạp nhưng được tác giả giải thích đơn giản dễ hiểu, có một số từ chuyên môn nhưng tra từ điển phát ra ngay. Đọc để thấy yêu trái đất này hơn.

Cuốn Đừng bao giờ đi ăn một mình là nhảm nhí. Lớn lên muốn đi ăn một mình hay không là tùy, đi ăn một mình cũng chả làm bạn chết. Lí do thì coi trong cuốn tiếp theo.

Đó là khi bạn là dân Introvert, này không có gì lạ: hơn 1/3 dân số thế giới là Introvert nên nếu bạn vô tình phát hiện ra bạn là Introvert thì bạn cũng không là cái gì đặc biệt hay ngoại lệ hết. Và khi người ta đang party thì bạn ở nhà và đọc cuốn Text, don’t call.

Nếu bạn ngấp nghé muốn lập gia đình cũng như gần gần như vậy, thì đọc cuốn bìa màu vàng nhé. Không bàn nôi dung nhiều, đọc thì biết, nhưng có một câu trong đó là “That you don’t have to be married to be happy in life, but you will be happily married if you first discover your singleness on time before marriage”

Cuốn cùng lại nói về cuốn cũ rích Nhà Giả Kim, tôi biết cuốn ngày từ lâu lắc lâu lơ và thấy nó chả có gì đặc biệt. Chả hiểu tại sao nhiều năm gần đây đi đâu cũng thấy các bạn trẻ quote từ cuốn sách quá trời quá đất. Nếu chấm điểm thì tôi chấm 5/10. Bạn cùng phòng cũng phổ cập thêm là cuốn sách này bị bạn đọc trên toàn thế giới chê tan tác.

Mấy cuốn còn lại mới hốt về chưa đọc, review sau. Nếu không thấy review có nghĩa là sách quá dở hoặc người quá lười.