Сортировка одномерных массивов по убыванию и возрастанию в Pascal.

pascalquestВ чем заключается вопрос: Как организовать сортировку массивов по убыванию и возрастанию в Паскаль. Метод пузырька.

Сложность : средняя .

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

Естественно есть готовый код, который мы сейчас и разберем:

    for i:=1 to n-1 do
        for j:=1 to n-i do
                if (mass[j] > mass[j+1]) then
                     begin
                        buf := mass[j];
                        mass[j] := mass[j+1];
                        mass[j+1] := buf;
                    end;

Массив mass, n кол-во элементов массива, i и j для циклов, buf для того чтобы поменять числа местами. Как я и сказал суть в том чтобы поменять местами соседние элементы пока не от сортируется. Давайте пока забудем про приведенный выше код и напишем следующее:

for j:=1 to n-1 do
    if (mass[j] > mass[j+1]) then
        begin
             buf := mass[j];
             mass[j] := mass[j+1];
             mass[j+1] := buf;
        end;

Мы меняем соседние элементы местами, СОСЕДНИЕ!!!!!!, цикл до n-1, потому что у последнего элемента массива соседнего элемента нету.

Что же делает этот цикл, он само собой поменяет местами соседние элементы при выполнении условия, что левый больше правого, т.е. например ( 3 , 2 ), 3 больше 2 значит поменяем местами.

После прохода этого цикла ХОТЬ КАК найдется наибольший элемент, т.е. он встанет в самый конец.

Сначала у нас j = 1, j + 1 = 2, т.е. сначала сравняться числа 5 и 2, они поменяются местами, потом j=2, j+1=3,
т.е. j = 2, там у нас уже 5, а в j = 3, у нас 3, условие выполняется значит опять местами.

И так пока цикл не кончиться, в итоге получиться что у нас в самом конце будет самый наибольший элемент. ВСЁЁЁЁЁ, у нас есть последний элемент.

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

    for i:=1 to n do
        for j:=1 to n-1 do
             if (mass[j] > mass[j+1]) then
                    begin
                        buf := mass[j];
                        mass[j] := mass[j+1];
                        mass[j+1] := buf;
                    end;

Всё работает правильно, можете проверить но все работает абсолютно ПРАВИЛЬНО. Теперь давайте сравним наш код с образцом:

    for i:=1 to n-1 do
        for j:=1 to n-i do
                if (mass[j] > mass[j+1]) then
                    begin
                        buf := mass[j];
                        mass[j] := mass[j+1];
                        mass[j+1] := buf;
                    end;

Есть два отличия:

1. n-1
2. n-i

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

По поводу 2-го, это значит что количество проверяемых чисел станет меньше, что это значит. Вот когда у нас идет первый цикл, у нас проверяются все числа и мы находим самый последний элемент, он у нас хоть как самый большой и больше смысла проверять его просто нет. Когда пойдет уже второй цикл у нас это число просто не будет затрагиваться вот и всё, а какой смысл его затрагивать ведь оно и так самое больше? И так после каждого прохода цикла )))

Пффффф… надеюсь вы поняли, да и еще это была сортировка по возрастанию чтобы сделать сортировку по убыванию достаточно просто понять знак в условии:

    for i:=1 to n-1 do
        for j:=1 to n-i do
                if (mass[j] < mass[j+1]) then
                     begin
                        buf := mass[j];
                        mass[j] := mass[j+1];
                        mass[j+1] := buf;
                    end;

Готовый код задачи на сортировку массива по возрастанию:

type
    massiv = array [1..10] of integer;

var
    mass : massiv;
    i , j , n , buf: integer;
begin
    randomize;
    write('Введите длину массива : ');readln(n);
    
    for i:=1 to n do
        begin
            mass[i] := random(10);
            write(mass[i], ' | ');
        end;
        
    for i:=1 to n-1 do
        for j:=1 to n-i do
            begin
                if (mass[j] > mass[j+1]) then
                    begin
                        buf := mass[j];
                        mass[j] := mass[j+1];
                        mass[j+1] := buf;
                    end;
            end;
     writeln;  
     
     for i:=1 to n do
        write(mass[i], ' | ');
     
     readln;
end.

2 комментария

  1. Огромное спасибо! Очень полезная статья. Использовал ваш код для сортировки массива по частям: левая часть сортируется по возрастанию, середина остается неизменной, а правая — по убыванию.
    P. S. А что у вас с футером?)

Написать ответ

Ваш e-mail не будет опубликован. Обязательные поля помечены *