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.


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

Output format

An integer indicating the fewest moves possible.

Sample input


2 1 3 5

Sample output



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.

List of free stock photos – Update 2019

A well-picked picture can play an important role to a blogpost or a document in general. However, the search for a good one requires effort (taking photos yourself, finding a good one on the internet) or money (stock market). Fortunately, there are free websites and nice people who are willing to provide their photos for free (or almost free), here is the update list of 2019 which I’m currently using: Continue reading List of free stock photos – Update 2019

Search in Windows

To be short: Searching files in Windows sucks.

I don’t understand why such a supposed-to-be-simple utility is poorly built in Windows system. I was hyped when upgrading from XP to 7, and 7 to 8, and 8 to 10. In the end, the feeling I have is disappointment.

At the beginning, when a fresh system is installed, everything seems smooth. Understandable! Reasons: Not many things to search, indexing is not a heavy job, and computer resource still has lots of room for software to run. Continue reading Search in Windows

[Manga Character]: Son Goku – Dragon Ball

(c) image:

My childhood was filled with full of manga and anime series, fairy tales, video games and traditional games with other neighborhood children. The most influencing hobbies motivated me to imagine and draw were manga and anime series that my mom kept searching and buying for me all the time. She’s a wonderful woman.

Although reading quite a lot, Dragon Ball is still one of my 2 favorite manga series along with Doraemon. It even significantly affected to the way I have grown up. Yes, it was just the beginning of my junior high school 21 years ago. There was a long time during my high school years that I wish I were born a boy. However, forget about it. If you are a fan of Dragon Ball, I am sure that you will have specific characters in the series that strongly inspired you. So do I.

I love Son Goku a lot. Continue reading [Manga Character]: Son Goku – Dragon Ball

Justify text automatically in wordpress blogpost

The new Gutenberg editor provided by WordPress is pretty neat. However, there are certain limits of the ability to align text as what we usually do in Microsoft Word, especially the nice-looking “justified text”.

In earlier version of the editor, we can open the extended editing bar and there would be a Justified Alignment option to click and apply on the paragraph. The current one doesn’t have it. To resolve this problem, there are several options: install the old editor plugin (which will be supported till 2022), or simply put the CSS code in the Additonal CSS section of the current theme setting:

p {text-align:justify}

Then all the paragraphs from now on will be formatted as Justified.

Abbreviations in daily business emails

In our daily work context, regardless of our industry or expertise, most of us will need to use emails for professional communication. The headache sometimes comes when we receive an email with what-the-heck-is-that abbreviations that no one taught at schools or no senior colleagues trained us. The list provided below comprises only some frequent text we may catch at work, excluding the terminologies as there would be plenty of them depending on different industries / sectors / business functions.

Continue reading Abbreviations in daily business emails

Preparing a scientific illustration

Making a beaufitul demonstration for your work is very important when you want to bring a clear and interesting message to the readers, especially in academic community.
Thanks to a lot of drawing tools, both open source and commercial, both click-to-draw and code, one can make beautiful and informative piece of artwork that provides better information to enrich the quality of a manuscript. Let us have a look of all available tools out there.

Continue reading Preparing a scientific illustration