Sắp xếp và tìm kiếm là gì? - Sắp xếp & tìm kiếm

Thuật toán sắp xếp và tìm kiếm là hai khái niệm căn bản trong tin học nói chung và trong chuyên ngành lập trình nói riêng. Ngay cả trong cuộc sống hằng ngày bạn cũng gặp rất nhiều người sử dụng hai hành động này. Nhớ ngày xưa lúc học lớp 1 các cô giáo hay bắt học sinh sắp xếp một dãy số theo thứ tự tăng dần hoặc giảm dần, tìm số lớn nhất và nhỏ nhất trong một dãy số, ... đó cũng là những bài toán sắp xếp nhưng ở khía cạnh khác.

Bây giờ chúng ta sẽ tìm hiểu hai khái niệm thuật toán sắp xếp và thuật toán tìm kiếm.

1. Thuật toán sắp xếp là gì?

Sắp xếp là quá trình bố trí lại các phần tử trong một tập hợp theo một trình tự nào đó nhằm mục đích giúp quản lý và tìm kiếm các phần tử dễ dàng và nhanh chóng hơn. Điển hình nhất trong thực tế là các ứng dụng quản lý danh bạ điện thoại thì có sắp xếp theo số, theo tên. Quản lý học sinh thì có sắp xếp theo điểm, theo lớp, theo trường, ... Như vậy có rất nhiều mục đích cần phải sắp xếp các phần tử theo một trình tự. Điển hình nhất lúc bạn học lập trình đó là sắp xếp dãy số tăng dần, giảm dần bởi các kỹ thuật sắp xếp được nghiên cứu và phân tích kỹ lưỡng.

Trong khoa học máy tính và trong toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hoặc một mảng) theo thứ tự (tăng hoặc giảm). Và để dễ dàng cho việc nghiên cứu và học tập thì người ta thường gán các phần tử được sắp xếp là các chữ số.

Chúng ta có khá nhiều thuật toán như:

• Sắp xếp chọn
• Sắp xếp chèn
• Sắp xếp nổi bọt
• Sắp xếp Quick sort
• Sắp xếp Help sort
• Sắp xếp Merge sort

2. Thuật toán tìm kiếm là gì?

Tìm kiếm là quá trình tìm một phần tử nằm trong một tập hợp nhiều phần tử dựa vào một miêu tả nào đó. Ví dụ bạn cần tìm đồng 10k trong một đống tiền từ 10k đến 100k thì quá trình đó ta gọi là tìm kiếm.

Nếu một tập hợp đã được sắp xếp thì quá trình tìm kiếm trong tập hợp đó sẽ nhanh hơn. Ở ví dụ trên nếu đống tiền từ 10k đến 100k đã được sắp xếp tăng dần hoặc giảm dần thì ta rất dễ dàng tìm kiếm tờ 10k. Nhưng nếu đó là một đống tiền lộn xộn thì bạn sẽ mất nhiều thời gian để xử lý chúng.

Vậy thuật toán tìm kiếm là thuật toán dùng để tìm kiếm phần tử trong một danh sách cho trước theo một tiêu chí nhất định. Chúng ta thường sử dụng hai thuật toán đó là thuật toán tìm kiếm tuyến tính và thuật toán tìm kiếm nhị phần.

Thuật toán tìm kiếm tuyến tính là quá trình tìm kiếm trong một tập hợp chưa sắp xếp, giống với đống tiền chưa được sắp xếp ở ví dụ trên. Còn thuật toán tìm kiếm nhị phân là quá trình tìm kiếm trong một dãy đã được sắp xếp. Cả hai thuật toán đều có những ưu và nhược điểm khác nhau.

3. Lời kết

Như vậy trong series này chúng ta sẽ học tổng cộng 6 thuật toán sắp xếp và 2 thuật toán tìm kiếm. Đây là một chương rất quan trọng trong trong học phần cấu trúc dữ liệu của các trường đại học công nghệ thông tin. Đây là bài mở đầu cho chương này nên cũng chỉ là giới thiệu cho các bạn, cái hay sẽ còn ở các bài tiếp theo, mời các bạn theo dõi.