Раздел «Образование».FIVTLecturesTerm1Lecture3:
<<Лекции ФИВТ, 1-й семестр

Лекция 3. Задача сортировки.

Задача сортировки

Упорядочивание с помощью многократного поиска максимума.

Сортировка методом "пузырька". Оценка времени работы алгоритма.

Обсуждение идей определения понятия сложности задачи.

Упоминание об алгоритмах сортировки, которые работают и в среднем и в худшем случае O(n log n):

Комментарии в коде

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

Нужно комментировать:

Также комментировать нужно призраки и подпорки:

Язык Си: массивы.

Статические массивы. Реализация сортировки методом пузырька

#include <stdio.h>

int main() {
  int a[1000000], i, j, n;

  scanf("%d", &n);

  for (i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }

  int g = 0; // общее количество операций swap
  // sort
  for (i = 0; i < n - 1; i++) {
    int k = 0; // количество операций swap на текущем пробеге
    for (j = 0; j < n - 1 - i; j++) {
      if ( a[j] > a[j+1] ) {
        //  операция swap - обмена местами значений в a[j] и a[j+1]
        int t = a[j];
        a[j] = a[j+1];
        a[j+1] = t;
        k++;
        g++;
      }
    }
    if ( k == 0 ) {
      break;
    }
  }

  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");

  printf("Swaps count = %d\n", g);

  return 0;
}

Задание на семинар