В чем заключается вопрос: Как организовать сортировку массивов по убыванию и возрастанию в Паскаль. Метод пузырька.
Сложность : средняя .
Довольно таки частый вопрос у начинающих программистов. Попробуем разобраться. Суть метода в том чтобы менять местами СОСЕДНИЕ числа пока наибольшее не окажется справа, но это для сортировки по возрастанию, пример:
Естественно есть готовый код, который мы сейчас и разберем:
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.