Сортировкой называют набор операций, упорядочивающий элементы массива в соответствии с заданным отношением порядка. Например, в упорядоченном массиве A по возрастанию выполняются неравенства вида:
Вопрос о возрастании или убывании упорядоченного массива для нас не принципиален. Как правило, программы, сортирующие массив по возрастанию, легко изменяются для сортировки по убыванию.
Существует множество алгоритмов сортировки (пузырьковая сортировка, сортировка по дереву, быстрая сортировка, сортировка слиянием, сортировка Шелла и т. д.), они имеют большую практическую значимость, являются фундаментальными в некоторых областях информатики.
Здесь приводится самый распространенный и очень понятный алгоритм пузырьковой сортировки по возрастанию.
Название «Пузырьковая сортировка» происходит от образной интерпретации, по которой алгоритм заставляет «легкие» элементы мало-помалу всплывать на «поверхность».
Суть алгоритма такова. Начиная с первого, сравниваются два соседних элемента массива A[i] и A[i+l], если A[i] > A[i+1], то элементы меняются местами. В первый раз мы проходим массив начиная с индекса 1, до индекса n — 1, во второй — с 1 до n — 2 и т. д. Любой массив будет отсортирован за n-1 проходов. Таким образом, порядок сложности данного алгоритма (максимальное количество операций проверок и перестановок элементов массива) пропорционален n 2 /2, хотя массив может быть отсортирован уже после первого прохода.
Самоучитель C++ (22 серия) Visual Studio, Итоги №3, Сортировка массивов и матриц
a: array [1.. n] of Real;
Writeln (‘ введите ‘, n, ‘ элементов массива: ‘ ) ;
for i := 1 to n do Read (A [i] ) ; Readln;
Writeln (‘ Массив до сортировки:’ ) ;
for i:= 1 to n do Write(А[i] : 6 : 2, ‘ ‘);
if A[i] > A[i + 1] then
begin < . если A[i] > A[i+1] , то элементы меняются местами >
Writeln (‘ Массив после сортировки:’ ) ;
for i:= 1 to n do Write (A [i] : 6 : 2, ‘ ‘) ;
8.3 Массивы с большей размерностью
Возможна следующая организация массива: каждый элемент массива является другой массив. Описание массива в этом случае может выглядеть так:
. : array [. ] of array .
Подобная запись достаточно громоздка (несколько раз записывается служебное слово array и т. д. ), но синтаксис языка Паскаля позволяет описывать многомерные массивы проще.
М: array[1.. 3] of array [1.. 3] of Real;
Подобное описание эквивалентно следующему:
М: array [1.. 3, 1.. 3] of Real;
В первом случае доступ к элементу осуществляется так:
Т: array[1 .. 2, 1 .. 3, 1 .. 4] of Integer;
U: array[1 .. 10, ‘A’ .. ‘Z’] of char;
Работа с n-мерными массивами заставляет программиста организовать n вложенных циклов. Подробнее остановимся на двумерных массивах. Двумерные массивы используются, в основном, для определения матриц (таблиц) с индексами, изменяющимися по строкам и по столбцам (первый индекс – номер строки, второй — номер столбца).
А[1, 1] , А[1, 2] , . . . , A[l, M]
А[2, 1] , А[2, 2] , . . . , А[2, M]
Язык C++ с нуля | #32 Сортировка массива в c++
А[N, 1] , A[N,2] , . . . , А[N,M]
Здесь приведён пример двух мерного массива с N строками и M столбцами.
С элементами двумерных массивов можно работать, указывая два индекса (номер строки и номер столбца) через запятую в квадратных скобках.
M[k, i] := SQR(M[i, j] + M[j, i] ) ;
Ввод элементов двумерного массива по строкам с клавиатуры:
for i := 1 to n do
for j:= 1 to m do Read (M[i, j]);
или с сообщениями:
for i:= 1 to n do
for j:= l to m do
Write(‘введите М[‘, i, ‘, ‘ , j, ‘] ‘);
Вывод элементов двумерного массива в виде матрицы:
Часто при работе с двумерными массивами (матрицами) приходится оперировать с элементами, обладающими некоторыми признаками, в частности, связанными с положением элементов относительно диагоналей матрицы. Например, элемент находится на главной диагонали рисунок 8.1a, на побочной диагонали рисунок 8.1б, ниже главной диагонали, ниже побочной и т. д. (рисунки 8.1в÷ж).
Положение этих элементов может быть описано следующими математическими соотношениями для матрицы n∙n:
— выше главной и выше побочной диагонали –
Задача. Матрица n*n вводится с клавиатуры, заменить все отрицательные элементы выше главной диагонали их квадратами. Вывести новую матрицу на экран.
М: array[1.. n, 1.. n] of integer;
for i:= 1 to n do
for j:= 1 to n do
Write(‘введите М[ ‘ , i, ‘, ‘ , j , ‘] : ‘);
for i: = 1 to n do
for j:= 1 to n do
for i:= l to n do
for j:= 1 to n do Write( M[i, j]: 3 , ‘ ‘);
Источник: studfile.net
О сортировках (пузырьковой, быстрой, расческой. )
Эта статья ориентирована в первую очередь на начинающих программистов. О сортировках вообще и об упомянутых в заголовке в интернете море статей, зачем нужно еще одна? Например, есть хорошая статья здесь, на хабре: Пузырьковая сортировка и все-все-все.
Во-первых, хорошего много не бывает, во-вторых в этой статье я хочу ответь на вопросы «зачем, что, как, почему».Зачем нужны сортировки? В первую очередь, для поиска и представления данных. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. Пример: орфографический словарь, в нем слова отсортированы по алфавиту.
Если бы это было не так, то попробуйте найти в нем нужное слово. Телефонная книга, где абоненты отсортированы по алфавиту. Даже если сортировка не обязательна и не сильно нужна, все равно бывает удобнее работать с отсортированными данными.
Вот начальный (неотсортированный) массив:
| 50 | 32 | 40 | 31 | 20 | 30 | 10 |
а вот отсортированный:
| 10 | 20 | 32 | 30 | 31 | 40 | 50 |
Обратите внимание: порядок элементов 32,31,30 изменился, т.е. сортировка не устойчивая (не стабильная).
Все используемые в статье сортировки сравнивают пару элементов и меняют их, если они не в нужном порядке. Чем же они отличаются? Отличаются способом выбора пар сравниваемых элементов.
Дальше примеры процедур сортировки на языки Си. Везде первый параметр — адрес массива, второй- количество элементов в массиве. Внешний цикл в процедурах назовем проходом, а внутренний — просто циклом.
Простая сортировка
Проход перебирает все элементы массива и в цикле сравнивает текущий элемент со всеми последующими.
void sorto(int *m,int n) // обычная, простая, примитивная. сортировка < int tmp; for (int i=0;i> > >
Результат работы
| 10 | 20 | 32 | 31 | 30 | 40 | 50 |
Плюсы простой сортировки — они простая в реализации и устойчивая.
Минусы — она очень медленная, т.к. происходит очень много операций сравнения. Каждый из n элементов сравнивается со всеми последующими, поэтому количество сравнений ~n*n/2. Если n=100000, то сравнений 5 миллиардов. Правда, если n=1000, то сравнений «только» 500 тыс и современный компьютер может это сделать менее чем за секунду, так что при небольшом количествах это сортировка годится.Ели один важный минус — если данные почти отсортированы (из 100тыс элементов только 10 стоят не на своих местах), то все равно время работы изменится мало, т.к. операций сравнения будет столько же.Попробуем улучшить алгоритм и перейдем к
Пузырьковая сортировка
Она же «Bubble» она же «пузырёк.» Внутренний цикл снова и снова пробегает по массиву и сравнивает текущий элемент с предыдущим (поэтому пробег начинается с 1) и если текущий меньше, переставляет его с предыдущим. Место перестановки запоминается в переменной k, и в конце прохода в k находится индекс, начиная с которого массив отсортирован.
void sortb(int *m,int n) < int tmp,k; while(n>1) < // проход проверят, не пора ли заканчивать k=0; // нет перестановок for (int i=1; i> n=k; // с k все отсортировано > >
В самом худшем случае (когда исходный массив отсортирован в обратном порядке, получается те же n*n/2 сравнений. А в лучшем или в хорошем»? Лучший случай — это когда массив полностью отсоротирован. Тогда на первом проходе ничего переставляться не будет, в конце прохода n присвоится 0 (k=0) и второго прохода не будет. Вместо 100тыс проходов — всего 1! Замечательно, но что, если массив отсортирован, но не совсем. Например переставим в отсортированном массиве минимальный и максимальный элементы и будем сортировать этот «проблемный» массив (помним, что 30-32 имеют одинаковый ключ):
| 50 | 20 | 32 | 31 | 30 | 40 | 10 |
На первом шаге 1 прохода «20» сравнивается с «50» и происходит обмен. На следующем шаге «32» сравнивается снова с «50» (он ведь теперь занял место «20». В результате в конце первого прохода «50» займет место в конце, а все остальные сдвинутся на 1 позицию к началу массива. А что произойдет с «10», который был в конце? Он тоже передвинется на 1 позицию к началу. Если представить, что начальные позиции вверху, а конечные внизу, «на дне», то в результате прохода самый тяжелый окажется на дне, а самый легкий «всплывет» на одну позицию. В одной из статей тяжелые элементы называют «зайцам», а легкие — «черепахами». Во время прохода «заяц» быстро бежит в конец (или тонет), пока не встретит более весомого зайца (который примет эстафету и побежит дальше) или пока не займет свое место. А легкие элементы всплывают на одну позицию. Если самый легкий занимает n-ю позицию, то нужно n проходов, чтобы ему добраться до своего места. Самый тяжелый («дробинка») за один проход быстро тонет, а самый легкий («пузырек») -медленно всплывает. Тот пузырек, которому всплывать дольше всех и определяет общее число необходимых проходов. Если самый легкий в конце массива, надо столько проходов, сколько элементов в массиве.
Что же делать с «черепахами», чтобы они не мешали так сильно. На помощь приходит
Шейкерная сортировка
Почему в пузырьковой сортировке тяжелые элементы быстро тонут, а легкие — медленно всплывают? Потому что цикл сравнения продвигается от начала массива к концу и «тащит» с собой тяжелые элементы. А если двигаться от конца к началу, то легкие станут быстро всплывать, а тяжелые медленно тонуть. Самый легкий за один проход переместится из конца в начало.
Шейкерная сортировка на четных проходах двигается из начала в конец, а на нечетных наборот и наш проблемный массив отсортирует за 3 прохода. Для почти отсортированного массива шейкерная сортировка может оказаться намного быстрее «пузырька», но для случайно отсортированного исходного массива выигрыш обычно не сильно велик.
Сортировка расчёской
Или гребёнкой. Снова спросим почему пузырек медленно всплывает? Потому что за проход он перемещается на 1 позицию. А почему он перемещается только на 1 позицию? Потому, что сравниваются и переставляются соседние элементы.
Так давайте сравнивать не соседние элементы, а находящиеся на расстоянии s (постепенно уменьшая s с каждым проходом). Реализуя эту идею на практике, приходим к сортировке расческой.
void sortc(int *m,int n) < int tmp,k; int s=n; // готовим начальный шаг long long cnt=0; while(n>1) < s/=1.247f; // шаг на этом проходе. На первом проходе получается примерно 80% от размера массива, // и легкие элементы в хвосте переносятся в первые 20% if (s<1) s=1; // 0 быть не может, присвоим 1 k=0; // нет перестановок for (int i=0; i+sm[i+s]/10) < tmp=m[i]; m[i]=m[i+s]; m[i+s]=tmp; k=i; >++cnt; > if (s==1) // шаг 1, как в обычном пузырьке.
Включаем контроль n=k+1; > >
Идея вроде простая и алгоритм не сложный, но результат впечатляет. Сортировка расческой оказывается намного быстрее, чем пузырек/шейкер, она даже может обогнать «быструю» сортировку qsort. Но есть и минус — она не устойчивая (что интуитивно понятно).
Быстрая сортировка qsort
Функция быстрой сортировки нашего массива очень простая:
// компаратор для qsort int fcomp(const void *i, const void *j) < return (*(int *)i)/10 — (*(int *)j)/10; >void sortq(int *m,int n)
Простая оно потому, что использует стандартную быструю сортировку qsort. Посмотрим снова на приведенные алгоритмы. Во всех выбираются и сравниваются пары элементов m[i] и m[j]. Но что такое m[i]? Это i-й элемент в массиве целых чисел m или «элемент, расположенный по адресу Ai=m+i*».
Соответственно, j-й элемент расположен по адресу Aj=m+j*. Итак, мы сравниваем элементы по адресами Ai и Aj и переставляем их, если Aj. Этот передается третьим параметром. Хорошо, но как qsort сравнит элементы, ведь у нас хитрый способ сравнения? Она не сравнивает сама, она использует нашу функцию сравнения fcomp, адрес которой передается в 4 параметре.
Когда qsort по своему внутреннему алгоритму решит, что надо сравнить i и j-й элементы, она передаст их адреса в качестве 1 и 2 параметров функции fcomp, которая возвращает результат сравнения 0 в зависимости от того, меньше первый параметр второго, равен ему или больше. Если qsort видит, что i0 она просто переставит элементы в массиве (размер элемента она знает, а содержимое ей не важно).
Время сортировки 100001 элемента
Измерим время сортировки для массива, содержащего 100001 элемент на компьютере с процессором Intel i5 (3.3Ггц).Время указано в сек, через дробь указано количество проходов (для быстрой сортировки оно неизвестно).Как и ожидалось, шейкерная сортировка на проблемном массиве (который полностью упорядочен, только первый и последний элементы переставлены) абсолютный лидер. Она идеально «заточена» под эти данные. Но на случайных данных сортировки расческой и qsort не оставляют соперницам шанса. Пузырьковая сортировка на проблемном массиве показывает двукратное увеличение скорости по сравнению с случайным просто потому, что количество операций перестановки на порядки меньше.
| Стабильная | + | + | + | — | — |
| Случайный | 23.1/100000 | 29.1/99585 | 19.8/50074 | 0.020/49 | 0.055 |
| Проблемный | 11.5/100000 | 12.9/100000 | 0.002/3 | 0.015/48 | 0.035 |
| Обратный | 18.3/100000 | 21.1/100000 | 21.1/100001 | 0.026/48 | 0.037 |
А теперь вернемся к истокам, к пузырьковой сортировке и воочию посмотрим на процесс сортировки. Видите, как на первом проходе тяжелый элемент (50) переносится в конец?
Сравниваемые элементы показаны в зеленых рамках, а переставленные — в красных
Дополнение после публикации
Я ни коей мере не считаю qsort плохой или медленной — она достаточно быстра, функциональна и при возможности следует пользоваться именно ею. Да, ей приходится тратить время на вызов функции сравнения и она уступила «расческе», которая сравнивает «по месту». Это отставание несущественно (сравните с отставанием пузырька от qsort, которое будет увеличиваться при росте массива).
Пусть теперь надо сравнивать не числа, а какую-то сложную структуру по определенному полю и пусть эта структура состоит из 1000 байтов. Поместим 100тыс элементов в массив (100мб — это кое-что) и вызовем qsort. Функция fcomp (функция-компаратор) сравнит нужные поля и в результате получится отсортированный массив.
При этом при перестановке элементов qsort придется 3 раза копировать фрагменты по 1000 байтов. А теперь «маленькая хитрость» — создадим массив из 100тыс ссылок на исходные элементы и передадим в qsort начало этого массива ссылок. Поскольку ссылка занимает 4 байта (в 64 битных 8), а не 1000, то при обмене ссылок qsort надо поменять эти 4/8 байтов.
Разумеется, нужно будет изменить fcomp, поскольку в качестве параметров она теперь получит не адреса элементов, а адреса адресов элементов (но это несложное изменение). Зато теперь можно сделать несколько функций сортировки (каждая сортирует по своему полю структуры). И даже, при необходимости, можно сделать несколько массивов ссылок. Вот сколько возможностей дает qsort!
Кстати: использование ссылок на объекты вместо самих объектов может быть полезно не только при вызове qsort, но и при применении таких контейнеров как vector, set или map.
Количество сравнений и обменов
В следующей таблице показывается количество операций сравнения/количество обменов для каждой сортировки. Для qsort количество обменов неизвестно, поэтому показано только количество сравнений. Видно, что для случайного массива количество сравнений минимально у qsort.
| Случайный | 5’000’050’000/1’131’715’503 | 4’999’702’086/2’507’142’238 | 3’341’739’679/2’507’142’238 | 4’489’129/714’533 | 1’915’414 |
| Проблемный | 5’000’050’000/199’999 | 5’000’050’000/199’999 | 299’997/199’999 | 4’395’305/91’829 | 1’588’741 |
| Обратный | 5’000’050’000/5’000’050’000 | 5’000’050’000/5’000’050’000 | 5’000’050’000/5’000’050’000 | 4’395’305/233’210 | 1’588’741 |
Источник: habr.com
Программа которая сортирует массив по возрастанию
Если тема для вас новая, и вы еще не знакомы с алгоритмами сортировки, то наверняка при решении задачи «Отсортировать массив по возрастанию» первое что придет в голову, это перебор, то есть: найти минимальный элемент и поменять его местами с начальным, потом, в оставшейся части массива (кроме первого элемента), найти снова минимальный элемент и поменять его со вторым элементом и т.д. Такой алгоритм называется Сортировка выбором. Рассмотрим его подробнее.
public static void selectionSort(int[] arr) < /*По очереди будем просматривать все подмножества элементов массива (0 — последний, 1-последний, 2-последний. )*/ for (int i = 0; i < arr.length; i++) < /*Предполагаем, что первый элемент (в каждом подмножестве элементов) является минимальным */ int min = arr[i]; int min_i = i; /*В оставшейся части подмножества ищем элемент, который меньше предположенного минимума*/ for (int j = i+1; j < arr.length; j++) < //Если находим, запоминаем его индекс if (arr[j] < min) < min = arr[j]; min_i = j; >> /*Если нашелся элемент, меньший, чем на текущей позиции, меняем их местами*/ if (i != min_i) < int tmp = arr[i]; arr[i] = arr[min_i]; arr[min_i] = tmp; >> >
СОРТИРОВКА МЕТОДОМ ПУЗЫРЬКА (BUBBLE SORT).
Алгоритм проходит массив от начала и до конца, сравнивая попарно соседние элементы, Если элементы стоят в неправильном порядке, то они меняются местами, таким образом, после первого прохода на конце массива оказывается максимальный элемент (для сортировки по возрастанию). Затем проход массива повторяется, и на предпоследнем месте оказывается другой наибольший после максимального элемент и т.д. В итоге, наименьший элемент постепенно перемещается к началу массива («всплывает» до нужной позиции как пузырёк в воде).
Реализация алгоритма Сортировка пузырьком на Java (по возрастанию):
public static void bubbleSort(int[] arr) < /*Внешний цикл каждый раз сокращает фрагмент массива, так как внутренний цикл каждый раз ставит в конец фрагмента максимальный элемент*/ for(int i = arr.length-1 ; i >0 ; i—) < for(int j = 0 ; j < i ; j++)< /*Сравниваем элементы попарно, если они имеют неправильный порядок, то меняем местами if( arr[j] >arr[j+1] ) < int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; >> > >
ПРИМЕРЫ.
Рассмотрим примеры того, как можно воспользоваться выше приведенными алгоритмами.
Для начала создадим массив. Это можно сделать так:
int arr[] =;
Или мы можем создать массив случайных чисел:
int arr[] = new int[10]; for(int i = 0; i < arr.length; i++) < //элементу массива присваивается случайное число от 0 до 99 arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + » «); >
Затем воспользуемся вышеприведёнными алгоритмами сортировки:
System.out.print(«n»); bubbleSort(arr); for(int i = 0; i
System.out.print(«n»); selectionSort(arr); for(int i = 0; i
Важно понимать, что сортировки выбором и пузырьком являются простыми, но неэффективными для больших массивов. Эти алгоритмы являются скорее учебными и практически не применяются в жизни. Вместо них используются более эффективные алгоритмы. Подробнее о разных алгоритмах можно прочитать, например, на википедии.
В наше время нет необходимости самостоятельно реализовывать алгоритмы для сортировки, поскольку все что нам нужно, уже имеется в стандартных библиотеках Java.
СОРТИРОВКА МАССИВА ПРИ ПОМОЩИ МЕТОДА SORT() ИЗ КЛАССА ARRAYS.
Метод sort() из класса Arrays использует усовершенствованный алгоритм Быстрой сортировки (Quicksort), который эффективен в большинстве случаев. Для того чтобы отсортировать массив, необходимо написать всего одну строку.
Arrays.sort(arr);// где arr это имя массива
Примечание: в начале файла предварительно нужно подключить библиотеку java.util.
import java.util.*;
СОРТИРОВКА МАСССИВА ЦЕЛЫХ ЧИСЕЛ ПО ВОЗРАСТАНИЮ.
//Создаем массив случайных чисел int arr[] = new int[10]; for(int i = 0; i < arr.length; i++) < arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + » «); >System.out.print(«nSorted: n»); //Сортируем массив Arrays.sort(arr); //Выводим отсортированный массив на консоль. for(int i = 0; i
СОРТИРОВКА МАССИВА ЦЕЛЫХ ЧИСЕЛ ПО УБЫВАНИЮ.
//Создаем массив случайных чисел Integer arr[] = new Integer[10]; for(int i = 0; i < arr.length; i++) < arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + » «); >System.out.print(«nSorted: n»); //Сортируем массив Arrays.sort(arr, Collections.reverseOrder()); //Выводим отсортированный массив на консоль. for(int i = 0; i
Обратите внимание, что при сортировке массива в обратном порядке (по убыванию) нужно использовать тип Integer[] вместо примитивного типа int[].
СОРТИРОВКА МАССИВА СТРОК В JAVA.
String[] names = new String[] ; Arrays.sort(names); for(int i = 0; i
В этом примере массив имен сортируется в порядке от А до Я. Для того чтобы отсортировать массив в обратном порядке, необходимо в методе sort() указать Collections.reverseOrder().
Arrays.sort(names, Collections.reverseOrder());
К сожалению, по умолчанию метод sort() сортирует только примитивные типы данных и строки.
Источник: digital-apple.ru