Hiểu về thuật toán QuickSort

Posted in Algorithm

Thuật toán dựa trên kỹ thuật chia để trị,được đề xuất bởi C.A.R Hoare
Ý tưởng như sau:

Sắp xếp dãy khóa k[1..n] thì có thể coi là sắp xếp đoạn từ chỉ số 1 tới chỉ số n trong dãy khóa đó.
Nếu đoạn đó có ít hơn 2 khóa thì không cần làm gì cả, nếu đoạn đó có ít nhất 2 khóa, ta chọn một khóa ngẫu nhiên nào đó làm chốt (pivot). Mọi khóa nhỏ hơn khóa chốt được xếp vào vị trí đứng trước chốt,mọi khóa lớn hơn chốt được xếp vào vị trí sau chốt.Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm 2 đoạn khác rỗng mà mọi khóa trong đoạn đầu đều <= chốt và mọi khóa trong đoạn sau đều >= chốt. Vấn đề trở thành sắp xếp 2 đoạn mới được tạo ra (độ dài ngắn hơn độ dài đoạn ban đầu) bằng phương pháp tương tự (gọi đệ quy)
Độ phức tạp là O(n*lgn) Continue reading

Please follow and like us:

Setup OpenGL Environment on Xcode

Posted in OpenGL, Tips

Preparing Libraries:

CMake:
Since most of the libraries provide cmake files to generate files, it is better to have a CMake on your Mac. I do not know a lot about CMake. I just explain how to install it.

For convenience, I installed CMake by Homebrew. Here is the link for installing Homebrew:http://brew.sh
After installing Homebrew, just type “brew install cmake” command in Terminal and CMake will be installed.

GLFW:
1. Go to website and download the file: http://www.glfw.org
2. Unzip the downloaded file.
3. Open Terminal and go to the root directory of glfw, like “glfw-3.2”.
4. Type commands:
cmake .
make
sudo make install
It means GLFW is successfully installed.

GLEW:
1. Go to website and download the file:http://glew.sourceforge.net
2. Open Terminal and go to the root directory of glew, like “glfw-3.1.2”.
3. Type commands:
make
make install
make clean
You may have problem like “no permission”. Because users do not have the permission to directly modify the folder /usr/local/include and /usr/local/lib. You may use command in Terminal to get the permission if you like to install in these folders. Otherwise you can modify the Makefile so that it will generate into different folder. The commands to get the permission are
sudo chown -R $(whoami) /usr/local/include/GL
sudo chown -R $(whoami) /usr/local/lib

What’s more, you can also install glew by Homebrew.

Continue reading

Please follow and like us: