The algorithm in Golang

Qua nhiều lần phỏng vấn mình nhận ra là mình rất yếu về các giải thuật trong lập trình. Nhân dịp mình tìm hiểu các giải thuật lập trình để mình chuẩn bị chiến đấu với các buổi phỏng vấn tiếp theo mình sẽ chia sẽ đến các bạn những gì mình đã tìm hiểu được để các bạn tham khảo :).

1. Sorting

a. Bubble sort

Bubble sort là một giải thuật sắp xếp đơn giản. Giải thuật sắp xếp này được tiến hành dựa trên việc so sánh cặp phần tử liền kề nhau và tráo đổi thứ tự nếu chúng không theo thứ tự.

Ý tưởng thuật toán: Xuất phát từ phần tử cuối danh sách ta tiến hành so sánh với phần tử bên trái của nó. Nếu phần tử đang xét có khóa nhỏ hơn phần tử bên trái của nó ta tiến đưa nó về bên trái của dãy bằng cách hoán vị với phần tử bên trái của nó. Tiếp tục thực hiện như thế đối với bài toán có n phần tử thì sau n –1 bước ta thu được danh sách tăng dần.

b. Cocktail sort

Cocktail Sort là một cải tiến của Bubble Sort. Sau khi đưa phần tử nhỏ nhất về đầu dãy, thuật toán sẽ giúp chúng ta đưa phần tử lớn nhất về cuối dãy. Do đưa các phần tử về đúng vị trí ở cả hai đầu nên thuật toán sắp xếp cocktail sẽ giúp cải thiện thời gian sắp xếp dãy số.