选择排序..帮助 [英] Selection Sort .. Help

问题描述

嗨..

我正在尝试实施选择排序的算法步骤。



1 - >找到最低指数

2 - >与Top&增量。



输出不正确..请有一个L ^ _ ^ K. >！？

  void   in （ int  arr []， int  size）
 { 
  for （ int  i =  0 ; i< size; i ++）
 {
 cout<<  元素＃<< i + 1<<  ：; 
 cin>> ARR [I]; 
} 
} 
  void  out（ int  arr []，  int  size）
 {
  for （ int  j =  0 ; j< size; j ++）
 {
 cout<< arr [j]<<   ||; 
} 
} 
  int  find_min（ int  arr []，  int  size）
 {
  int  index =  0 ; 
  for （ int  k =  0 ; k< size; k ++）
 {
  if （arr [index]> arr [k]）
 {
 index = k; 
} 
} 
  return  index; 
} 
  void  exchange（ int & x， int & y）
 {
  int  temp = x; 
 x = y; 
 y = temp; 
} 
  void  selection_sort（ int  arr []， int  size）
 {
  int  loc; 
  for （ int  i =  0 ; i< size; i ++）
 {
 loc = find_min（arr，size  -  i）; 
 exchange（arr [loc]，arr [i]）; 
} 
} 
 
  int  main（）
 {
  const   int  size =  5 ; 
  int  my_array [size]; 
  in （my_array，size）; 
 out（my_array，size）; 
 cout<<  选择后排序..<<   \ n \ n; 
 selection_sort（my_array，size）; 
 cout<<   \ n\t<<   p r i n t g ...<< ENDL; 
 out（my_array，size）; 
 
  return   0 ; 
} 

= =>更新（V2）

  int  find_min（ int  ar []， int  size）
 {
  int  index =  0 ; 
  bool  found =  false ; 
  for （ int  i =  1 ; i< size; i ++）
 {
  if （ar [index]> ar [i]）
 {
 index = i; 
 found =  true ; 
} 
} 
 
 如果（找到）
 {
  return  index; 
} 
  else  
  return   -   1 ; 
 
} 
 
  void  selection_sort（ int  arr []， int  size）
 {
  int  loc; 
  for （ int  count =  0 ; count< size; count ++）
 {
 loc = find_min（arr，size  -  count）; 
  if （loc> =  0 ）
 {
 exchange （arr [count]，arr [loc]）; 
} 
} 
} 

解决方案

主要错误是在步骤i中你应该找到元素的最小值为... N-1并用arr [i]切换位置。所以不应该是

  for （ int  i =  0 ; i< size; i ++）
 {
 loc = find_min（arr  + i ，尺寸 -  i）; 
 exchange（arr [loc]，arr [i]）; 
} 
 

一个更美观的问题是你在find_min函数中做了一个多余的比较：

  int  find_min（ int  arr []， int  size）
 {
  int  index =  0  ; 
  for （ int  k =  0 ; k< size; k ++）
 {
  if （arr [index]> arr [k]）

在第一次迭代中，您将arr [0]与arr [0]进行比较。那你为什么不用k = 1开始循环：

  int  find_min（ int  arr []， int  size）
 {
  int  index =  0 ; 
  for （ int  k =  1 ; k< size; k ++）
 {
  if （arr [index]> arr [k]）

Hi ..
I'm Trying To Implement The Algorithmic Steps of Selection Sort.

1 -> Find The Min Index
2 -> Exchange It With The Top & Increment.

The Output Is Not Correct .. Please Have A L^_^K. >!?

void in(int arr[], int size)
{
    for(int i = 0; i < size; i++)
    {
        cout << "Element # " << i+1 << ": ";
        cin >> arr[i];
    }
}
void out(int arr[], int size)
{
    for(int j = 0; j < size; j++)
    {
        cout << arr[j] << "||";
    }
}
int find_min(int arr[], int size)
{
    int index = 0;
    for(int k = 0; k < size; k++)
    {
        if( arr[index] > arr[k])
        {
            index = k;
        }
    }
    return index;
}
void exchange(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}
void selection_sort(int arr[], int size)
{
    int loc;
    for(int i = 0; i < size; i++)
    {
        loc = find_min(arr, size - i);
        exchange(arr[loc], arr[i]);
    }
} 

int main()
{
    const int size = 5;
    int my_array[size];
    in(my_array, size);
    out(my_array, size);
    cout << "After Selection Sort.." << "\n\n";
    selection_sort(my_array, size);
    cout << "\n\t" << "p r i n t i n g.." << endl;
    out(my_array, size);

    return 0;
}

= = > Update(V2)

int find_min(int ar[], int size)
{
    int index = 0;
	bool found = false;
	for(int i = 1; i < size; i++)
    {
		if(ar[index] > ar[i])
        {
			index = i;
			found = true;
        }
    }

	if (found)
	{
		return index;
	}
	else
		return -1;
	
}

void selection_sort(int arr[], int size)
{
    int loc;
	for(int count = 0; count < size; count++)
    {
		loc = find_min(arr, size - count);
		if (loc >= 0)
		{
			exchange(arr[count], arr[loc]);
		}
    }
}

解决方案

The main error is that in step i you should find the minimum of the elements i ... N-1 and switch places with arr[i]. So shouldn't it be

for(int i = 0; i < size; i++)
{
    loc = find_min(arr+i, size - i);
    exchange(arr[loc], arr[i]);
}

A more cosmetic problem is that you do one superfluous compare in your find_min function:

int find_min(int arr[], int size)
{
    int index = 0;
    for(int k = 0; k < size; k++)
    {
        if( arr[index] > arr[k])

In the first iteration you are comparing arr[0] with arr[0]. So why don't you start the loop with k = 1:

int find_min(int arr[], int size)
{
    int index = 0;
    for(int k = 1; k < size; k++)
    {
        if( arr[index] > arr[k])

这篇关于选择排序..帮助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！