Сортировка вставками (реализация на C++)

C++   22 февраля 2012  Автор статьи:  

Приведем пример реализации алгоритма простой сортировки — вставками. Данный алгоритм является устойчивым и онлайновым. Эффективен при достаточно малых размерах массива.

#include
using namespace std;

int main()
{
// Считываем размер массива,
// который необходимо отсортировать
int size;
cin >> size;

// Динамически выделяем память под
// хранение массива размера size
int *a = new int[size];

// Считываем массив
for (int i = 0; i < size; i++) { cin >> a[i];
}

for (int i = 0; i < size; i++) { int temp = a[i];// запомним i-ый элемент int j =i-1;//будем идти начиная с i-1 элемента while(j >= 0 && a[j] > temp)
// пока не достигли начала массива
// или не нашли элемент больше i-1-го
// который храниться в переменной temp
{
a[j + 1] = a[j];
//проталкиваем элемент вверх
j--;
}
a[j + 1] = temp;
// возвращаем i-1 элемент
}
// Выводим отсортированный массив
for (int i = 0; i < size; i++) { cout << a[i] << ' '; } return 0; }

  • Netally

    Не поняла! Если i начинается с 0, то как сочетается j = i — 1 и while j >= 0

    • А в чем проблема? Просто на первом шаге цикл не исполнится ни разу и это хорошо=)

  • Scarpion

    можна и так
    for(int i=1,j;i=0&&a[j]>t;j—)
    a[j+1]=a[j];
    a[j+1]=t;
    }

Научиться программировать

  • на Delphi

  • на Java

  • на C++