Рубрики

Сортировка вставки

Сортировка вставок — это простой алгоритм сортировки, который работает так, как мы сортируем игральные карты в наших руках.

Алгоритм
// Сортировка arr [] размера n
inserttionSort (обр, n)
Цикл от i = 1 до n-1.
…… а) Выберите элемент arr [i] и вставьте его в отсортированную последовательность arr [0… i-1]

Пример:

Другой пример:
12 , 11, 13, 5, 6

Давайте зациклим для i = 1 (второй элемент массива) до 4 (последний элемент массива)

i = 1. Поскольку 11 меньше 12, переместите 12 и вставьте 11 перед 12
11, 12 , 13, 5, 6

i = 2. 13 останется на своем месте, так как все элементы в A [0..I-1] меньше 13
11, 12, 13 , 5, 6

i = 3,5 переместится в начало, а все остальные элементы с 11 по 13 переместятся на одну позицию впереди своей текущей позиции.
5, 11, 12, 13 , 6

i = 4. 6 переместится в позицию после 5, а элементы с 11 по 13 переместятся на одну позицию впереди своей текущей позиции.
5, 6, 11, 12, 13

C ++

// C ++ программа для сортировки вставками
#include <bits/stdc++.h>

using namespace std;

  
/ * Функция для сортировки массива с использованием вставки sort * /

void insertionSort(int arr[], int n) 

    int i, key, j; 

    for (i = 1; i < n; i++)

    

        key = arr[i]; 

        j = i - 1; 

  

        / * Переместить элементы arr [0..i-1], которые

        больше, чем ключ, на одну позицию впереди

        их текущей позиции * /

        while (j >= 0 && arr[j] > key)

        

            arr[j + 1] = arr[j]; 

            j = j - 1; 

        

        arr[j + 1] = key; 

    

  
// Вспомогательная функция для печати массива размера n

void printArray(int arr[], int n) 

    int i; 

    for (i = 0; i < n; i++) 

        cout << arr[i] << " "

    cout << endl;

  
/ * Код водителя * /

int main() 

    int arr[] = { 12, 11, 13, 5, 6 }; 

    int n = sizeof(arr) / sizeof(arr[0]); 

  

    insertionSort(arr, n); 

    printArray(arr, n); 

  

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для вставки сортировки
#include <math.h>
#include <stdio.h>

  
/ * Функция для сортировки массива с использованием вставки sort * /

void insertionSort(int arr[], int n)

{

    int i, key, j;

    for (i = 1; i < n; i++) {

        key = arr[i];

        j = i - 1;

  

        / * Переместить элементы arr [0..i-1], которые

          больше, чем ключ, на одну позицию впереди

          их текущей позиции * /

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j = j - 1;

        }

        arr[j + 1] = key;

    }

}

  
// Вспомогательная функция для печати массива размера n

void printArray(int arr[], int n)

