{ "version": "https:\/\/jsonfeed.org\/version\/1.1", "title": "Блоги: заметки с тегом алгоритми та структури даних", "_rss_description": "Автоматически собираемая лента заметок, написанных в блогах на Эгее", "_rss_language": "ru", "_itunes_email": "", "_itunes_categories_xml": "", "_itunes_image": false, "_itunes_explicit": "no", "home_page_url": "https:\/\/blogengine.ru\/blogs\/tags\/algoritmi-ta-strukturi-danih\/", "feed_url": "https:\/\/blogengine.ru\/blogs\/tags\/algoritmi-ta-strukturi-danih\/json\/", "icon": false, "authors": [ { "name": "Илья Бирман", "url": "https:\/\/blogengine.ru\/blogs\/", "avatar": false } ], "items": [ { "id": "119832", "url": "https:\/\/stefaniuk.website\/all\/sorting-algorithms\/", "title": "Алгоритмы сортировки", "content_html": "

Классификация<\/h2>\n

По методу сортировки: вставка, слияние, обмен<\/li>\n<\/ol>\n

Распространенные алгоритмы<\/h2>\n

Быстрая сортировка<\/li>\n<\/ul>\n

Ссылка на сайт с гифками, которые демонстрируют работу алгоритмов: https:\/\/www.toptal.com\/developers\/sorting-algorithms<\/a><\/p>\n

Сортировка пузырьком<\/h2>\n

Самая стандартная и простая сортировка. Выполняет проходы по массиву и перемещает наибольший элемент в конец массива.<\/p>\n

<\/td>\n Лучший вариант<\/td>\n Средний вариант<\/td>\n Худший вариант<\/td>\n<\/tr>\n

Степень сложности<\/td>\n O(n)<\/td>\n O(n^2)<\/td>\n O(n^2)<\/td>\n<\/tr>\n

Рост памяти<\/td>\n

O(1)<\/td>\n<\/tr>\n<\/table>\n<\/div>\n

public void Sort(int[] inputArray)\r\n{\r\n\tfor (int i = 0; i < inputArray.Length; i++) {\r\n\t\tfor (int j = 1; j < inputArray.Length; j++) {\r\n\t\t\tif (inputArray[j-1] > inputArray[j]) {\r\n\t\t\t\tSwap(inputArray, j-1, j);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}\r\n\r\npublic void Swap(int[] inputArray, int indexLeft, int indexRight)\r\n{\r\n\tif (indexLeft == indexRight) return;\r\n\tvar temp = inputArray[indexLeft];\r\n\tinputArray[indexLeft] = inputArray[indexRight];\r\n\tinputArray[indexRight] = temp;\r\n}<\/code><\/pre>Сортировка вставками<\/b>
\nТакже достаточно простой алгоритм, на каждом этапе которого выбирается один элемент массива, для которого осуществляется поиск позиции для вставки.<\/p>\n
\n\n\n\n\n<\/td>\n Лучший вариант<\/td>\n Средний вариант<\/td>\n Худший вариант<\/td>\n<\/tr>\n
Степень сложности<\/td>\n O(n)<\/td>\n O(n^2)<\/td>\n O(n^2)<\/td>\n<\/tr>\n
Рост памяти<\/td>\n O(1)<\/td>\n O(1)<\/td>\n O(1)<\/td>\n<\/tr>\n<\/table>\n<\/div>\npublic static void Sort(int[] inputArray)\r\n{\r\n\tint currentElementIndex= 1;\r\n\twhile (currentElementIndex < inputArray.Length)\r\n\t{\r\n\t\tif (inputArray[currentElementIndex] < inputArray[currentElementIndex - 1]) {\r\n\t\t\tvar newIndex = FindIndex(inputArray, inputArray[currentElementIndex]);\r\n\t\t\tInsert(inputArray, newIndex, currentElementIndex);\r\n\t\t}\r\n\t\tcurrentElementIndex++;\r\n\t}\r\n}\r\n\r\npublic static int FindIndex(int[] inputArray, int element)\r\n{\r\n\tfor (int i = 0; i < inputArray.Length; i++)\r\n\t{\r\n\t\tif (inputArray[i] > element) {\r\n\t\t\treturn i;\r\n\t\t}\r\n\t}\r\n\treturn 0;\r\n}\r\n\r\npublic static void Insert(int[] inputArray, int indexLeft, int indexRight)\r\n{\r\n\tif (indexLeft == indexRight) return;\r\n\tvar temp = inputArray[indexLeft];\r\n\tinputArray[indexLeft] = inputArray[indexRight];\r\n\tfor (int current = indexRight; current > indexLeft; current--) {\r\n\t\tinputArray[current] = inputArray[current-1];\r\n\t}\r\n\tinputArray[indexLeft + 1] = temp;\r\n}<\/code><\/pre>Сортировка выбором<\/b>
\nНа каждом своем шаге отыскивает наименьший элемент в неотсортированной части массива и устанавливает его в соответствующую позицию массива.<\/p>\n
\n\n\n\n\n<\/td>\n Лучший вариант<\/td>\n Средний вариант<\/td>\n Худший вариант<\/td>\n<\/tr>\n
Степень сложности<\/td>\n O(n)<\/td>\n O(n^2)<\/td>\n O(n^2)<\/td>\n<\/tr>\n
Рост памяти<\/td>\n O(1)<\/td>\n O(1)<\/td>\n O(1)<\/td>\n<\/tr>\n<\/table>\n<\/div>\npublic static void Sort(int[] input) {\r\n\tfor (int i = 0; i < input.Length; i++) {\r\n\t\tvar smallestElementIndex = FindIndexOfSmallestElement(input, i);\r\n\t\tSwap(input, smallestElementIndex, i);\r\n\t}\r\n}\r\n\r\npublic static int FindIndexOfSmallestElement(int[] input, int startFrom = 0) {\r\n\tvar smallestElementValue = input[startFrom];\r\n\tvar smallestElementIndex = startFrom;\r\n\tfor (int i = startFrom + 1; i < input.Length; i++)\r\n\t{\r\n\t\tif (smallestElementValue > input[i]) {\r\n\t\t\tsmallestElementValue = input[i];\r\n\t\t\tsmallestElementIndex = i;\r\n\t\t}\r\n\t}\r\n\treturn smallestElementIndex;\r\n}\r\n\r\npublic static void Swap(int[] input, int indexLeft, int indexRight)\r\n{\r\n\tif (indexLeft == indexRight) return;\r\n\tvar temp = input[indexLeft];\r\n\tinput[indexLeft] = input[indexRight];\r\n\tinput[indexRight] = temp;\r\n}<\/code><\/pre>Сортировка слиянием<\/b>
\nРазбивает массив на подмассивы примерно одинакового размера, рекурсивно разбивает до тех пор, пока размер массива будет равен 1. После этого происходит сортировка частей и их соединение в один.<\/p>\n
\n\n\n\n\n<\/td>\n Лучший вариант<\/td>\n Средний вариант<\/td>\n Худший вариант<\/td>\n<\/tr>\n
Степень сложности<\/td>\n O(n log n)<\/td>\n O(n log n)<\/td>\n O(n log n)<\/td>\n<\/tr>\n
Рост памяти<\/td>\n O(n)<\/td>\n O(n)<\/td>\n O(n)<\/td>\n<\/tr>\n<\/table>\n<\/div>\npublic static void Sort(int[] input) {\r\n\tif (input.Length <= 1) {\r\n\t\treturn;\r\n\t}\r\n\t\r\n\t\/\/ Поделили массивы\r\n\tvar leftSize = input.Length \/ 2;\r\n\tvar rightSize = input.Length - leftSize;\r\n\tvar left = new int[leftSize];\r\n\tvar right = new int[rightSize];\r\n\t\r\n\t\/\/ Скопировали данные из основного массива\r\n\tArray.Copy(input, 0, left, 0, leftSize);\r\n\tArray.Copy(input, leftSize, right, 0, rightSize);\r\n\t\r\n\tSort(left);\r\n\tSort(right);\r\n\t\r\n\tMerge(input, left, right);\r\n}\r\n\r\npublic static void Merge(int[] input, int[] left, int[] right) {\r\n\tvar leftIndex = 0;\r\n\tvar rightIndex = 0;\r\n\tvar leftAndRightSize = left.Length + right.Length;\r\n\t\r\n\tfor (int i = 0; i < leftAndRightSize; i++) {\r\n\t\tif (leftIndex >= left.Length) {\r\n\t\t\tinput[i] = right[rightIndex];\r\n\t\t\trightIndex++;\r\n\t\t}\r\n\t\telse if (rightIndex >= right.Length) {\r\n\t\t\tinput[i] = left[leftIndex];\r\n\t\t\tleftIndex++;\r\n\t\t}\r\n\t\telse if (left[leftIndex] < right[rightIndex]) {\r\n\t\t\tinput[i] = left[leftIndex];\r\n\t\t\tleftIndex++;\r\n\t\t}\r\n\t\telse {\r\n\t\t\tinput[i] = right[rightIndex];\r\n\t\t\trightIndex++;\r\n\t\t}\r\n\t}\r\n}<\/code><\/pre>Быстрая сортировка<\/b>
\nОдин из самых быстрых алгоритмов, о чем говорит название.<\/p>\n
Этапы сортировки:
\n• Случайный выбор опорного элемента массива (pivotValue), относительно которого переупорядочиваются элементы массива.
\n• Переместить все значения, которые больше опорного, вправо, а все значения, что меньше опорного, влево.
\n• Повторить алгоритм для неотсортированной левой и правой части массива, пока каждый элемент не окажется на своей позиции.<\/p>\n
\n\n\n\n\n<\/td>\n Лучший вариант<\/td>\n Средний вариант<\/td>\n Худший вариант<\/td>\n<\/tr>\n
Степень сложности<\/td>\n O(n log n)<\/td>\n O(n log n)<\/td>\n O(n^2)<\/td>\n<\/tr>\n
Рост памяти<\/td>\n O(1)<\/td>\n O(1)<\/td>\n O(1)<\/td>\n<\/tr>\n<\/table>\n<\/div>\npublic static void Sort(int[] input, int leftIndex, int rightIndex) {\r\n\tvar i = leftIndex;\r\n\tvar j = rightIndex;\r\n\tvar pivot = input[(leftIndex + rightIndex) >> 1];\r\n\t\r\n\twhile (i <= j) {\r\n\t\twhile (input[i] < pivot) {\r\n\t\t\ti++;\r\n\t\t}\r\n\t\twhile (input[j] > pivot) {\r\n\t\t\tj--;\r\n\t\t}\r\n\t\t\r\n\t\tif (i <= j) {\r\n\t\t\tSwap(input, i, j);\r\n\t\t\tj--;\r\n\t\t\ti++;\r\n\t\t}\r\n\t\t\r\n\t\tif (leftIndex < j) {\r\n\t\t\tSort(input, leftIndex, j);\r\n\t\t}\r\n\t\t\r\n\t\tif (rightIndex > i) {\r\n\t\t\tSort(input, i, rightIndex);\r\n\t\t}\r\n\t}\r\n}\r\n\r\npublic static void Swap(int[] input, int indexLeft, int indexRight)\r\n{\r\n\tif (indexLeft == indexRight) return;\r\n\tvar temp = input[indexLeft];\r\n\tinput[indexLeft] = input[indexRight];\r\n\tinput[indexRight] = temp;\r\n}<\/code><\/pre>",
            "date_published": "2019-08-01T01:05:53+05:00",
            "date_modified": "2023-06-03T04:50:49+05:00",
            "tags": [
                "алгоритми та структури даних",
                "программирование"
            ],
            "author": {
                "name": "Bohdan Stefaniuk",
                "url": "https:\/\/stefaniuk.website\/",
                "avatar": "https:\/\/stefaniuk.website\/pictures\/userpic\/userpic@2x.jpg?1565716580"
            },
            "_date_published_rfc2822": "Thu, 01 Aug 2019 01:05:53 +0500",
            "_rss_guid_is_permalink": "false",
            "_rss_guid": "119832",
            "_rss_enclosures": [],
            "_e2_data": {
                "is_favourite": false,
                "links_required": null,
                "og_images": []
            }
        }
    ],
    "_e2_version": 4079,
    "_e2_ua_string": "Aegea 11.0 (v4079e)"
}