---

using System;
using System.IO;
using System.Linq;
using System.Windows.Forms;
using System.Diagnostics;

namespace Sortirovka
{
    public partial class Form1 : Form
    {
        private string[] originalData; // исходные данные

        public Form1()
        {
            InitializeComponent();

            comboBox1.Items.AddRange(new string[]
            {
                "Пузырёк",
                "Вставками",
                "Быстрая сортировка"
            });

            comboBox1.SelectedIndex = 0;
        }

        // Открыть файл
        private void buttonOpen_Click(object sender, EventArgs e)
        {
            OpenFileDialog dialog = new OpenFileDialog();
            dialog.Filter = "Text files (*.txt)|*.txt";

            if (dialog.ShowDialog() == DialogResult.OK)
            {
                originalData = File.ReadAllLines(dialog.FileName);

                listBox1.Items.Clear();
                listBox1.Items.AddRange(originalData);

                labelCount.Text = "Строк: " + originalData.Length;
            }
        }

        // Сортировать
        private void buttonSort_Click(object sender, EventArgs e)
        {
            if (originalData == null) return;

            string[] data = (string[])originalData.Clone();
            bool ascending = !checkBoxDesc.Checked;

            Stopwatch sw = new Stopwatch();
            sw.Start();

            switch (comboBox1.SelectedItem.ToString())
            {
                case "Пузырёк":
                    BubbleSort(data, ascending);
                    break;

                case "Вставками":
                    InsertionSort(data, ascending);
                    break;

                case "Быстрая сортировка":
                    QuickSort(data, 0, data.Length - 1, ascending);
                    break;
            }

            sw.Stop();

            listBox1.Items.Clear();
            listBox1.Items.AddRange(data);

            labelTime.Text = "Время: " + sw.ElapsedMilliseconds + " мс";
        }

        // Сохранить
        private void buttonSave_Click(object sender, EventArgs e)
        {
            if (listBox1.Items.Count == 0) return;

            SaveFileDialog dialog = new SaveFileDialog();
            dialog.Filter = "Text files (*.txt)|*.txt";

            if (dialog.ShowDialog() == DialogResult.OK)
            {
                File.WriteAllLines(
                    dialog.FileName,
                    listBox1.Items.Cast<string>().ToArray()
                );

                MessageBox.Show("Файл сохранён!");
            }
        }

        // ================= СОРТИРОВКИ =================

        private void BubbleSort(string[] arr, bool asc)
        {
            int n = arr.Length;

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = 0; j < n - i - 1; j++)
                {
                    int cmp = arr[j].CompareTo(arr[j + 1]);

                    if ((asc && cmp > 0) || (!asc && cmp < 0))
                    {
                        string temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }

        private void InsertionSort(string[] arr, bool asc)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                string key = arr[i];
                int j = i - 1;

                while (j >= 0)
                {
                    int cmp = arr[j].CompareTo(key);

                    if ((asc && cmp > 0) || (!asc && cmp < 0))
                    {
                        arr[j + 1] = arr[j];
                        j--;
                    }
                    else break;
                }

                arr[j + 1] = key;
            }
        }

        private void QuickSort(string[] arr, int left, int right, bool asc)
        {
            if (left >= right) return;

            int i = left;
            int j = right;
            string pivot = arr[(left + right) / 2];

            while (i <= j)
            {
                while ((asc && arr[i].CompareTo(pivot) < 0) ||
                       (!asc && arr[i].CompareTo(pivot) > 0))
                    i++;

                while ((asc && arr[j].CompareTo(pivot) > 0) ||
                       (!asc && arr[j].CompareTo(pivot) < 0))
                    j--;

                if (i <= j)
                {
                    string temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;

                    i++;
                    j--;
                }
            }

            if (left < j) QuickSort(arr, left, j, asc);
            if (i < right) QuickSort(arr, i, right, asc);
        }
    }
}