Сортировка методом пузырька

Задача

Отсортировать массив, заполненный случайными числами, по возрастанию. Для сортировки использовать метод "пузырька". Вывести на экран массив в исходном и отсортированном виде.

Пояснение к задаче и алгоритм решения

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

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

Исходный код на языке программирования Pascal

const
    N = 10;
var
    arr: array[1..N] of integer;
    i, j, k: integer;
 
begin
    randomize;
    for i:=1 to N do begin
        arr[i] := random(256);
        write (arr[i]:4);
    end;
    writeln;
    for i:=1 to N-1 do
        for j:=1 to N-i do
            if arr[j] > arr[j+1] then begin
                k := arr[j];
                arr[j] := arr[j+1];
                arr[j+1] := k
            end;
 
    for i:=1 to N do
        write (arr[i]:4);    
    writeln;
end.

Пример(ы) выполнения программы на языке Pascal

  97   8 156  88   3  99 217 170 135 133
   3   8  88  97  99 133 135 156 170 217

Исходный код на языке программирования C

#include <stdio.h>
#define N 10
 
main() {
    int a[N], i, j, b;
    srand(time(NULL));
    for (i=0; i<N; i++) {
        a[i] = rand()%100;
        printf("%3d", a[i]);
    }
    printf("\n");
 
    for (i=0; i < N-1; i++) {
        for (j=0; j < N-i-1; j++) {
            if (a[j] > a[j+1]) {
                b = a[j];
                a[j] = a[j+1];
                a[j+1] = b;
            }
        }
    }
 
    for (i=0; i<N; i++)
        printf("%3d", a[i]);
    printf("\n");
}

Пример(ы) выполнения программы на языке C

 71 62 25  3 46 61 25 31 56 12
  3 12 25 25 31 46 56 61 62 71

Исходный код на языке программирования Python

from random import random
a = [0]*10
for i in range(10):
    a[i] = int(random()*100)
print(a)
 
for i in range(9):
    for j in range(9-i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
print(a)

Пример(ы) выполнения программы на языке Python

[42, 9, 95, 78, 59, 14, 50, 79, 54, 84]
[9, 14, 42, 50, 54, 59, 78, 79, 84, 95]

Особенности решения на языке программирования Python

В Питоне при обмене значений переменных можно обойтись без буферной переменной. Это делается с помощью присваивания в одном выражении. Такая возможность существует, т.к. в Python перед присваиванием в подобных выражениях сначала формируются кортежи.

Исходный код на языке программирования КуМир

алг сортировка пузырьком
нач
  цел N = 10
  цел таб arr[1:N]
  цел i,j,k
  нц для i от 1 до N
    arr[i] := int(rand(0,100))
    вывод arr[i],  " "
  кц
  вывод нс
  нц для i от 1 до N-1
    нц для j от 1 до N-i
      если arr[j] > arr[j+1] то
        k := arr[j]
        arr[j] := arr[j+1]
        arr[j+1] := k
      все
    кц
  кц
 
  нц для i от 1 до N
    вывод arr[i],  " "
  кц
кон

Пример(ы) выполнения программы на языке КуМир

41 38 95 61 71 1 20 14 83 61
1 14 20 38 41 61 61 71 83 95

Исходный код на языке программирования Basic

dim a(10)
for i =0 to 9
        a[i] = int(rand()*100)
        print a[i] + " ";
next i
print
 
for i=0 to 8
        for j=0 to 8-i
                if a[j] > a[j+1] then
                        b = a[j]
                        a[j] = a[j+1]
                        a[j+1] = b
                endif
        next j
next i
 
for i =0 to 9
        print a[i] + " ";
next i

Пример(ы) выполнения программы на языке Basic

6 61 17 0 51 36 43 32 88 6
0 6 6 17 32 36 43 51 61 88

Тема

Массивы

Уровень сложности

Сложный

Дата публикации