Сортировки

[Sna1L]

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

Итак начнем.

Метод пузырька

Паскаль:

// ar - сам массив
// LEN - кол-во эл-тов
for i:=2 to LEN do 
    for j:=1 to LEN-1 do
        if ar[j] < ar[j+1] then
            begin
            temp := ar[j];
            ar[j] := ar[j+1];
            ar[j+1] := temp;
            end;

Си:

// ar - сам массив
// LEN - кол-во эл-тов
for(i = 1; i < LEN; i++)
    for(j = 0; j < LEN - 1; j++)
        if(ar[j] < ar[j+1] ){
            temp = ar[j];
            ar[j] = ar[j+1];
            ar[j+1] = temp;
        }

Самая простая реализация. Алгоритм достаточно медленный. Можно улучшить:
1. Принцип "пузырька" - после каждого прохода цикла, самый "тяжелый" эл-т становится в конец списка => нет смысла проверять последние эл-ты.

2. Допустим, у нас есть массив чисел: (1,2,4,3). Чтобы его упорядочить, достаточно одного прохода, но по этому алгоритму будет 4 обхода. => нужно проверять, упорядочен ли массив, дабы избежать лишних проверок. Решается введением доп. переменной. В большинстве случаев, это ускорит работу, хотя в худшем случае замедлит, т.к. обходы будут все, но с проверками на упорядоченность. Но худших случаев не так уж много, выбирайте.

3. Допустим, есть массив чисел: ( 2,3,4,1 ). По нашему алгоритму будет 3 обхода с такими результатами:
1) (2,3,1,4)
2) (2,1,3,4)
3) (1,2,3,4)
Вам не кажется, что если бы двигались справа-налево, то достаточно было бы одного обхода ? Вывод: делаем обход в две стороны. Опять же, в некоторых случаях это замелит работу.

Давайте реализуем все это на практике.
Нам потребуется: еще один внутренний цикл(обход в другую сторону), булевская переменная(для проверки упорядоченности), еще 2 переменные для правой и левой границы(после каждого обхода, граница смещается)

Си:

char bool = 0; // упорядоченность 
int left = 0,right = LEN-1;

while( right - left > 1 && bool == 0) {
    bool = 1;
    for( i = left; i < right; i++) 
        if( ar[i] > ar[i+1] ) {
             bool = 0;
             temp = ar[i];
             ar[i] = ar[i+1];
             ar[i+1] = temp;
         }
     if( bool )
         break;
     bool = 1;
     right--; // сдвигаем правую границу, там уже самый толстый эл-т
     for( i = right; i > left; i--)
          if( ar[i] < ar[i-1]) {
                bool = 0;
                temp = ar[i];
                ar[i] = ar[i-1];
                ar[i-1] = temp;
          }
       left++; // левая граница
     }
}

Паскаль:

bool := false; // упорядоченность 
left := 1;
right := LEN;

while (right - left) > 1 AND not bool )  do
    begin
    bool = true;
    for i := left to right-1 do 
        if ar[i] > ar[i+1]    then
             begin
             bool := false;
             temp := ar[i];
             ar[i] := ar[i+1];
             ar[i+1] := temp;
             end;
     if bool  then
         break;
     bool := true;
     dec(right); // сдвигаем правую границу, там уже самый толстый эл-т
     for i := right; downto left+1 do
          if ar[i] < ar[i-1] then
                begin
                bool := false;
                temp := ar[i];
                ar[i] := ar[i-1];
                ar[i-1] := temp;
                end;
       inc(left); // левая граница
     }
}

Реализованная сортировка называется шейкер-сортировка

[Sna1L]

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

Паскаль:

right := LEN;
for i:=1 to LEN-1 do
    begin
    max := ar[1];
    ind := 1;
    for j := 2 to right-1 do
          if max < ar[j] then
               begin
               max := ar[j];
               ind := j;
               end;
     if max > ar[right] then
               begin
               ar[ind] := ar[right];
               ar[right] := max;
               end;
     end;

Си:

right = LEN-1;
for( i = 1; i < LEN; i++) {
    max = ar[1];
    ind = 0;
    for(j = 1; j < right; j++)
          if(max < ar[j] ) {
               max = ar[j];
               ind = j;
          }
     if(max > ar[right]) {
               ar[ind] := ar[right];
               ar[right] := max;
     }
}

Плюсы этой сортировки в том, что она занимает мало времени на реализацию и при этом быстрее чем пузырек, реализуемый примерно за то же время.
Возможно, ее еще можно оптимизировать. Мне лень

[Sna1L]

Сортировка методом подсчета

Это очень быстрая сортировка, требующая дополнительной памяти. Реализовать ее можно, только зная диапазон чисел, входящих в массив(если он неизвестен, то можно пройтись по массиву в поиске максимальных).
Суть такова:
Создается дополнительный массив с индексами от наименьшего эл-та сортируемого массива до наибольшего. В каждый эл-т массива ar2[n] заносится кол-во эл-тов равных n. А потом в массив по порядку заносятся эл-ты. Немного непонятно? Понимаю, посмотрите лучше на код:
Оговорка: для краткости, подразумеваю, что в массиве содержатся числа от 0 до 10

Си:

int ar2[11];
/*
    заполнение массива нулями
*/
for(i = 0; i < LEN; i++) //подсчет
     ar2[ ar[i] ] += 1; 

j = 0;

for(i = 0; i < 11; i++) 
     while( ar2[i] > 0) {
           ar[j] = i;
           j++;
           ar2[i]--;
     }

Паскаль:

for i := 0 to LEN-1 //подсчет
     inc( ar2[ ar[i] ] ); 

j := 0;

for i := 0  to 10 do
     while ar2[i] > 0  do
           begin
           ar[j] := i;
           inc(j);
           dec(ar2[i]);
           end;

Быстрая и легкореализуемая сортировка, но применить ее можно далеко не везде. Смотрите по ситуации

[Sna1L]

На этом все. Есть еще код сортировки вставками, но она какая-то слишком уж убогая.
Потом, может быть, напишу быструю сортировку и сортировку Шелла. Или выкладывайте свои варианты.

ЗЫ прошу прощения за возможные ошибки, часть кода писал "от руки" прямо тут
ЗЫЫ думаю, тема будет полезна некоторым студентам, так что предлагаю модераторам прикрепить ее кверху

[whatever]

Лови + за старания. А вообще, отправь ЛС модератору, пусть сюда добавят, а то твоя темя затеряется быстро.