如何优化我的代码以在C ++中对数组进行排序？ [英] How do I optimize my code to sort an array in C++?

问题描述

我编写了一个程序来为Hackerrank中值问题排序一个数组，我的代码通过3/4测试用例。当阵列的总元素为10001时，最后一个测试用例由于超时而失败。如何优化此代码以防止更高数字的超时？

  #include   <   iostream  >  
  使用 命名空间标准; 
  int  main（）{
  int  n，j，i，tmp， MED; 
 cin>> N; 
  int  * a =（ int  *）malloc（n *  sizeof （ int ））; 
  for （i =  0 ; i< n; i ++）
 cin> ;> A [1]; 
  for （i =  0 ; i< n-  1 ; i ++）{
  for （j =  0 ; j< ; ni-  1 ; j ++）{
  if （a [j]> a [ j + 1]）{
 tmp = a [j]; 
 a [j] = a [j + 1]; 
 a [j + 1] = tmp; 
} 
} 
} 
 med = a [n / 2]; 
免费（a）; 
 cout<< MED; 
  return   0 ; 
} 

我的尝试：



我尝试将整数更改为long int但时间复杂度保持不变。

解决方案

简单：更改算法。

这是一个简单的冒泡排序：它不是一种快速算法，而且有更快的版本：排序算法 - 维基百科 [ ^ ]



但是你可以通过记住你最后交换的地方，忽略分类区域来显着改善泡泡;通过双向进行，所以传递一个移动到最后，第二个移动最低到开始。



但是改变算法以获得时间效率的算法随着数据大小的增加，这将是最大的改进。

将循环更改为如下所示：

  for （i =  0 ; i< n  -   2 ; i ++）
 {
  for （j = i +  1 ; j< n  -   1 ; j ++）
 {
  if （a [j]> a [i]）
 {
 tmp = a [j]; 
 a [j] = a [i]; 
 a [i] = tmp; 
} 
} 
} 
 

这将使外循环运行到比结束少一个，内循环从外循环后运行一个索引到数组的末尾。问题是内部循环重复处理之前已经评估过的项目，因此浪费时间。此外，此代码不会仅检查相邻条目。它检查i和j索引处的数组，这些索引并不总是相邻的。这应该可以更快地工作。

Quote：

如何优化此代码以防止更高的超时号码？

我同意OG和Rick，你使用的是最简单的冒泡排序算法而没有细化。这是一个坏主意，因为它效率非常低。

首先，您需要了解代码的工作原理并以此方式进行更改：

  int  cnt_test =  0 ; 
  int  cnt_swap =  0 ; 
  for （i =  0 ; i< n-  1 ; i ++）{
  for （j =  0 ; j< ; ni-  1 ; j ++）{
  cnt_test ++;  
  if （a [j]> a [j + 1]）{
  cnt_swap ++;  
 tmp = a [j]; 
 a [j] = a [j + 1]; 
 a [j + 1] = tmp; 
} 
} 
} 
  //  然后打印2计数器 
 

通过这种方式，您将能够看到工作负载。

然后使用示例运行代码数据：

1 2 3 4 5 6 7 8 9

9 1 2 3 4 5 6 7 8

2 3 4 5 6 7 8 9 1

1 2 6 5 4 3 7 8 9

那么20和30值相同的数据



然后尝试更改以使您的代码对数据敏感并查看计数器如何演变。



对排序算法的一点研究将帮助您选择更好的算法。

I wrote a program to sort an array for Hackerrank median problem, my code passes 3/4 testcases. The last testcase fails due to timeout when the total elements of the array are 10001. How can I optimize this code to prevent timeouts with higher numbers?

#include<iostream>
using namespace std;
int main() {
    int n,j,i,tmp,med;
    cin >> n;
    int *a = (int*) malloc(n * sizeof(int));
    for(i=0; i<n; i++) 
        cin >> a[i];
    for(i=0; i<n-1; i++) {
        for(j=0; j<n-i-1; j++) {
            if(a[j] > a[j+1]) {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }
    med = a[n/2];
    free(a);
    cout << med;
    return 0;
}

What I have tried:

I tried changing the integer to long int but the time complexity remains the same.

解决方案

Simple: change the algorithm.
That's a simple Bubble sort: it's not a "quick" algorithm by any means, and there are much faster versions: Sorting algorithm - Wikipedia[^]

But you can dramatically improve Bubble just by "remembering" where you last swapped, and ignoring sorted areas; by doing it bidirectionally, so pass one moves the highest to the end, and the second moves the lowest to the beginning.

But changing the algorithm for a time efficient one will be the biggest improvement as data sizes increase.

Change the looping to look like this :

for( i = 0; i < n - 2; i++ )
{
    for( j = i + 1; j < n - 1; j++ )
    {
        if( a[j] > a[i] )
        {
            tmp = a[j];
            a[j] = a[i];
            a[i] = tmp;
        }
    }
}

This will have the outer loop run to one less than the end and the inner loop runs from one after the outer loop's index to the end of the array. The problem was the inner loop repeated processing of items that had been evaluated previously so it was wasting time. Also, this code does not check adjacent entries only. It checks the array at the i and j indexes which won't always be adjacent. This should work considerably faster.

Quote:

How can I optimize this code to prevent timeouts with higher numbers?

I agree with OG and Rick, you are using the simplest possible Bubble sort algorithm with no refinement. And this is a bad idea as it is really inefficient.
First, you need to understand how your code works and change it that way:

int cnt_test= 0;
int cnt_swap= 0;
for(i=0; i<n-1; i++) {
    for(j=0; j<n-i-1; j++) {
        cnt_test++;
        if(a[j] > a[j+1]) {
            cnt_swap++;
            tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;
        }
    }
}
// and then print the 2 counters

This way, you will be able to see the workload.
Then run your code with sample data:
1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9 1
1 2 6 5 4 3 7 8 9
Then same data with 20 and 30 values

Then try changes to make your code sensitive to data and see how the counters evolve.

A little study of sort algorithms will help you choose a better one.

这篇关于如何优化我的代码以在C ++中对数组进行排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！