Процессы для сортировки вставками

Question

Я искал алгоритмы сортировки в течение нескольких дней. В настоящее время я делаю Insertion Sort. Итак, общий алгоритм:

void insertionSort(int N, int arr[]) {
    int i,j;
    int value;
    for(i=1;i<N;i++)
    {
        value=arr[i];
        j=i-1;
        while(j>=0 && value<arr[j])
        {
            arr[j+1]=arr[j];
            j=j-1;
        }
        arr[j+1]=value;
    }
    for(j=0;j<N;j++)
    {
        printf("%d ",arr[j]);
    }

    printf("\n");
}

Теперь я сделал это:

void print_array(int arr_count, int* arr){
        int i;
        for (i=0;i<arr_count;i++){
                printf("%d ",arr[i]);
        }
        printf("\n");

    }

    void swap(int* m, int* n){
        int t = 0;
        t = *m;
        *m = *n;
        *n = t;
    }

    void insertionSort(int arr_count, int* arr) {
        int i, j;

        for(i = 0;i<arr_count;i++){
            for (j=0;j<i;j++){
                if (arr[i] < arr[j]){
                    swap(arr+i, arr+j); 
                  }
            }
            //if (i!=0)
            //print_array(arr_count, arr);
        }

    print_array(arr_count, arr);
    }

Теперь, мой вопрос: в чем разница между моим индивидуальным подходом и традиционным подходом. Оба имеют сложность N ² ....
Пожалуйста, помогите ..
Заранее спасибо

Answer 1

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

Еще одним ключевым отличием является, в лучшем случае, сложность вставки сортировки и ваш алгоритм. Сортировка вставки останавливается, если значение

Answer 2

На каждой итерации исходный код, который вы представляете, перемещает каждый элемент на место, перемещая элементы в цикле. Для цикла n -элемента, который включает в себя n + 1 назначения.

Можно реализовать сортировку вставкой, перемещая элементы с попарными перестановками вместо больших циклов. На самом деле этому иногда учат. Это возможно, потому что любая перестановка (не только циклы) может быть выражена как серия перестановок. Реализация цикла n -элементов с помощью свопов требует n -1 свопов, а каждый своп, представляющий собой цикл из 2 элементов, требует 2 + 1 = 3 назначения. Таким образом, для циклов, превышающих два элемента, подход, использующий парные свопы, делает больше работы, масштабируя его как 3 * ( n -1), а не n + 1. Это не меняет асимптотическую сложность, однако, как вы можете видеть по факту, что показатель n не изменяется.

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

Сканирование вперед означает, что как только вы найдете позицию вставки, вы только начали. Вы затем должны циклически изменить элементы. В результате ваш подход проверяет каждый элемент заголовка отсортированного массива на каждой итерации. Кроме того, когда он фактически выполняет переупорядочение, он выполняет кучу ненужных сравнений. Вместо этого он мог бы использовать знание, что заголовок списка начал сортироваться, и просто выполнить цикл (в любом случае) без каких-либо дополнительных сравнений. Дополнительные сравнения маскируют тот факт, что код просто выполняет соответствующий цикл элемента в этот момент ( вы осознали это?), И, возможно, поэтому несколько человек приняли вашу реализацию за Bubble Sort.

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