{

    int i;

    for (i = 0; i < n; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

  
/ * Драйверная программа для проверки сортировки вставок * /

int main()

{

    int arr[] = { 12, 11, 13, 5, 6 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    insertionSort(arr, n);

    printArray(arr, n);

  

    return 0;

}

Джава

// Java-программа для реализации Insertion Sort

class InsertionSort {

    / * Функция сортировки массива с использованием вставки сортировки * /

    void sort(int arr[])

    {

        int n = arr.length;

        for (int i = 1; i < n; ++i) {

            int key = arr[i];

            int j = i - 1;

  

            / * Переместить элементы arr [0..i-1], которые

               больше, чем ключ, на одну позицию впереди

               их текущей позиции * /

            while (j >= 0 && arr[j] > key) {

                arr[j + 1] = arr[j];

                j = j - 1;

            }

            arr[j + 1] = key;

        }

    }

  

    / * Утилита для печати массива размером n * /

    static void printArray(int arr[])

    {

        int n = arr.length;

        for (int i = 0; i < n; ++i)

            System.out.print(arr[i] + " ");

  

        System.out.println();

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        int arr[] = { 12, 11, 13, 5, 6 };

  

        InsertionSort ob = new InsertionSort();

        ob.sort(arr);

  

        printArray(arr);

    }

} / * Этот код предоставлен Раджатом Мишрой. * /

питон

# Python-программа для реализации Insertion Sort

  
# Функция для сортировки при вставке

def insertionSort(arr):

  

    # Пройдите через 1 до len (обр.)

    for i in range(1, len(arr)):

  

        key = arr[i]

  

        # Переместить элементы arr [0..i-1], которые

        # больше ключа, на одну позицию впереди

        № их текущей позиции

        j = i-1

        while j >= 0 and key < arr[j] :

                arr[j + 1] = arr[j]

                j -= 1

        arr[j + 1] = key

  

  
# Код драйвера для проверки выше

arr = [12, 11, 13, 5, 6]

insertionSort(arr)

for i in range(len(arr)):

    print ("% d" % arr[i])

  
# Этот код предоставлен Мохитом Кумрой

C #

// C # программа для реализации Insertion Sort

using System;

  

class InsertionSort {

  

    // Функция для сортировки массива

    // используя сортировку вставкой

    void sort(int[] arr)

    {

        int n = arr.Length;

        for (int i = 1; i < n; ++i) {

            int key = arr[i];

            int j = i - 1;

  

            // Переместить элементы arr [0..i-1],

            // которые больше ключа,

            // на одну позицию впереди

            // их текущая позиция

            while (j >= 0 && arr[j] > key) {

                arr[j + 1] = arr[j];

                j = j - 1;

            }

            arr[j + 1] = key;

        }

    }

  

    // Утилита для печати

    // массив размером n

    static void printArray(int[] arr)

    {

        int n = arr.Length;

        for (int i = 0; i < n; ++i)

            Console.Write(arr[i] + " ");

  

        Console.Write("\n");

    }

  

    // Код драйвера

    public static void Main()

    {

        int[] arr = { 12, 11, 13, 5, 6 };

        InsertionSort ob = new InsertionSort();

        ob.sort(arr);

        printArray(arr);

    }

}

  
// Этот код предоставлен ChitraNayal.

PHP

<?php 
// PHP программа для сортировки вставок

  
// Функция для сортировки массива
// используя сортировку вставкой

function insertionSort(&$arr, $n)

{

    for ($i = 1; $i < $n; $i++)

    {

        $key = $arr[$i];

        $j = $i-1;

      

        // Переместить элементы arr [0..i-1],

        // больше ключа, чтобы

        // на одну позицию впереди их

        // текущая позиция

        while ($j >= 0 && $arr[$j] > $key)

        {

            $arr[$j + 1] = $arr[$j];

            $j = $j - 1;

        }

          

        $arr[$j + 1] = $key;

    }

}

  
// Функция полезности для
// выводим массив размером n

function printArray(&$arr, $n)

{

    for ($i = 0; $i < $n; $i++)

        echo $arr[$i]." ";

    echo "\n";

}

  
// Код драйвера

$arr = array(12, 11, 13, 5, 6);

$n = sizeof($arr);

insertionSort($arr, $n);

printArray($arr, $n);

  
// Этот код предоставлен ChitraNayal.
?>

Выход:

5 6 11 12 13

Сложность времени: O (n * 2)

Вспомогательное пространство: O (1)

Граничные случаи : сортировка вставкой занимает максимальное время, если элементы сортируются в обратном порядке. И это занимает минимальное время (порядок n), когда элементы уже отсортированы.

Алгоритмическая парадигма: инкрементальный подход

Сортировка на месте: да

Стабильно: да

Онлайн: да

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

Что такое бинарная сортировка?
Мы можем использовать бинарный поиск, чтобы уменьшить количество сравнений в обычной сортировке вставкой. Бинарная сортировка вставок использует бинарный поиск, чтобы найти правильное место для вставки выбранного элемента на каждой итерации. При обычной вставке сортировка занимает O (i) (на i-й итерации) в худшем случае. Мы можем уменьшить его до O (logi), используя бинарный поиск. Алгоритм в целом все еще имеет время выполнения в наихудшем случае O (n2) из-за серии перестановок, необходимых для каждой вставки. Направьте это для реализации.

Как реализовать сортировку вставок для связанного списка?
Ниже приведен простой алгоритм сортировки вставок для связанного списка.

1) Create an empty sorted (or result) list
2) Traverse the given list, do following for every node.
......a) Insert current node in sorted way in sorted or result list.
3) Change head of given linked list to head of sorted (or result) list. 

Направьте это для реализации.

Фотосъёмка:





Тест на вставку сортировки


Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz

Сортировка выбора , пузырьковая сортировка , сортировка вставкой, сортировка слиянием, сортировка кучи , быстрая сортировка , сортировка по радикалу , счетная сортировка , сортировка по корзинам , ShellSort , сортировка по гребне ,

Практика кодирования для сортировки.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Сортировка вставки

0.00 (0%) 0 votes