THAM KHẢO!

Nếu dãy ban đầu đã được sắp xếp, thì thuật toán sắp xếp chèn sẽ không thực hiện thay đổi nào trên dãy vì mỗi phần tử trong dãy đã đứng đúng vị trí của nó. Cụ thể, các bước của thuật toán sẽ được thực hiện như sau:

Xác định phần tử đầu tiên trong dãy là phần tử thứ 2 (i = 1), không cần thực hiện bất kỳ thay đổi nào vì phần tử này đã đứng đúng vị trí của nó trong dãy đã được sắp xếp.

Kiểm tra phần tử thứ 3 (i = 2) so với các phần tử trước nó trong dãy. Nếu phần tử này đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Tiếp tục kiểm tra và so sánh từng phần tử còn lại trong dãy với các phần tử trước nó. Nếu phần tử đang xét đã đứng đúng vị trí, không cần thực hiện thay đổi nào.

Sau khi kiểm tra hết các phần tử trong dãy, thuật toán kết thúc mà không có bất kỳ thay đổi nào được thực hiện trên dãy ban đầu, vì dãy đã được sắp xếp.

Bước 1: i = 1;//giả sử có đoạn a[0] đã được sắp xếp

Bước 2: x = a[i];

Bước 3:

Tìm vị trí pos thích hợp trong đoạn a[0] đến a[i-1] để chèn a[i] vào danh sách.

Dời chỗ các phần tử từ a[pos] đến a[i-1] sang phải 1 vị trí để dành chổ cho a[i].

Bước 4: a[pos] = x;//chèn x, có đoạn a[0],…,a[i] đã được sắp.

Bước 5: i = i+1; nếu i < n -> lặp lại bước 2, ngược lại -> Dừng.

Ý tưởng của thuật toán sắp xếp chèn là thực hiện vòng lặp duyệt từ phần tử thứ hai đến cuối dãy. Sau mỗi bước lặp phần tử tương ứng sẽ được chèn vào vị trí đúng của dãy con đã sắp xếp là các phần tử phía trước vị trí đang duyệt.

Em có thể thực hiện như sau:

- Duyệt qua từng phần tử của dãy từ đầu đến cuối.
- So sánh hai phần tử liền kề, nếu phần tử sau lớn hơn phần tử trước thì hoán đổi chúng.
- Tiếp tục duyệt qua các phần tử còn lại cho đến khi không còn phần tử nào cần hoán đổi.
- Lặp lại quá trình trên cho đến khi toàn bộ dãy được sắp xếp.
Hoặc:
-Duyệt qua từng phần tử của dãy từ đầu đến cuối.
-Lưu giá trị của phần tử hiện tại vào biến tạm thời.
-So sánh phần tử hiện tại với các phần tử bên trái, nếu phần tử nào lớn hơn phần tử hiện tại thì dời chúng sang phải một vị trí.
-Chèn giá trị của phần tử hiện tại vào vị trí đúng sau khi dời các phần tử.
-Tăng vị trí phần tử hiện tại lên 1 và lặp lại quá trình trên cho đến khi toàn bộ dãy được sắp xếp.

1.Điểm được sắp xếp theo thứ tự ngẫu nhiên:

# Danh sách tên học sinh

class_names = ["Sơn", "Huyền", "Nam", "Hùng", "Hương", "Hà"]

# Danh sách điểm thi tương ứng

class_scores = [5.6, 7.4, 7.8, 8.4, 8.9, 9.5]

# Nhập khoảng điểm cần tra cứu

start_score = float(input("Nhập điểm bắt đầu của khoảng điểm: "))

end_score = float(input("Nhập điểm kết thúc của khoảng điểm: "))

# Kiểm tra và thông báo tên học sinh có điểm nằm trong khoảng tương ứng

found = False

for i in range(len(class_names)):

  if class_scores[i] >= start_score and class_scores[i] <= end_score:

   print("Học sinh", class_names[i], "có điểm là", class_scores[i])

   found = True

if not found:

  print("Không tìm thấy học sinh nào có điểm trong khoảng điểm đã nhập.")

2.Điểm được sắp xếp theo thứ tự tăng dần:

# Danh sách tên học sinh

class_names = ["Sơn", "Huyền", "Nam", "Hùng", "Hương", "Hà"]

