В чем заключается вопрос: Как организовать сортировку массивов по убыванию и возрастанию в Паскаль. Метод пузырька.
Сложность: средняя.
Довольно таки частый вопрос у начинающих программистов. Попробуем разобраться. Суть метода в том чтобы менять местами СОСЕДНИЕ числа пока наибольшее не окажется справа, но это для сортировки по возрастанию, пример:
Естественно есть готовый код, который мы сейчас и разберем:
| for i:= 1 to n- 1 do for if begin buf := mass[j]; mass[j] := mass[j+ mass[j+ end |
Массив mass, n кол-во элементов массива, i и j для циклов, buf для того чтобы поменять числа местами. Как я и сказал суть в том чтобы поменять местами соседние элементы пока не от сортируется. Давайте пока забудем про приведенный выше код и напишем следующее:
| for j:= 1 to n- 1 do if begin buf := mass[j]; mass[j] := mass[j+ mass[j+ 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 if begin buf := mass[j]; mass[j] := mass[j+ mass[j+ end |
Всё работает правильно, можете проверить но все работает абсолютно ПРАВИЛЬНО. Теперь давайте сравним наш код с образцом:
| for i:= 1 to n- 1 do for if begin buf := mass[j]; mass[j] := mass[j+ mass[j+ end |
Есть два отличия:
- n-1
- n-i
По поводу 1-го, не заморачивайте голову, можете оставить и просто n, но как видно что нам хватит на один проход меньше чтобы отсортировать массив, вот и всё.
По поводу 2-го, это значит что количество проверяемых чисел станет меньше, что это значит. Вот когда у нас идет первый цикл, у нас проверяются все числа и мы находим самый последний элемент, он у нас хоть как самый большой и больше смысла проверять его просто нет. Когда пойдет уже второй цикл у нас это число просто не будет затрагиваться вот и всё, а какой смысл его затрагивать ведь оно и так самое больше? И так после каждого прохода цикла )))
Пффффф… надеюсь вы поняли, да и еще это была сортировка по возрастанию чтобы сделать сортировку по убыванию достаточно просто понять знак в условии:
| for i:= 1 to n- 1 do for if begin buf := mass[j]; mass[j] := mass[j+ mass[j+ end |
Готовый код задачи на сортировку массива по возрастанию:
| type
massiv = mass : massiv; i , j , n , buf: randomize; write for begin mass[i] := random( write end for for begin if begin buf := mass[j]; mass[j] := mass[j+ mass[j+ end end writeln for write readln; |
