Exchange sort là gì
Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu.Đây là một bài viết trong seriescác thuật toán sắp xếpcó minh họa code sử dụng ngôn ngữ lập trình C++. Show Ở bài viết nàyNguyễn Văn Hiếuxin giới thiệu tới các bạn thuật toán sắp xếp bubble sort. Nội dung bài viết bao gồm các phần sau:
Lưu ý: Bài viết chỉ mô tả cho việc sắp xếp dãy số tăng dần. Việc sắp xếp dãy số giảm dần sẽ tương tự và bạn đọc tự tìm hiểu Ý tưởng của thuật toán bubble sortThuật toán sắp xếp bubble sort thứcj hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự(số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được sắp xếp. Ví dụ minh họaGiả sử chúng ta cần sắp xếp dãy số [514 2 8] này tăng dần. Lần lặp thứ 2: Lần lặp thứ 3: Minh họa thuật toán sử dụng ngôn ngữ C++
Ở đây, trong hàm bubbleSort tôi sử dụng thêm một biến haveSwap để kiểm tra tại lần lặp hiện hành có xảy ra việc đổi chỗ hai số không. Nếu không, ta có thể kết luận mảng đã sắp xếp mà không cần phải thêm một lần lặp nữa. Kiểm tra kết quả:
Đánh giá thuật toán sắp xếp bubble sortĐộ phức tạp thuật toán
Không gian bộ nhớ sử dụng: O(1) Nếu bạn đang cần học một ngôn ngữ lập trình, hay tìm tới các khóa học hay mà tôi chia sẻ ở mục khóa học nhé. Bạn hãy để lại các thắc mắc, ý kiến đóng góp nếu có xuống mục bình luận ở cuối bài viết nhé. |