1 практика
.pdfПриложение Б
(обязательное)
Быстрая сортировка
using System; namespace bistraya
{
static class MainProgram
{
static void Main(string[] args)
{
Console.WriteLine("Быстрая сортировка");
Console.Write("Введите массив: ");
int[] QuickTest = ReadIntArray();
Console.Write("Отсортированный массив: ");
foreach (int i in QuickSort.Sort(QuickTest, 0, QuickTest.Length - 1))
{
Console.Write(i + " ");
}
Console.WriteLine();
Console.WriteLine();
}
static int[] ReadIntArray()
{
string line = Console.ReadLine(); string[] nums = line.Split(' ');
int[] array = new int[nums.Length];
11
for (int i = 0; i < nums.Length; i++)
{
array[i] = Convert.ToInt32(nums[i]);
}
return array;
}
}
public static class QuickSort
{
public static int[] Sort(int[] input, int leftIndex, int rightIndex)
{
var i = leftIndex; var j = rightIndex;
var pivot = input[leftIndex];
while (i <= j)
{
while (input[i] < pivot)
{
i++;
}
while (input[j] > pivot)
{
j--;
}
if (i <= j)
12
{
Swap(ref input[i], ref input[j]); i++;
j--;
}
}
if (leftIndex < j) Sort(input, leftIndex, j);
if (i < rightIndex) Sort(input, i, rightIndex);
return input;
}
static void Swap(ref int f1, ref int f2)
{
int temp = f2; f2 = f1;
f1 = temp;
}
}
}
13
Приложение В
(обязательное)
Сортировка методом Шелла
import random import math mas = []
a = 100000 count = 0
b = int(input())
for l in range(0,100000): count+=1
x1 = random.randint(1,a) mas.append(x1)
if count==b: break
def shellSort(array): n = len(array)
k = int(math.log2(n)) interval = 2**k -1 while interval > 0:
for i in range(interval, n): temp = array[i]
j = i
while j >= interval and array[j - interval] > temp: array[j] = array[j - interval]
j -= interval array[j] = temp
k -= 1
interval = 2**k -1 return array
shellSort(mas) print (mas)
14