标签: insertion-sort

我正在尝试为Insertion排序编写OpenMP解决方案,但是我遇到问题要让它并行运行并给出正确的结果:).有没有办法让Insertion排序并行运行.

这是我的代码:

void insertionsort(int *A, int num)
{

// clock_t start, stop;
// 
// start=clock();
int k;
#pragma omp parallel for shared(A) private(k)
for(int n = 1; n < num; n++)
{
    int key = A[n];
    k = n;
#pragma omp critical

    for(;k>0 && A[k-1]> key;k--)
    {
        A[k] = A[k-1];   
    }



    A[k] = key;  


}
// stop=clock();
// cas = (double)(stop-start)/CLOCKS_PER_SEC;
}

为什么使用二进制搜索的插入排序比使用线性搜索的插入排序慢？

插入代码使用线性搜索排序:

void InsertionSort(int data[], int size)
{
    int i=0, j=0, temp=0;

    for(i=1; i<size; i++)
    {
     temp = data[i];
     for (j=i-1; j>=0; j--)
         {
             if(data[j]>temp)
             data[j+1]=data[j];
             else  
                 break;
         }
     data[j+1] = temp;       
    }        
}

使用线性搜索的插入排序代码:

void InsertionSort (int A[], int n)
{
    int i, temp;
    for (i = 1; i < n; i++)
    {
        temp = A[i];

        /* Binary Search */

        int low = 0, high = i, k;

        while (low<high)
        {
            int mid = (high + low) / 2; …

我对插入排序的实现似乎是在排序第一个元素的例外.我这里有一个小测试用例.谁能告诉我算法有什么问题？

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;



void Insert(int *S, int k)
{
        int key = S[k];
        int j = k-1;
        while(j>0 && S[j] > key)
        {
                S[j+1] = S[j];
                j--;
        }

        S[j+1] = key;
}


void Insertionsort(int S[], int n)
{
        if(n>1)
                Insertionsort(S,n-1);
        Insert(S,n);

}

int main()
{
        srand ( time(NULL) );
        int S1_8[8];
        for(int i=0; i<8; i++)
                S1_8[i] = rand()%100;

        Insertionsort(S1_8,8);

        for(int i=0; i<8; i++)
        {
                cout << S1_8[i] << endl;
        }

        return 0;
}

可能的重复：
插入排序与冒泡排序与选择排序的效率？

对于大数组，选择排序比插入更快吗？最坏的情况是什么时候？

我知道插入比选择更快，但是对于大型数组和最坏的情况？

我正在用 C++ 实现一个简单的插入排序，如下所示：

void insertion_sort(int a[], int size)
{
    int temp;
    for (int i = 2; i < size; i++)
    {
        temp = a[i];
        int j = i - 1;
        while (j > 0 && a[j] > temp)
        {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = temp;
        print_array(a, size);
    }
    cout << "Final:" << endl;
    print_array(a, size);
}

但是，这会对数组中除第一个元素之外的所有元素进行排序。这是输出的样子：

Original array:
5 2 4 1 3 0 
Insertion Sorted array:
5 2 4 1 3 0 …

我试图弄清楚如何使用插入排序来排序一组int.我需要从原始数组中获取值并将它们放入新数组中.我将展示我的代码,但是我遇到了一堵砖墙,无法弄清楚这种排序方法是如何工作的

import java.util.Arrays;
public static void main(String[] args)
{
int[] orgArray = {5,4,1,6,3,144,2,14};
    int[] newArray = new int[orgArray.length];
    int currentNum=0;
    for(int x=1; x<orgArray.length; x++)
    {
        if(x==1)
            newArray[0]=orgArray[0];
        else
            for(int y=x;y>0; y--)
            {
                currentNum = orgArray[x];
                if(newArray[y]<currentNum)
                {
                    for(int z=orgArray.length-2;z>y;z--)
                        newArray[z]=newArray[z+1];
                    newArray[x]=orgArray[x];
                }

            }
    }
    System.out.println("Ascending order : " + Arrays.toString(newArray));
}

输出是:

Ascending order : [5, 0, 14, 14, 14, 14, 14, 14]

我基本上是在处理以下问题，我试图改变插入排序，以便它也可以删除它计数器的重复项。下面是插入排序。

public void insertSort() {

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

            int temp = a[i];
            int j = i;

            while (j > 0 && temp <= a[j - 1]) {

                a[j] = a[j - 1];

                j--;
            }

            a[j] = temp;
        }

    }

我不确定我是否正确理解了该方法。如果我理解正确（请告诉我我是否错了），该方法建议我应该在内部 while 循环开始之前遍历整个数组，并使用任意数字（例如 -1）标记任何重复项。然后当内部 while 循环开始时，它将整理数组，所有重复项将在开始时堆叠在一起。

如果是这种情况，那么我可以在插入排序开始之前简单地将数组中的每个元素相互比较，并标记任何重复项 - 1，然后插入排序将处理排序部分。之后我可以减少arraySize。

但是我觉得我没有正确理解它，所以有人可以就此提出任何建议吗？

我正在尝试解决这个问题http://www.mycodeschool.com/work-outs/sorting/7 问题是在插入排序中找不到任何变化。

我已经编写了代码，但无法弄清楚我在逻辑上哪里出错了

http://ideone.com/GGjZjw

#include<iostream>
#include<cstdio>
#include<cmath>
// Include headers as needed

using namespace std;

int main()
{
// Write your code here
int T,count,n,*a;
// int imin;
cin >> T;
int value,hole;

while(T--)
{
    cin >> n;
    count=0;
    a=new int[n];
    //reading the input array
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }

    // considering the 0th element to be already sorted and
    // remaining list unsorted
    for(int i=1;i<n;i++)
    {
        value=a[i];
        hole=i;
        // shifting 
        while(hole>0&&a[hole-1]>value)
        {
            // …

我已经实现了Insertion排序和堆排序.理论上,Heap排序具有nlogn时间复杂度,插入具有n ^ 2.为什么,然后我的Insertion实现需要大约6倍的时间来排序100,000个长阵列？

我使用JMH来对每种排序算法的平均时间进行基准测试.这是我的基准代码:

import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;

public class MyBenchmark {

// setup the benchmark - create a new array for each iteration
    @State(Scope.Thread)
    public static class MyState {
        int[] array = null;

        @Setup(Level.Iteration)
        public void doSetup() {
            array = createArray(100000, 0, 100);
        }
    }

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.SECONDS)
    public void insertionSort(MyState state) {
        int[] array = state.array;

        for (int i = …

为此，插入函数需要通过将大于值的项目向右移动来为值腾出空间。它应该从 rightIndex 开始，并在找到小于或等于 value 的项目或到达数组开头时停止。一旦函数为值腾出了空间，它就可以将值写入数组。

var insert = function(array, rightIndex, value) {
    var key = value;
    for(var i = rightIndex; array[i] > value ; i = i - 1)
    {
        array[rightIndex + 1] = array[rightIndex];
    }
    array[i+1] = value;
};

为什么我输入这个数组后这个函数不能正常工作！

var array = [3, 5, 7, 11, 13, 2, 9, 6];

它显示了这个结果：

insert(array, 4, 2);

2,5,7,11,13,13,9,6