# Danh sách điểm thi tương ứng (đã được sắp xếp theo thứ tự tăng dần)

class_scores = [5.6, 7.4, 7.8, 8.4, 8.9, 9.5]

# Nhập khoảng điểm cần tra cứu

start_score = float(input("Nhập điểm bắt đầu của khoảng điểm: "))

end_score = float(input("Nhập điểm kết thúc của khoảng điểm: "))

# Tìm kiếm nhị phân để tra cứu tên học sinh

found = False

low = 0

  high = len(class_names) – 1

while low <= high:

  mid = (low + high) // 2

  if class_scores[mid] >= start_score and class_scores[mid] <= end_score:

   print("Học sinh", class_names[mid], "có điểm là", class_scores[mid])

   found = True

   break

  elif class_scores[mid] < start_score:

   low = mid + 1

  else:

   high = mid - 1

if not found:

  print("Không tìm thấy học sinh nào có điểm trong khoảng điểm đã nhập.")

Def BinrySearch(A,K):

     left=0

     right=len(A)-1

     while left<=right:

         mid=(left+right)//2

         if A[mid]==K:

          return mid

         elif A[mid]<K:

          left=mid-1

         else:

          right=mid+1

     return -1

input_file=open(“diemthi_sx.inp”)

ds_diem=[]

for line in input_file.readlines():

     ds_diem.append(float(line))

input_file.close():

diem=float(input(‘nhập điểm số cần kiểm tra:’))

vitri=BanirySearch(ds_diem,diem)

if vitri==-1:

     print(‘không tồn tại điểm số cần tìm trong danh sách’)

else:

     print(‘điểm cần tìm nằm ở hàng thứ’,vitri,’trong danh sách’)

def binary_search(names, target):

 low = 0

 high = len(names) - 1

 while low <= high:

  mid = (low + high) // 2

  mid_name = names[mid]

  if mid_name == target:

   return mid

  elif mid_name < target:

   low = mid + 1

  else:

   high = mid - 1

return -1

# Danh sách tên học sinh trong lớp (đã được sắp xếp theo thứ tự bảng chữ cái)

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Trung"]

# Tên học sinh cần tìm

target_name = "Minh"

# Gọi hàm tìm kiếm nhị phân

result = binary_search(class_names, target_name)

if result != -1:

 print("Học sinh có tên là", target_name, "được tìm thấy tại vị trí", result)

else:

 print("Học sinh có tên là", target_name, "không tồn tại trong danh sách.")

def sequential_search(names, target):

    found = []

    for name in names:

        if name == target:

            found.append(name)

    return found

# Danh sách tên học sinh trong lớp

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Hoàn", "Trung"]

# Tên học sinh cần tìm

target_name = "Hoàn"

# Danh sách tên học sinh trong lớp

class_names = ["An", "Bình", "Cường", "Đạt", "Hoàn", "Minh", "Nam", "Thảo", "Hoàn", "Trung"]

# Tên học sinh cần tìm

target_name = "Hoàn"

# Gọi hàm tìm kiếm tuần tự

found_names = sequential_search(class_names, target_name)

if len(found_names) > 0:

    print("Các học sinh có tên là", target_name, "là:", found_names)

else:

    print("Không tìm thấy học sinh nào có tên là", target_name)

def binary_search(arr, x):
   left = 0
   right = len(arr) - 1

   while left <= right:
       mid = (left + right) // 2

       if arr[mid] == x:
           return mid
       elif arr[mid] < x:
           right = mid - 1
       else:
           left = mid + 1

   return -1

# Sử dụng hàm để tìm kiếm giá trị 5 trong dãy sắp xếp giảm dần [9, 8, 6, 5, 3, 1]
arr = [9, 8, 6, 5, 3, 1]
x = 5
result = binary_search(arr, x)

if result != -1:
   print("Element is present at index", str(result))
else:
   print("Element is not present in array")

def timTatCaGiaTri(a, x):

    danhSach = [] # Khởi tạo danh sách rỗng để lưu trữ các phần tử tìm thấy

    for i in range(len(a)):

        if a[i] == x:

            danhSach.append(i) # Nếu phần tử được duyệt là phần tử cần tìm, thêm chỉ số của nó vào danh sách

    return danhSach # Trả về danh sách chứa các chỉ số của các phần tử bằng giá trị cần tìm