设计一种分类和打印算法 [英] Design an algorithm for sorting and printing

问题描述

设计优化算法。程序中的输入作为来自用户的数字输出，输出是每个步骤的逗号分隔排序输出。

例如-ip from user->

 5 
 4 
 23 
 2 
 56 
 1 

其中第一个数字即5是要输入的总数。

和输入数字后每一步的输出将是

 4 
 4,23 
 2,4,23 
 2,4,23,56 
 1,2,4， 23,56 

我的尝试：

  void 排序（ int  Arr []， int  nTotalNum）
 {
  int  nSorted =  1 ; 
  for （ int  i =  0 ; i<（nTotalNum  -   1 ）&& nSorted; ++ i）
 {
 nSorted =  0 ; 
  for （ int  j =  0 ; j<（nTotalNum  -  i  -   1 ）; ++ j）
 {
  if （Arr [j]> Arr [j + 1]）$ ​​b $ b {
  int  Temp = Arr [j] ; 
 Arr [j] = Arr [j + 1]; 
 Arr [j + 1] = Temp; 
 
 nSorted =  1 ; 
} 
} 
} 
} 
 
 
  void 显示（< span class =code-keyword> int  Arr []， int  nNum）
 {
  for （ int  i =  0 ; i< nNum; ++ i）
 {
 cout<<编曲[I]; 
  if （i！=（nNum  -   1 ））
 {
 cout<<  ，; 
} 
} 
} 
 
 
  int  main（）
 { 
  int  nTotalNum =  0 ; 
  int  nCount =  0 ; 
 
 cin>> nTotalNum; 
 
  if （nTotalNum>  0 ）
 {
  int  * Arr =  new   int  [nTotalNum]; 
  for （ int  i =  0 ; i< nTotalNum; ++ i）
 {
 nCount ++; 
 cin>>编曲[I]; 
 
排序（Arr，nCount）; 
显示（Arr，nCount）; 
 cout<< endl; 
} 
  delete  [] Arr; 
} 
  return   0 ; 
} 

解决方案

它会做任何预期的事情。只是想检查一下其他一些优化的方法这样做。因为这是在一次采访中被问到我而且这个答案没有被接受。

嗯......它根本没有优化。

首先要注意的是它没有被优化：你一次只收到一个项目，并且每次都要显示一个排序列表。

所以每次你尝试插入时，你都是使用排序列表和单个未排序元素。您不需要嵌套循环，因为您所要做的就是找到插入数据的位置并将其放入。每次完整的冒泡排序并不是一种有效的方法。即使使用qsort库函数也没有效率！

其次，这里的list一词可能是相关的：它们可能需要一个真正的列表 - 这使得插入更容易。

第三，这是糟糕的代码。没有记载，模糊不清，行尾是在错误的地方输出的 - 它只是不是性感的代码，它会让任何人坐起来去雇用这个人！如果我非常诚实，那么在他的第一个计算机课程的第二周或第三周看起来就像是学生作品......不是经验丰富的专业人士提供的优质软件。

你的程序未完全优化。

每次调用 sort 时，都会对数组进行重新排序。你忘了考虑你只是为已经排序的数组添加一个值。

建议：拿笔和纸并手动进行排序，并尝试设置如何在程序中翻译。 / BLOCKQUOTE>

Design an optimized algorithm. Where in program takes input as numbers from user and output is comma separated sorted output at each step.
for example- Ip from user->

5
4
23
2
56
1

where first number i.e 5 is total numbers to be input.
and Ouput at each step after entering a number will be

4
4,23
2,4,23
2,4,23,56
1,2,4,23,56

What I have tried:

void Sort(int Arr[], int nTotalNum)
{
	int nSorted = 1;
	for(int i = 0 ; i < (nTotalNum - 1) &&  nSorted; ++i)
	{
		nSorted = 0;
		for(int j = 0 ; j < (nTotalNum - i - 1); ++j)
		{
			if(Arr[j] > Arr[j+1])
			{
				int Temp = Arr[j];
				Arr[j]   = Arr[j+1];
				Arr[j+1] = Temp;

				nSorted = 1;
			}
		}
	}
}


void Display(int Arr[], int nNum)
{
	for(int i = 0; i < nNum; ++i) 
	{
		cout << Arr[i];
		if( i != (nNum - 1))
		{
			cout << ",";
		}
	}
}


int main()
{
	int nTotalNum = 0;
	int nCount = 0;

	cin >> nTotalNum;
		
	if(nTotalNum > 0)
	{
		int* Arr = new int[nTotalNum];
		for(int i = 0; i < nTotalNum; ++i)
		{
			nCount++;
			cin >> Arr[i];
			
			Sort(Arr, nCount);
			Display(Arr, nCount);
			cout<<endl;
		}
		delete[] Arr;
	}
	return 0;
}

解决方案

"It does everything whatever is expected. Just wanted to check if some other optimized way to do that. Because this was asked to me in one of the interview and this answer was not accepted."
Well...it's not optimised at all.
The first thing to note is that it's not optimised: you are receiving items one at a time, and expected to show a sorted list each time.
So each time you try to insert, you are working with a sorted list and a single unsorted element. You don't need a nested loop, because all you have to do is find where to insert the data and put it in. A full "bubble sort" each time is not an efficient way to do it. Even using the qsort library function is inefficient here!
Secondly, the word "list" here may be relevant: it may be that they want a true list - which makes the insertion even easier.
Thirdly, it's poor code. Undocumented, vague, the end of line is output in the wrong place - it's just not "sexy" code which would make anyone sit up and go "Employ this guy!" If I'm brutally honest, it looks like a student piece in the second or third week of his first computing course...not a polished piece of software by an experienced professional.

Your program is not optimized at all.
You re-sort the array every time you call sort. You forgot to take into account that you just add a value to an array already sorted.
Advice: take a pen and paper and do the sorting manually, and try to device how to translate in program.

这篇关于设计一种分类和打印算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！