30/09/2018, 18:33

chèn 1 số vào vị trí bất kì trong mảng

  • các bác hôm tc em gặp cái bài thế này:
  • nhập 1 mảng rồi sắp xếp tăng dần, rồi chèn 1 phần tử bất kì vào 1 vị trí bất kì trong mảng sao cho trật tự không thay đổi.
  • em làm thế này:
    VD: 1 mảng sắp xếp tăng dần:
    1 3 4 5 6 7
    em chèn 2 vào cuối cùng rồi sắp xếp lại
    1 2 3 4 5 6 7
    thế này thầy em bảo sai. các bác giải đáp giúp em vs. em cám ơn!
Nguyễn Duy Khánh viết 20:48 ngày 30/09/2018

Sau khi sắp xếp mảng, duyệt từ đầu tới cuối để kiểm tra nếu phần tử nằm trong đoạn từ a[i] -> a[i+1] thì chèn vào đó.

Gió viết 20:46 ngày 30/09/2018

Nên dùng tìm kiếm nhị phân để tìm vị trí chèn vào

long viết 20:48 ngày 30/09/2018

ý này của bác có vẻ hay!

long viết 20:45 ngày 30/09/2018

em không hiểu cách của bác lắm!
bác có thẻ nói rõ cách này hơn không

Dương Tiến Thịnh viết 20:45 ngày 30/09/2018

Đầu tiên bạn tìm vị trí cần chèn. Ví dụ bạn muốn chèn số 4 vào mảng. Vị trí cần chèn sẽ là 2(i tính từ 0).
Khi xác định được vị trí cần chèn rồi, bạn dồn toàn bộ các phần tử về phía sau.(có thể gán a[i+i]=a[i])
Sau khi dồn xong thì chèn số 3 vào vị trí 2 như đã định từ trước.

Gió viết 20:39 ngày 30/09/2018

Các bước này liên quan đến binary insert sort. Bạn có thể tìm hiểu thêm [Wiki] Binary Insert Sort in C

Bài liên quan
0