bubble_sort

2483 단어
이제 거품 순서를 말해 봅시다.
기본 사상: 한쪽에서부터 서로 인접한 두 요소를 하나하나 비교하여 역순을 발견하면 교환된다.
내 코드 붙여넣기: (오름차순 정렬)
코드 1: (매번 정렬되지 않은 최소 수를 수조의 맨 앞머리로 먼저 낸다)
#include<iostream>
using namespace std;

/*       */
void bubble_sort(int a[],int n)  
{
	int i,j,temp;

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

int main()
{
	int i,n;
	int a[100];

	while(cin>>n,n)  
	{
		for(i=0;i<n;i++)
			cin>>a[i];

		bubble_sort(a,n);

		for(i=0;i<n;i++)
			cout<<a[i]<<" ";

		cout<<endl<<endl;
	}

	return 0;
}

 
코드2: (매번 정렬되지 않은 최대 수를 수조 맨 뒤로 끌어올리기)
/*       */
void bubble_sort(int a[],int n)  
{
	int i,j,temp;

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

        
이상의 두 코드는 모두'중규중규'이므로 개선할 여지가 있다.예를 들면, 만약 어떤 비교에서 이미 없는 것을 발견한다면
대조가 바뀌면 수조가 이미 질서정연하다는 것을 설명한다.끝낼 수 있어.다음 코드에 bool exchanged를 도입하여 정렬 여부를 보조합니다
교환이 이루어졌습니다.
코드 3은 다음과 같습니다.
void bubble_sort(int a[],int n)   
{
	int i,j,temp;
	bool exchanged;   //             

	i=1;
	do
	{
		exchanged=false;
		
		for(j=n-1;j>=i;j--)
		{
			if(a[j]<a[j-1])
			{
				temp=a[j];
				a[j]=a[j-1];
				a[j-1]=temp;

				exchanged=true;
			}
		}

		i++;
	}while(i<=n-1 && exchanged==true);
}

 
다시 한 번 분석해 봅시다.
승차순으로 배열해서 분석하자.기본 사상은 마지막 원소부터 둘씩 비교하는 것이다. 만약 뒤의 수가 앞의 수보다 작다면 바꾸는 것이다
마지막 수를 비교할 때까지 두 수의 순서.이때는 최소수가 맨 앞까지 배열되는 것을 확정한다.그러면 다음에 비교하면 더 이상 비교하지 않아도 된다
세었어.바로 코드 중의 두 번째 for 순환, for(j=n-1;j>i;j--)이다.첫 번째 for 순환은 몇 개의 수가 위치를 정하고 있는지 기록하는 것이다.
           Attiontion:
①거품 정렬도 제자리 정렬이고temp라는 보조 공간만 있으면 된다.
② 거품 정렬의 시간성능은 O(n^2), 공간성능은 O(n)이다.
③ 거품 정렬은 매번 한 수의 최종 위치를 정할 수 있다.만약 승차순에 거품이 생기면 두 번째 for 순환마다 이 번의 최소수를 확정할 수 있고
이 최소수를 맨 앞에 놓아라.

좋은 웹페이지 즐겨찾기