Что такое сортировка вставками в C?
Метод сортировки, называемый сортировкой вставками, сопоставляет каждый отдельный элемент с соседними при переборе массива. Меньший элемент, чем тот, который был до того, как он был вставлен в отсортированный подмассив в соответствующем месте.
Чтобы еще больше проиллюстрировать это, я продемонстрировал пример, в котором я рассматривал массив из четырех элементов в таком массиве, как обр[]= {5, 4, 60, 9} и мы хотим отсортировать этот элемент в порядке возрастания с помощью сортировки вставками. Следующие взаимодействия объясняют полный пробный запуск сортировки вставками:
Итерация 1
| 5 | 4 | 60 | 9 |
У нас есть массив как arr[5, 4, 60, 9] теперь, в первой итерации сортировки вставками мы сначала сравниваем первые два элемента, такие как 5 и 4, поскольку arr[5] > arr[4], поэтому мы меняем их местами, чтобы отсортировать массив в порядке возрастания. Теперь массив будет:
| 4 | 5 | 60 | 9 |
Итерация 2
| 4 | 5 | 60 | 9 |
Во второй итерации мы сравниваем следующие два элемента, например, arr[5] с arr[60].
Так как arr[5] < arr[60] свопинг не происходит, так как он уже отсортирован в порядке возрастания. Теперь массив становится:
| 4 | 5 | 60 | 9 |
Итерация 3
| 4 | 5 | 60 | 9 |
Как и в третьей итерации, мы сопоставляем третий и четвертый элементы, такие как arr[60], с arr[9].
Теперь мы видим, что arr[60] > arr[9] поэтому происходит подкачка, тогда массив будет отсортирован в порядке возрастания.
| 4 | 5 | 9 | 60 |
Вот как работает сортировка вставками в C, которая легко сортирует элемент массива в порядке возрастания или убывания.
Блок-схема сортировки вставками
Ниже приведена блок-схема алгоритма сортировки вставками:
Реализация примера сортировки вставками на C
Сначала нам потребуется набор элементов, которые необходимо отсортировать в порядке убывания и возрастания, чтобы построить метод сортировки вставками в C. Предположим для целей этого примера, что мы имеем дело с массивом чисел. {5, 4, 60, 9} :
#includeпустота вставки sort_ascending ( инт обр1 [ ] , инт н ) {
инт я , Дж , мой ключ ;
// цикл for используется для перебора значений i от 1 до i
для ( я '=' 1 ; я < н ; я ++ ) {
мой ключ '=' обр1 [ я ] ;
Дж '=' я - 1 ;
пока ( Дж >= 0 && обр1 [ Дж ] > мой ключ ) {
обр1 [ Дж + 1 ] '=' обр1 [ Дж ] ;
Дж '=' Дж - 1 ;
}
обр1 [ Дж + 1 ] '=' мой ключ ;
}
}
пустота вставки sort_descending ( инт обр2 [ ] , инт м ) {
инт я , Дж , мой ключ ;
// создается еще один цикл for для перебора значений i от 1 до i
для ( я '=' 1 ; я < м ; я ++ ) {
мой ключ '=' обр2 [ я ] ;
Дж '=' я - 1 ;
пока ( Дж >= 0 && обр2 [ Дж ] < мой ключ ) {
обр2 [ Дж + 1 ] '=' обр2 [ Дж ] ;
Дж '=' Дж - 1 ;
}
обр2 [ Дж + 1 ] '=' мой ключ ;
}
}
инт основной ( ) {
// Сортировка вставками по убыванию
инт my_arr [ ] '=' { 5 , 4 , 60 , 9 } ; //инициализируем my_arr[] с четырьмя значениями
инт м '=' размер ( my_arr ) / размер ( my_arr [ 0 ] ) ;
вставки sort_descending ( my_arr , м ) ;
printf ( 'Отсортированный массив в порядке убывания: ' ) ;
для ( инт я '=' 0 ; я < м ; я ++ )
printf ( '%д' , my_arr [ я ] ) ;
printf ( ' \n ' ) ;
// Сортировка вставками по возрастанию
инт н '=' размер ( my_arr ) / размер ( my_arr [ 0 ] ) ;
вставки sort_ascending ( обр2 , н ) ;
printf ( 'Отсортированный массив в порядке возрастания: ' ) ;
для ( инт я '=' 0 ; я < н ; я ++ )
printf ( '%д' , my_arr [ я ] ) ;
printf ( ' \n ' ) ;
возвращаться 0 ;
}
В этом коде два метода вставки sort_descending () , и вставки sort_ascending () взять значения массива my_arr[] . Затем код использует для петли для перебора элементов массива.
Мы вызываем обе функции в основной функции после того, как они отсортировали массивы в порядке убывания и возрастания. После этого циклы for используются для печати отсортированного массива.
Когда мы запускаем эту программу, ожидаемый результат помещается ниже:
Заключение
Сортировка вставками — это быстрый и простой способ сортировки массива по убыванию или возрастанию. Для небольших наборов данных этот метод сортировки работает хорошо. Как вы можете видеть в приведенном выше руководстве, просто реализовать пример программы на C, чтобы легко понять сортировку вставками как в порядке убывания, так и в порядке возрастания.