bubble_sort
기본 사상: 한쪽에서부터 서로 인접한 두 요소를 하나하나 비교하여 역순을 발견하면 교환된다.
내 코드 붙여넣기: (오름차순 정렬)
코드 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 순환마다 이 번의 최소수를 확정할 수 있고
이 최소수를 맨 앞에 놓아라.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.