Python

Программа на питоне

Программа для сортировки массивных данных двумя методами. Метод вставки программа не считает количество перестановок

def insertion_sort(mas):
count_if = 0
count_move = 0
for i in range(1, len(mas)):
temp = mas[i]
j = i - 1
count_if += 2
while j >= 0 and temp < mas[j]:
mas[j + 1] = mas[j]
j = j - 1
count_move+= 1
count_if+= 2
mas[j + 1] = temp
if j < 0: count_if -= 1
return arr, count_if, count_move

n_arr = [16,32,64,128,256,512,1024]
for n in n_arr:
arr = []
for i in range(n):
arr.append(randint(-100, 100))
print("Исходный массив ", arr)
print("======Количество символов====== ", n)
arr, count_if, count_move = buble_sort(arr)
print("Пузырьковая сортировка", arr)
print(f"Количество сравнений: {count_if} " f"Количество перестановок: {count_move}")
arr, count_if, count_move =insertion_sort(arr)
print("Сортировка вставкой ", arr)
print(f"Количество сравнений: {count_if} " f"Количество перестановок: {count_move}")
input('Чтобы продолжить нажмите Enter')
АР
Александр Рычков
96 
 from random import randint 

 

def bubble_sort(mas): 

    count_if = 0 

    count_move = 0 

    n = len(mas) 

    for i in range(n - 1): 

        for j in range(n - 1 - i): 

            count_if += 1 

            if mas[j] > mas[j + 1]: 

                mas[j], mas[j + 1] = mas[j + 1], mas[j] 

                count_move += 1 

    return mas, count_if, count_move 

 

def insertion_sort(mas): 

    count_if = 0 

    count_move = 0 

    for i in range(1, len(mas)): 

        temp = mas[i] 

        j = i - 1 

        count_if += 2 

        while j >= 0 and temp < mas[j]: 

            mas[j + 1] = mas[j] 

            j = j - 1 

            count_move += 1 

            count_if += 2 

        mas[j + 1] = temp 

        if j < 0: 

            count_if -= 1 

    return mas, count_if, count_move 

 

n_arr = [16, 32, 64, 128, 256, 512, 1024] 

for n in n_arr: 

    arr = [] 

    for i in range(n): 

        arr.append(randint(-100, 100)) 

    print("Исходный массив:", arr) 

    print("======Количество символов======", n) 

    sorted_arr, count_if, count_move = bubble_sort(arr) 

    print("Пузырьковая сортировка:", sorted_arr) 

    print(f"Количество сравнений: {count_if}, Количество перестановок: {count_move}") 

    arr, count_if, count_move = insertion_sort(arr) 

    print("Сортировка вставкой:", arr) 

    print(f"Количество сравнений: {count_if}, Количество перестановок: {count_move}") 

    input('Чтобы продолжить, нажмите Enter')
Максим Жук
Максим Жук
2 415
Лучший ответ
Александр Рычков не помогает
Александр Рычков да
у меня тоже самое
прога должна считать колво перестановок
Александр Рычков или вообще не должно быть пререстановок
Александр Рычков спасибо большое как мне вас отблагодарить
В методе вставок НЕТ перестановок. Есть лишь копирование элементов. Но temp = mas[i] и mas[j + 1] = temp - это тоже копирование. И, кстати, одна перестановка равна трём копированиям.

Основная проблема в том, что в insertion_sort ты передаёшь массив, который уже отсортирован buble_sort.

Код insertion_sort пришлось усложнить - ради правильного подсчёта количества сравнений и копирований.
 import random



def insertion_sort(mas):

  count_if, count_copy = 0, 0

  for i in range(1, len(mas)):

    count_if += 1

    if mas[i] >= mas[i - 1]: continue

    count_copy += 1

    temp, j = mas[i], i

    while True:

      count_copy += 1

      mas[j] = mas[j - 1]

      j -= 1

      if j == 0: break

      count_if += 1

      if temp >= mas[j - 1]: break

    count_copy += 1

    mas[j] = temp

  return mas, count_if, count_copy



def buble_sort(mas):

    count_if, count_swap = 0, 0

    for i in range(len(mas) - 1, 0, -1):

        flg = True

        for j in range(i):

            count_if += 1

            if mas[j] > mas[j + 1]:

                count_swap += 1

                mas[j], mas[j + 1], flg = mas[j + 1], mas[j], False

        if flg: break

    return mas, count_if, count_swap



for n in [16, 32, 64, 128, 256, 512, 1024]:

  arr = [random.randint(-100, 100) for _ in range(n)]

  print('Исходный массив:', arr)

  print('Чисел:', len(arr))

  res, count_if, count_swap = buble_sort(arr.copy())

  print('Пузырьковая сортировка:', res)

  print('Cравнений:', count_if, ' Перестановок:', count_swap, ' Копирований:', count_swap * 3)

  res, count_if, count_copy = insertion_sort(arr.copy())

  print('Сортировка вставками:', res)

  print('Cравнений:', count_if, ' Копирований:', count_copy)

  input('Чтобы продолжить нажмите Enter')
Лескин Демьян
Лескин Демьян
91 875
Ваша программа содержит несколько ошибок:




Отступы: Python сильно зависит от отступов, и все блоки кода (такие как функции, циклы и условные выражения) требуют правильного отступа.






Использование randint: Чтобы использовать randint, вы должны импортировать модуль random.






Функция buble_sort: Эта функция не определена в вашей программе, но она используется в цикле в конце программы.






Возврат arr: Вы возвращаете arr в функции insertion_sort, которую не изменяли, поэтому она вернет исходный массив, а не отсортированный.




Вот исправленная версия вашей программы: 
 from random import randint 

 

def insertion_sort(mas): 

    count_if = 0 

    count_move = 0 

    for i in range(1, len(mas)): 

        temp = mas[i] 

        j = i - 1 

        count_if += 2 

        while j >= 0 and temp < mas[j]: 

            mas[j + 1] = mas[j] 

            j = j - 1 

            count_move+= 1 

            count_if+= 2 

        mas[j + 1] = temp 

        if j < 0:  

            count_if -= 1 

    return mas, count_if, count_move   

 

# Здесь нужно определить функцию buble_sort 

 

n_arr = [16,32,64,128,256,512,1024] 

for n in n_arr: 

    arr = [] 

    for i in range(n): 

        arr.append(randint(-100, 100)) 

    print("Исходный массив ", arr) 

    print("======Количество символов====== ", n) 

     

    # предполагается, что функция buble_sort определена 

    arr, count_if, count_move = buble_sort(arr)   

    print("Пузырьковая сортировка", arr) 

    print(f"Количество сравнений: {count_if} " f"Количество перестановок: {count_move}") 

     

    arr, count_if, count_move =insertion_sort(arr) 

    print("Сортировка вставкой ", arr) 

    print(f"Количество сравнений: {count_if} " f"Количество перестановок: {count_move}") 

 

input('Чтобы продолжить нажмите Enter')

Пожалуйста, обратите внимание, что вам потребуется реализовать функцию buble_sort.
Саша Неважно
Саша Неважно
56 728

Похожие вопросы