Предположим, что у нас массив разбит на 2 части : отсортированную и не отсортированную.
Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место, а затем заново сортировать весь список.
Этот процесс повторяется до тех пор, пока весь массив не станет отсортированным. В процессе работы меняются местами только соседние элементы.
В худшем случае сложность алгоритма : O(n^2), время работы алгоритма будет меньше, если большая часть массива уже отсортирована. Плюс в том, что требуется O(1) дополнительной памяти.
Реализация:
Основная идея сортировки вставками состоит в том, что при добавлении нового элемента в уже отсортированный список его стоит сразу вставлять в нужное место, а затем заново сортировать весь список.
Этот процесс повторяется до тех пор, пока весь массив не станет отсортированным. В процессе работы меняются местами только соседние элементы.
В худшем случае сложность алгоритма : O(n^2), время работы алгоритма будет меньше, если большая часть массива уже отсортирована. Плюс в том, что требуется O(1) дополнительной памяти.
Реализация:
template < typename Type>
void Insertion_Sort(Type mas[],unsigned long size){
Type temp;
unsigned long index;
unsigned long prevIndex;
for (index=0; index=0 && mas[prevIndex]>temp;prevIndex--)
mas[prevIndex+1]=mas[prevIndex]; //пока у нас пред. индекс >=0 и если пред элемент>a[index]
mas[prevIndex+1]=temp; //заменим элемент
}
}
0 коммент.:
Отправить комментарий