Под сортировкой массива понимают упорядочивание его элементов по некоторому признаку.

Порядок сортировки бывает по возрастанию, по убыванию, по не возрастанию (не строгое убывание) или по не убыванию (не строгое возрастание).

Для сортировки массивов разработано достаточное количество алгоритмов, которые отличатся друг от друга по скорости сортировки, по объему используемой при этом памяти. Эффективность алгоритма также зависит от первоначального состояния массива.

Для начала мы рассмотрим достаточно простой и в меру эффективный алгоритм попарной сортировки, известный еще как пузырьковая сортировка.

Суть алгоритма пузырьковой сортировки заключается в попарном сравнении двух рядом стоящих элементов. Если эти элементы находятся по отношении друг к другу не в правильном порядке, то они переставляются местами. После чего проверка выполняется со следующей парой элементов. Сделав проход по всему массиву, и попарно переставив элементы, выполняется новый проход по массиву... и так до тех пор, пока все элементы не будут стоять на своих местах.

Исходя из этого сформулируем алгоритм: будем считать количество перестановок элементов при каждом полном проходе по массиву (переменная count), и если при очередном проходе не было сделано ни одной перестановки, то массив отсортирован и цикл можно завершить:

 repeat
  count := 0;
  for i := 2 to n do
   if a[i] < a[i - 1]
    then begin
          <Обмен значениями a[i] и a[i-1] элементов>
          inc(count)
         end
 until count = 0

Напомним, что при обмене значениями двух элементов массива используется временная переменная:

 temp := a[i];
 a[i] := a[i - 1];
 a[i - i] := temp;

После первого прохода по массиву самый большой элемент перемещается на "свое" место. После второго прохода, следующий по значению элемент, также становится на свое место. Поэтому, после очередного прохода по массиву, верхнюю границу индекса элемента можно уменьшать на единицу:

 m := n;
 repeat
  count := 0;
  for i := 2 to m do
   if a[i] < a[i - 1]
    then begin
          <Обмен значениями a[i] и a[i-1] элементов>
          inc(count)
         end;
  dec(m);
 until count = 0

Здесь мы ввели в алгоритм новую переменную m, первоначально присвоив ей значение переменной n (количество элементов массива). По завершению очередного прохода по массиву мы уменьшаем значение переменной m. Это несколько ускорит сортировку массива, так как количество попарных сравнений элементов с каждым проходом будет уменьшаться.

Рассмотрим еще один алгоритм сортировки - сортировка вставкой. Идея его заключается в следующем: начиная со второго элемента массива, по очереди будем "продвигать" текущий элемент к началу массива, пока этот элемент не окажется первым в массиве или его значение будет меньше значения впереди стоящего элемента.

Pascal Реализация:

for i := 2 to n begin
  k := i;
  // "Продвигаем" k-й элемент к началу массива
  while (k > 1) and (a[k] < a[k - 1]) begin
    // Меняем местами текущий элемент с впереди стоящим "соседом"
    temp := a[k];
    a[k] := a[k - 1];
    a[k - 1] := temp;
    k := k - 1;
   end;
end;

C/C++ реализация:

for (int i = 1; i < n; ++i) {
  int k = i;
  // "Продвигаем" k-й элемент к началу массива
  while (k > 0 && a[k] < a[k - 1]) {
    // Меняем местами текущий элемент с впереди стоящим "соседом"
    int temp = a[k];
    a[k] = a[k - 1];
    a[k - 1] = temp;
    --k;
  }
}

Выше описанные алгоритмы сортировки обладают одним существенным недостатком: относительно низкой скоростью сортировки больших массивов.

Существенно уменьшить время сортировки можно применив алгоритм так называемой быстрой сортировки. Идея быстрой сортировки заключается в следующем: для выбранной части массива находим значение среднего элемента (опорный элемент). Ищем первый элемент в поиске слева на право, который больше или равен опорному и меняем его местами с первым элементом, в поиске с право налево, который меньше или равен опорному. Такой обмен продолжается до тех пор, пока левый индекс не превысит правый индекс элементов найденной пары. После чего для каждой из двух частей (от левой границы до правого индекса, и от левого индекса до правой границы) повторяем вышеописанные действия.

Рекурсивная реализация на C/C++

 void qsort(int* a, int left, int right) {
  int l = left, r = right;
  int m = a[(left + right) / 2]; // Значение опорного элемента
  do {
   while (a[l] < a[m])
    l++;
   while (a[r] > a[m])
    r--;
   if (l <= r) {
    int temp = a[l];
    a[l] = a[r];
    a[r] = temp;
    l++;
    r--;
   }
  } while (l < r);
  if (left < r)
   qsort(a, left, r);
  if (l < right)
   qsort(a, l, right);
 }

Предлагаемый алгоритм быстрой сортировки относится к так называемым неустойчивым типам сортировки, при котором элементы с одинаковыми значениями могут изменить свое положение в массиве относительно друг друга.

Еще один вариант рекурсивной реализации алгоритма быстрой сортировки:

void swap(int &a, int &b) {
  int tmp = a;
  a = b;
  b = tmp;
}

void qsort(int* a, int left, int right) {
  int l = left, r = right, m = a[(left + right) / 2];
  while (l < r) {
    while (a[l] < m)
      l++;
    while (a[r] > m)
      r--;
    if (l <= r)
      swap(a[l++], a[r--]);
  }
  if (left < r)
    qsort(a, left, r);
  if (l < right)
    qsort(a, l, right);
}

Если постараться, быструю сортировку можно написать без рекурсии. Для этого можно использовать структуру данных стек, который реализует принцип LIFO, что соответствует принципу выполнения функции при рекурсии. В стек мы будем складывать пары (l, r). Также при выборе опорного элемента лучше писать int piv = a[l + (r - l) / 2]. Так можно уменьшить вероятность переполнения переменной.