Как отсортировать массив по возрастанию c
Array.Sort Method is used to sort elements in a one-dimensional array. There are 17 methods in the overload list of this method as follows:
Here we will discuss the first 4 methods.
Sort<T>(T[]) Method
This method sorts the elements in an Array using the IComparable<T> generic interface implementation of each element of the Array.
Syntax: public static void Sort<T> (T[] array);
Parameter:
array: It is the one dimensional, zero-based Array which is to be sorted.
Exceptions:
- ArgumentNullException: If the array is null.
- InvalidOperationException: If one or more elements in the array do not implement the IComparable<T> generic interface.
Example:
Sort<T>(T[], IComparer<T>) Method
This method Sorts the elements in an Array using the specified IComparer<T> generic interface.
- T : It is the type of the elements of the array.
- array : It is the one-dimensional Array which is to be sorted.
- comparer : It is the IComparer<T> generic interface implementation to use when comparing elements or null to use the IComparable<T> generic interface implementation of each element.
Exceptions:
- ArgumentNullException: If the array is null.
- InvalidOperationException: If the comparer is null and there is no implementation of the IComparable<T> generic interface.
- ArgumentException:
Example:
Array.Sort<T>(T[], Int32, Int32) Method
This method sorts the elements in a range of in an Array using the IComparable<T> generic interface implementation of each element of the Array.
Sorting an array in C?
Which is the best sorting technique to sort the following array and if there are duplicates how to handle them:
Also which is the best sorting technique of all?
5 Answers 5
In C, you can use the built in qsort command:
To answer the second part of your question: an optimal (comparison based) sorting algorithm is one that runs with O(n log(n)) comparisons. There are several that have this property (including quick sort, merge sort, heap sort, etc.), but which one to use depends on your use case.
As a side note, you can sometime do better than O(n log(n)) if you know something about your data — see the wikipedia article on Radix Sort
In your particular case the fastest sort is probably the one described in this answer. It is exactly optimized for an array of 6 ints and uses sorting networks. It is 20 times (measured on x86) faster than library qsort. Sorting networks are optimal for sort of fixed length arrays. As they are a fixed sequence of instructions they can even be implemented easily by hardware.
Generally speaking there is many sorting algorithms optimized for some specialized case. The general purpose algorithms like heap sort or quick sort are optimized for in place sorting of an array of items. They yield a complexity of O(n.log(n)), n being the number of items to sort.
The library function qsort() is very well coded and efficient in terms of complexity, but uses a call to some comparizon function provided by user, and this call has a quite high cost.
For sorting very large amount of datas algorithms have also to take care of swapping of data to and from disk, this is the kind of sorts implemented in databases and your best bet if you have such needs is to put datas in some database and use the built in sort.
Язык Си в примерах/Сортировка
Задача «сортировки» (упорядочения) — одна из первых интересных и сложных задач теории алгоритмов. Общие принципы освещает статья «Алгоритмы сортировки», здесь же мы рассматриваем способы упорядочения посредством языка Си.
Содержание
Метод «пузырька» [ править ]
Один из простейших алгоритмов решения — метод «пузырька».
Понятно, что после первого «пробега» самый большой элемент массива окажется на последнем месте. После второго пробега мы будем уверены, что второй по величине элемент находится на предпоследнем месте.
Решив эту задачу, вы докажете, что метод «пузырька» решает задачу сортировки.
Функция qsort из библиотеки stdlib [ править ]
Два оператора for, в которых происходит сортировка, можно заменить на одну строку:
Это функция, описанная в стандартной библиотеке ANSI C и объявлена в заголовочном файле stdlib.h.
Поэтому в начале программы нужно добавить
Функцией qsort можно упорядочивать объекты любой природы. По сути, она предназначена упорядочивать множества блоков байтов равной длины. Второй аргумент функции — это число таких блоков, третий аргумент — длина каждого блока. Первый аргумент — это адрес, где находится начало первого блока (предполагается, что блоки в памяти расположены друг за другом подряд).
Четвёртый аргумент функции qsort — это имя функции, которая умеет сравнивать два элемента массива. В нашем случае это
В силу указанной универсальности функции сортировки, функция сравнения получает в качества аргумента адреса двух блоков, которые нужно сравнить и возвращает 1, 0 или -1:
положительное значение, если a > b 0, если a == b отрицательное значение, если a < b
Поскольку у нас блоки байт — это целые числа (в 32-битной архитектуре это четырёхбайтовые блоки), то необходимо привести данные указатели типа (const void*) к типу (int *) и осуществляется это с помощью дописывания перед указателем выражения «(const int*)». Затем нужно получить значение переменной типа int, которая лежит по этому адресу. Это делается с помощью дописывания спереди звездочки.
Таким образом, мы получили следующую программу
Динамическое выделение памяти [ править ]
Ниже приведена программа, где память под массив выделяется динамически:
Функция malloc (от англ. memory allocation — выделение памяти) делает запрос к ядру операционной системы по выделению заданного количества байт. Единственный аргумент этой функции — число байт, которое вам нужно. В качестве результата функция возвращает указатель на начало выделенной памяти. Указатель на начало выделенной памяти &mbsah — это адрес ячейки памяти, начиная с которого идут N байт, которые вы можете использовать под любые свои нужды. Всю память, которая была выделена с помощью функции malloc, нужно освобождать с помощью функции free. Аргумент функции free — это указатель на начало выделенной когда-то памяти.
Программа упорядочения строк в алфавитном порядке [ править ]
Обратите внимание на сложное приведение типов.
Функция strcmp, объявленная в файле string.h имеет следующий прототип:
То есть функция получает два аргумента — указатели на кусочки памяти, где хранятся элементы типа char, то есть два массива символов, которые не могут быть изменены внутри функции strcmp (запрет на изменение задается с помощью модификатора const) [1] .
В то же время в качестве четвертого элемента функция qsort хотела бы иметь функцию типа
В языке Си можно осуществлять приведение типов являющихся типами функции. В данном примере тип
Алгоритмы сортировки: реализация на С++
Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.
Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.
Но есть одно «но». Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.
В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.
В этой статье приведены примеры реализации стандартных алгоритмов сортировки.
Сортировка выбором (Selection sort)
Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.
Код C++
Пузырьковая сортировка (Bubble sort)
При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива.
Код C++
Сортировка вставками (Insertion sort)
При сортировке вставками массив разбивается на две области: упорядоченную и и неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом проходе первый элемент из неупорядоченной области изымается и помещается в правильном положении в упорядоченной области.
На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной области сокращается на 1.
Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i].
Код C++
Сортировка слиянием (Merge sort)
При рекурсивной сортировке слиянием массив сначала разбивается на мелкие кусочки — на первом этапе — на состоящие из одного элемента. Затем эти кусочки объединяются в более крупные кусочки — по два элемента и элементы при этом сравниваются, а в результате в новом кусочке меньший элемент занимает место слева, а больший — справа. Далее происходит слияние в ещё более крупные кусочки и так до конца алгоритма, когда все кусочки будут объединены в один, уже отсортированный массив. Если есть интерес, есть статья о рекурсивных функциях.
Код C++
Быстрая сортировка (Quick sort)
Быстрая сортировка использует алгоритм «разделяй и властвуй». Она начинается с разбиения исходного массива на две области. Эти части находятся слева и справа от отмеченного элемента, называемого опорным. В конце процесса одна часть будет содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше опорного.