def selection_sort(arr): count_if = 0 count_move = 0 for i in range(len(arr)): minimum = i for j in range(i + 1, len(arr)): count_if += 1 if arr[j] < arr[minimum]: minimum = j count_move += 1 arr[minimum], arr[i] = arr[i], arr[minimum]
return arr, count_if, count_move
n_arr = [30,45,69,105,159,240,360] 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 = selection_sort(arr) print("Сортировка отбором ", arr) print(f"Количество сравнений: {count_if} " f"Количество перестановок: {count_move}") input('Чтобы продолжить нажмите Enter')
Исходный массив [90, 30, -95, -84, -15, -81, 49, -4, 58, 9, -19, 94, -43, -81, -5, 64, -31, 17, 44, 66, -92, 37, -11, 27, 46, -29, 58, -31, 86, -88]
======Количество символов====== 30
Пузырьковая сортировка [-95, -92, -88, -84, -81, -81, -43, -31, -31, -29, -19, -15, -11, -5, -4, 9, 17, 27, 30, 37, 44, 46, 49, 58, 58, 64, 66, 86, 90, 94]
Количество сравнений: 435 Количество перестановок: 203
Сортировка отбором [-95, -92, -88, -84, -81, -81, -43, -31, -31, -29, -19, -15, -11, -5, -4, 9, 17, 27, 30, 37, 44, 46, 49, 58, 58, 64, 66, 86, 90, 94]
Количество сравнений: 435 Количество перестановок: 30
Исходный массив [82, -92, 82, -25, -33, 82, 80, 85, 23, -12, 11, -47, -41, -69, 100, 81, -96, -67, 83, -92, -9, 64, 34, 41, 54, 37, 92, -43, 19, -60, 53, 15, -84, -11, -96, 77, -95, 30, 88, -56, 96, 56, -21, 23, -52]
======Количество символов====== 45
Пузырьковая сортировка [-96, -96, -95, -92, -92, -84, -69, -67, -60, -56, -52, -47, -43, -41, -33, -25, -21, -12, -11, -9, 11, 15, 19, 23, 23, 30, 34, 37, 41, 53, 54, 56, 64, 77, 80, 81, 82, 82, 82, 83, 85, 88, 92, 96, 100]
Количество сравнений: 990 Количество перестановок: 525
Сортировка отбором [-96, -96, -95, -92, -92, -84, -69, -67, -60, -56, -52, -47, -43, -41, -33, -25, -21, -12, -11, -9, 11, 15, 19, 23, 23, 30, 34, 37, 41, 53, 54, 56, 64, 77, 80, 81, 82, 82, 82, 83, 85, 88, 92, 96, 100]
Количество сравнений: 990 Количество перестановок: 45
Исходный массив [69, -10, -56, -100, 85, 24, 34, -9, -19, 20, 61, -58, -89, -26, 67, -84, -34, 34, 51, -84, 62, 35, -48, 5, 71, -55, -37, -32, 29, 41, -68, -25, 97, -88, 11, -95, -24, -31, -15, -17, -67, -78, -78, -25, -2, -90, -54, 81, 68, -62, 76, -41, -12, -21, 76, -75, 57, -12, -87, -54, -43, -74, 74, -58, -99, 42, 57, 65, -9]
======Количество символов====== 69
Пузырьковая сортировка [-100, -99, -95, -90, -89, -88, -87, -84, -84, -78, -78, -75, -74, -68, -67, -62, -58, -58, -56, -55, -54, -54, -48, -43, -41, -37, -34, -32, -31, -26, -25, -25, -24, -21, -19, -17, -15, -12, -12, -10, -9, -9, -2, 5, 11, 20, 24, 29, 34, 34, 35, 41, 42, 51, 57, 57, 61, 62, 65, 67, 68, 69, 71, 74, 76, 76, 81, 85, 97]
Количество сравнений: 2346 Количество перестановок: 1217
Сортировка отбором [-100, -99, -95, -90, -89, -88, -87, -84, -84, -78, -78, -75, -74, -68, -67, -62, -58, -58, -56, -55, -54, -54, -48, -43, -41, -37, -34, -32, -31, -26, -25, -25, -24, -21, -19, -17, -15, -12, -12, -10, -9, -9, -2, 5, 11, 20, 24, 29, 34, 34, 35, 41, 42, 51, 57, 57, 61, 62, 65, 67, 68, 69, 71, 74, 76, 76, 81, 85, 97]
Количество сравнений: 2346 Количество перестановок: 69
Исходный массив [-67, 69, 45, -98, 3, -63, 7, 59, 25, -54, 65, -15, -89, 6, -41, -13, 30, 55, -26, 74, -5, -50, -100, 67, -94, 32, 37, 21, -50, -49, 88, 35, 90, 23, -96, -32, 86, -68, 57, 29, 42, 96, 81, -92, 82, 94, -55, -74, -55, -77, 66, -17, 93, 35, -94, 17, -79, 87, 5, -71, -75, 2, 83, 17, 35, 100, 70, -24, 1, 74, 33, -89, -72, -78, -54, -38, -29, -22, -54, 18, -9, -59, 85, -53, 71, 71, 73, -66, 67, 63, 31, -71, -75, -37, -8, 19, -22, 14, 82, -64, -16, -63, -71, -29, 5]
======Количество символов====== 105
Пузырьковая сортировка [-100, -98, -96, -94, -94, -92, -89, -89, -79, -78, -77, -75, -75, -74, -72, -71, -71, -71, -68, -67, -66, -64, -63, -63, -59, -55, -55, -54, -54, -54, -53, -50, -50, -49, -41, -38, -37, -32, -29, -29, -26, -24, -22, -22, -17, -16, -15, -13, -9, -8, -5, 1, 2, 3, 5, 5, 6, 7, 14, 17, 17, 18, 19, 21, 23, 25, 29, 30, 31, 32, 33, 35, 35, 35, 37, 42, 45, 55, 57, 59, 63, 65, 66, 67, 67, 69, 70, 71, 71, 73, 74, 74, 81, 82, 82, 83, 85, 86, 87, 88, 90, 93, 94, 96, 100]
Количество сравнений: 5460 Количество перестановок: 2789
Сортировка отбором [-100, -98, -96, -94, -94, -92, -89, -89, -79, -78, -77, -75, -75, -74, -72, -71, -71, -71, -68, -67, -66, -64, -63, -63, -59, -55, -55, -54, -54, -54, -53, -50, -50, -49, -41, -38, -37, -32, -29, -29, -26, -24, -22, -22, -17, -16, -15, -13, -9, -8, -5, 1, 2, 3, 5, 5, 6, 7, 14, 17, 17, 18, 19, 21, 23, 25, 29, 30, 31, 32, 33, 35, 35, 35, 37, 42, 45, 55, 57, 59, 63, 65, 66, 67, 67, 69, 70, 71, 71, 73, 74, 74, 81, 82, 82, 83, 85, 86, 87, 88, 90, 93, 94, 96, 100]
Количество сравнений: 5460 Количество перестановок: 105
Исходный массив [-65, 45, 23, -87, -13, 23, 8, 88, 68, -34, 28, 42, -64, -62, 49, -75, -50, -81, 15, -45, -72, -92, -37, -17, -58, 38, 33, -51, 90, -86, 50, -18, -43, -28, 8, -35, 14, 99, -54, -92, -81, 28, 85, 34, 42, -66, 32, -71, 26, -8, -36, 47, 9, -8, 0, -90, 73, 33, -67, -14, -58, -59, -82, -43, -55, 20, -72, 60, -64, 86, 48, 29, -79, 41, 4, -24, -78, -28, 48, -32, 63, 40, -16, -7, 46, 78, 82, -53, 24, 64, -81, 21, 9, 19, 95, 75, -65, -42, 16, 24, 15, 95, -19, -48, 94, -8, 98, 43, -60, 82, 1, 26, -31, -20, -30, 99, -29, 0, -51, -1, -41, -83, 16, 82, -96, 29, -64, -17, 91, 45, -16, 89, -57, -61, -66, 23, 22, 47, 98, -94, -11, 38, 93, 95, 37, 96, -24, 78, -24, 96, 38, -71, -66, -12, -60, 26, 2, 48, 68]
======Количество символов====== 159
Пузырьковая сортировка [-96, -94, -92, -92, -90, -87, -86, -83, -82, -81, -81, -81, -79, -78, -75, -72, -72, -71, -71, -67, -66, -66, -66, -65, -65, -64, -64, -64, -62, -61, -60, -60, -59, -58, -58, -57, -55, -54, -53, -51, -51, -50, -48, -45, -43, -43, -42, -41, -37, -36, -35, -34, -32, -31, -30, -29, -28, -28, -24, -24, -24, -20, -19, -18, -17, -17, -16, -16, -14, -13, -12, -11, -8, -8, -8, -7, -1, 0, 0, 1, 2, 4, 8, 8, 9, 9, 14, 15, 15, 16, 16, 19, 20, 21, 22, 23, 23, 23, 24, 24, 26, 26, 26, 28, 28, 29, 29, 32, 33, 33, 34, 37, 38, 38, 38, 40, 41, 42, 42, 43, 45, 45, 46, 47, 47, 48, 48, 48, 49, 50, 60, 63, 64, 68, 68, 73, 75, 78, 78, 82, 82, 82, 85, 86, 88, 89, 90, 91, 93, 94, 95, 95, 95, 96, 96, 98, 98, 99, 99]
Количество сравнений: 12561 Количество перестановок: 5526
Сортировка отбором [-96, -94, -92, -92, -90, -87, -86, -83, -82, -81, -81, -81, -79, -78, -75, -72, -72, -71, -71, -67, -66, -66, -66, -65, -65, -64, -64, -64, -62, -61, -60, -60, -59, -58, -58, -57, -55, -54, -53, -51, -51, -50, -48, -45, -43, -43, -42, -41, -37, -36, -35, -34, -32, -31, -30, -29, -28, -28, -24, -24, -24, -20, -19, -18, -17, -17, -16, -16, -14, -13, -12, -11, -8, -8, -8, -7, -1, 0, 0, 1, 2, 4, 8, 8, 9, 9, 14, 15, 15, 16, 16, 19, 20, 21, 22, 23, 23, 23, 24, 24, 26, 26, 26, 28, 28, 29, 29, 32, 33, 33, 34, 37, 38, 38, 38, 40, 41, 42, 42, 43, 45, 45, 46, 47, 47, 48, 48, 48, 49, 50, 60, 63, 64, 68, 68, 73, 75, 78, 78, 82, 82, 82, 85, 86, 88, 89, 90, 91, 93, 94, 95, 95, 95, 96, 96, 98, 98, 99, 99]
Количество сравнений: 12561 Количество перестановок: 159
Исходный массив [-11, 52, 31, -28, 79, -54, 13, -71, -22, -45, 51, -85, 94, 18, -56, -81, 89, 59, -24, -99, 15, -65, -95, -7, 44, -16, -59, 14, 77, 80, 56, 86, 81, 34, 44, -47, -50, -53, -54, 42, 97, -31, -9, -74, 50, -92, -4, -68, -14, -61, 83, -34, 55, -47, 48, -7, -91, 97, -38, 92, -14, 77, -4, -60, -81, -86, 65, 9, -84, 1, 69, -33, -64, -79, 17, -93, 93, -51, -29, 5, 44, -33, -77, 86, -50, 75, -63, -46, 37, -66, 48, 12, 49, 67, 51, 74, 8, 22, -46, -35, -30, -20, -76, -37, 44, -74, 44, 27, 18, 24, 10, 58, -70, -21, -2, 18, -60, 74, -64, 95, -84, -14, 94, -62, 21, -47, 86, 72, 60, 35, 61, 12, -7, -69, 82, -10, -98, 17, 82, 66, 35, -3, 46, 44, 17, 45, -37, 77, -85, -67, -55, 33, 19, -18, 69, 77, 92, -29, 74, -38, 99, -23, 53, 40, -75, 66, 94, 30, -46, 78, -72, -5, 73, -52, 62, 57, -100, -96, -8, -55, -7, -96, 66, 4, 79, 8, 82, -24, -90, -76, -6, -18, -5, -5, 85, -35, 98, 76, -1, 76, 99, 65, -4, -44, 69, -14, -53, 56, -85, 36, -59, -95, -11, -27, -87, -82, 52, -88, 15, -37, 74, -62, -26, -92, 4, 72, -13, 28, -21, -49, -12, 94, 81, 78, -95, -55, -20, 25, 44, -26]
======Количество символов====== 240
Пузырьковая сортировка [-100, -99, -98, -96, -96, -95, -95, -95, -93, -92, -92, -91, -90, -88, -87, -86, -85, -85, -85, -84, -84, -82, -81, -81, -79, -77, -76, -76, -75, -74, -74, -72, -71, -70, -69, -68, -67, -66, -65, -64, -64, -63, -62, -62, -61, -60, -60, -59, -59, -56, -55, -55, -55, -54, -54, -53, -53, -52, -51, -50, -50, -49, -47, -47, -47, -46, -46, -46, -45, -44, -38, -38, -37, -37, -37, -35, -35, -34, -33, -33, -31, -30, -29, -29, -28, -27, -26, -26, -24, -24, -23, -22, -21, -21, -20, -20, -18, -18, -16, -14, -14, -14, -14, -13, -12, -11, -11, -10, -9, -8, -7, -7, -7, -7, -6, -5, -5, -5, -4, -4, -4, -3, -2, -1, 1, 4, 4, 5, 8, 8, 9, 10, 12, 12, 13, 14, 15, 15, 17, 17, 17, 18, 18, 18, 19, 21, 22, 24, 25, 27, 28, 30, 31, 33, 34, 35, 35, 36, 37, 40, 42, 44, 44, 44, 44, 44, 44, 44, 45, 46, 48, 48, 49, 50, 51, 51, 52, 52, 53, 55, 56, 56, 57, 58, 59, 60, 61, 62, 65, 65, 66, 66, 66, 67, 69, 69, 69, 72, 72, 73, 74, 74, 74, 74, 75, 76, 76, 77, 77, 77, 77, 78, 78, 79, 79, 80, 81, 81, 82, 82, 82, 83, 85, 86, 86, 86, 89, 92, 92, 93, 94, 94, 94, 94, 95, 97, 97, 98, 99, 99]
Количество сравнений: 28680 Количество перестановок: 14014
Сортировка отбором [-100, -99, -98, -96, -96, -95, -95, -95, -93, -92, -92, -91, -90, -88, -87, -86, -85, -85, -85, -84, -84, -82, -81, -81, -79, -77, -76, -76, -75, -74, -74, -72, -71, -70, -69, -68, -67, -66, -65, -64, -64, -63, -62, -62, -61, -60, -60, -59, -59, -56, -55, -55, -55, -54, -54, -53, -53, -52, -51, -50, -50, -49, -47, -47, -47, -46, -46, -46, -45, -44, -38, -38, -37, -37, -37, -35, -35, -34, -33, -33, -31, -30, -29, -29, -28, -27, -26, -26, -24, -24, -23, -22, -21, -21, -20, -20, -18, -18, -16, -14, -14, -14, -14, -13, -12, -11, -11, -10, -9, -8, -7, -7, -7, -7, -6, -5, -5, -5, -4, -4, -4, -3, -2, -1, 1, 4, 4, 5, 8, 8, 9, 10, 12, 12, 13, 14, 15, 15, 17, 17, 17, 18, 18, 18, 19, 21, 22, 24, 25, 27, 28, 30, 31, 33, 34, 35, 35, 36, 37, 40, 42, 44, 44, 44, 44, 44, 44, 44, 45, 46, 48, 48, 49, 50, 51, 51, 52, 52, 53, 55, 56, 56, 57, 58, 59, 60, 61, 62, 65, 65, 66, 66, 66, 67, 69, 69, 69, 72, 72, 73, 74, 74, 74, 74, 75, 76, 76, 77, 77, 77, 77, 78, 78, 79, 79, 80, 81, 81, 82, 82, 82, 83, 85, 86, 86, 86, 89, 92, 92, 93, 94, 94, 94, 94, 95, 97, 97, 98, 99, 99]
Количество сравнений: 28680 Количество перестановок: 240
Исходный массив [71, 65, 95, 70, -32, -68, 69, -14, 50, -60, -43, 81, -20, -28, 61, -83, -79, 89, -95, -66, -28, 66, 16, 9, -79, -61, -89, 31, 77, -44, 97, -91, 81, 22, 31, -73, -63, -48, 30, 79, 22, -68, 99, -41, 9, -28, -31, 45, 5, -87, 37, -90, -7, -96, 22, -26, 22, -80, 2, -100, 33, 63, 31, -72, 77, -73, -18, 25, -78, 59, -29, -28, 79, 16, 18, -39, -60, 9, 3, -25, -80, 76, 36, -63, 7, 33, -67, -44, -6, 100, -6, 58, -29, 9, 92, -57, 69, -56, 44, 16, -49, 34, -29, 43, 87, -58, -10, -58, 20, -58, -98, -54, 56, 52, -6, -67, -35, 81, 99, -53, -95, -53, 74, 76, 99, 25, -55, 45, 49, 13, 30, 15, 59, 75, -66, -70, 37, 90, -4, 39, 25, -63, -29, -76, 23, -97, 25, -4, -71, -42, 81, -79, -4, 50, -21, -36, -86, -64, -20, 73, -44, 92, 92, 66, -27, 58, -75, -89, 24, 10, 21, 21, 25, 69, -26, 37, -30, -82, -58, 75, 57, -48, -80, 94, 39, -43, -93, -84, -63, 79, -94, 60, -53, -24, 5, -58, 32, -55, -89, -27, -22, -46, 40, -37, 38, -10, 94, 51, 38, 42, -78, -88, -44, 55, -57, -17, 98, 9, -20, -63, -89, -24, -8, 41, -14, 29, 3, -50, 55, -94, 8, -66, -59, -27, -47, -31, 55, 30, 59, 23, 52, 46, -48, -56, 92, 69, 51, -95, -42, -92, 47, 51, -28, -62, 50, -30, 88, 97, 82, -28, 36, 45, -2, -11, 88, -59, -46, 35, 11, -21, -41, -54, 44, -11, -26, -96, 99, -2, 53, -100, 10, 13, 16, -53, -65, 42, -15, 81, 27, -64, 20, -76, 87, 72, 1, -32, 31, 6, 55, -63, 40, 66, 70, 17, 74, 5, 24, 85, 62, -96, -1, -22, 33, -19, 29, 68, 82, -24, 82, -65, 84, -17, 23, 69, 79, 67, -7, -37, 6, 88, 62, 96, 59, -58, -43, 89, -66, 3, 26, -43, 62, -31, -41, -64, -44, -39, 7, -50, 71, -76, 54, -69, 89, -19, -83, 45, 67, -86, 10, 44]
======Количество символов====== 360
Пузырьковая сортировка [-100, -100, -98, -97, -96, -96, -96, -95, -95, -95, -94, -94, -93, -92, -91, -90, -89, -89, -89, -89, -88, -87, -86, -86, -84, -83, -83, -82, -80, -80, -80, -79, -79, -79, -78, -78, -76, -76, -76, -75, -73, -73, -72, -71, -70, -69, -68, -68, -67, -67, -66, -66, -66, -66, -65, -65, -64, -64, -64, -63, -63, -63, -63, -63, -63, -62, -61, -60, -60, -59, -59, -58, -58, -58, -58, -58, -58, -57, -57, -56, -56, -55, -55, -54, -54, -53, -53, -53, -53, -50, -50, -49, -48, -48, -48, -47, -46, -46, -44, -44, -44, -44, -44, -43, -43, -43, -43, -42, -42, -41, -41, -41, -39, -39, -37, -37, -36, -35, -32, -32, -31, -31, -31, -30, -30, -29, -29, -29, -29, -28, -28, -28, -28, -28, -28, -27, -27, -27, -26, -26, -26, -25, -24, -24, -24, -22, -22, -21, -21, -20, -20, -20, -19, -19, -18, -17, -17, -15, -14, -14, -11, -11, -10, -10, -8, -7, -7, -6, -6, -6, -4, -4, -4, -2, -2, -1, 1, 2, 3, 3, 3, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13, 13, 15, 16, 16, 16, 16, 17, 18, 20, 20, 21, 21, 22, 22, 22, 22, 23, 23, 23, 24, 24, 25, 25, 25, 25, 25, 26, 27, 29, 29, 30, 30, 30, 31, 31, 31, 31, 32, 33, 33, 33, 34, 35, 36, 36, 37, 37, 37, 38, 38, 39, 39, 40, 40, 41, 42, 42, 43, 44, 44, 44, 45, 45, 45, 45, 46, 47, 49, 50, 50, 50, 51, 51, 51, 52, 52, 53, 54, 55, 55, 55, 55, 56, 57, 58, 58, 59, 59, 59, 59, 60, 61, 62, 62, 62, 63, 65, 66, 66, 66, 67, 67, 68, 69, 69, 69, 69, 69, 70, 70, 71, 71, 72, 73, 74, 74, 75, 75, 76, 76, 77, 77, 79, 79, 79, 79, 81, 81, 81, 81, 81, 82, 82, 82, 84, 85, 87, 87, 88, 88, 88, 89, 89, 89, 90, 92, 92, 92, 92, 94, 94, 95, 96, 97, 97, 98, 99, 99, 99, 99, 100]
Количество сравнений: 64620 Количество перестановок: 30574
Сортировка отбором [-100, -100, -98, -97, -96, -96, -96, -95, -95, -95, -94, -94, -93, -92, -91, -90, -89, -89, -89, -89, -88, -87, -86, -86, -84, -83, -83, -82, -80, -80, -80, -79, -79, -79, -78, -78, -76, -76, -76, -75, -73, -73, -72, -71, -70, -69, -68, -68, -67, -67, -66, -66, -66, -66, -65, -65, -64, -64, -64, -63, -63, -63, -63, -63, -63, -62, -61, -60, -60, -59, -59, -58, -58, -58, -58, -58, -58, -57, -57, -56, -56, -55, -55, -54, -54, -53, -53, -53, -53, -50, -50, -49, -48, -48, -48, -47, -46, -46, -44, -44, -44, -44, -44, -43, -43, -43, -43, -42, -42, -41, -41, -41, -39, -39, -37, -37, -36, -35, -32, -32, -31, -31, -31, -30, -30, -29, -29, -29, -29, -28, -28, -28, -28, -28, -28, -27, -27, -27, -26, -26, -26, -25, -24, -24, -24, -22, -22, -21, -21, -20, -20, -20, -19, -19, -18, -17, -17, -15, -14, -14, -11, -11, -10, -10, -8, -7, -7, -6, -6, -6, -4, -4, -4, -2, -2, -1, 1, 2, 3, 3, 3, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 9, 9, 9, 10, 10, 10, 11, 13, 13, 15, 16, 16, 16, 16, 17, 18, 20, 20, 21, 21, 22, 22, 22, 22, 23, 23, 23, 24, 24, 25, 25, 25, 25, 25, 26, 27, 29, 29, 30, 30, 30, 31, 31, 31, 31, 32, 33, 33, 33, 34, 35, 36, 36, 37, 37, 37, 38, 38, 39, 39, 40, 40, 41, 42, 42, 43, 44, 44, 44, 45, 45, 45, 45, 46, 47, 49, 50, 50, 50, 51, 51, 51, 52, 52, 53, 54, 55, 55, 55, 55, 56, 57, 58, 58, 59, 59, 59, 59, 60, 61, 62, 62, 62, 63, 65, 66, 66, 66, 67, 67, 68, 69, 69, 69, 69, 69, 70, 70, 71, 71, 72, 73, 74, 74, 75, 75, 76, 76, 77, 77, 79, 79, 79, 79, 81, 81, 81, 81, 81, 82, 82, 82, 84, 85, 87, 87, 88, 88, 88, 89, 89, 89, 90, 92, 92, 92, 92, 94, 94, 95, 96, 97, 97, 98, 99, 99, 99, 99, 100]
Количество сравнений: 64620 Количество перестановок: 360
Графики изменения числа сравнений и перестановок от размеров массивов сортировки
Блок-схема алгоритма
Вывод
В результате выполнения работы были выполнены все задания, изучены процессы алгоритмизации, выявлены изменения числа сравнений и перестановок от размеров массивов сортировки.
Do'stlaringiz bilan baham: |
