버블 정렬을 위한 C 프로그램: C의 버블 정렬
게시 됨: 2020-10-20목차
소개
배열의 정렬은 컴퓨터 과학에서 매우 중요한 위치를 차지합니다. 특정 순서로 데이터를 정렬해야 할 때 유용합니다. 다양한 종류의 정렬 알고리즘이 있습니다. 가장 일반적이고 널리 사용되는 정렬 알고리즘은 버블 정렬입니다.
C의 버블 정렬
버블 정렬에서 정렬에 사용되는 기술은 간단하고 이해하기 쉽습니다. 현재 요소를 다음 요소와 비교하고 조건에 따라 더 크거나 작으면 교체합니다. 알고리즘은 매우 정확합니다. 요소가 위치를 찾을 때까지 다른 요소와 비교할 때마다 이를 통과라고 합니다.
이 알고리즘은 배열과 같은 거품의 상단을 걸러내므로 물 속의 거품과 비슷합니다. 정렬에 사용되는 모든 알고리즘 중 버블 정렬은 시간 복잡도가 O(n^2)인 가장 쉽고 가장 느립니다. 그러나 스와핑이 완료되면 루프를 종료하는 플래그 변수를 사용하여 알고리즘을 최적화할 수 있습니다. 버블 정렬의 가장 좋은 경우는 배열이 정렬될 때 O(n)일 수 있습니다.
예를 들어 아래와 같이 5개의 숫자로 구성된 정렬되지 않은 배열을 가정해 보겠습니다.
13, 32,26, 34,9
버블 정렬은 처음 두 요소를 고려하기 시작하고 비교하여 어느 것이 더 큰지 확인합니다. 이 경우 32는 13보다 큽니다. 따라서 이 부분은 이미 y로 정렬되어 있습니다. 다음으로 32와 26을 비교합니다. 따라서 32는 26보다 크므로 교환해야 합니다. 새 배열은 다음과 같습니다.
13, 26, 32,34,9
다음으로, 우리는 32와 34를 비교합니다. 우리는 그것들이 이미 정렬되어 있다는 것을 압니다. 따라서 우리는 마지막 두 변수 34와 9로 이동합니다. 34는 9보다 크므로 교환해야 합니다.
값을 교환하고 첫 번째 반복 후에 배열의 끝에 도달합니다. 이제 배열은 다음과 같이 보일 것입니다.
13, 26. 32,9,34
두 번째 반복 후 배열은 다음과 같습니다.
13, 26, 9,32,34
세 번째 반복 후에 배열은 다음과 같이 됩니다.
13,9,26,32,34
네 번째 반복 후에 배열이 완전히 정렬됩니다.
9, 13,26,32,34
필독: C로 된 프로젝트 아이디어
알고리즘
여기서 우리는 배열에 n개의 요소가 있다고 가정합니다. 또한, 값 교환 기능이 모든 값을 교환하여 배열 번호를 정렬된 순서로 만든다고 가정합니다.
BubbleSort(배열) 시작
목록의 모든 요소에 대해
배열[i]> 배열[i+1]인 경우
값 교환(배열[i], 배열[i+1])
종료
끝내다
반환 배열
버블 정렬 종료
읽기: 데이터 구조에서 정렬: 범주 및 유형
의사 코드
위의 알고리즘에서 전체 배열이 오름차순으로 정렬될 때까지 배열 요소의 각 쌍 간에 비교가 있음이 분명합니다. 배열이 이미 오름차순으로 정렬된 경우 알고리즘의 결과와 같은 몇 가지 복잡성 문제가 발생할 수 있습니다. 문제를 완화하기 위해 하나의 플래그 변수를 사용하여 스와핑이 있는지 확인할 수 있습니다. 더 이상 스와핑이 필요하지 않으면 내부 루프에서 나옵니다.
BubbleSort 알고리즘의 의사 코드는 다음과 같이 작성할 수 있습니다.
절차 BubbleSort(배열: 배열의 항목)
반복 = array.count;
k=0에서 1을 반복하려면 다음을 수행하십시오.
플래그 = 거짓
l=0에서 iterate-1을 수행하려면 다음을 수행하십시오.
if (배열[l]> 배열[l+1]) 그러면
값 교환(배열[l], 배열[l+1])
플래그=참
종료
끝내다
(스왑되지 않은) 경우
부서지다
종료
종료
종료 프로시저 반환 배열
C에서 버블 정렬 의 샘플 프로그램을 사용해 보겠습니다 .
# 포함<stdio.h>
보이드 메인
{
정수 배열 [10], i, j, num
(i=0, i<=9, i++)
{
scanf("%d", &배열[i])
}
for(i=0;i<=9;i++)
{
for(j=0;j<=9-i;j++)
{
if(배열[j]>배열[j+1])
{
숫자 = 배열[j];
배열[j]=배열[j+1];
배열[j+1]=숫자;
}
}
}
printf("정렬된 배열은 /n입니다.");
for(i=0;i<=9;i++)
{
printf("%d",&배열[i])
}
}
샘플에서 볼 수 있듯이 이 버블 정렬 알고리즘은 사용자로부터 10개의 숫자를 받아 배열에 저장합니다. 다음 부분에는 두 개의 for 루프가 있습니다. 외부 루프는 0에서 9보다 작은 I 값에 대해 실행됩니다. 외부 루프의 기능은 다른 요소와 비교해야 하는 값의 모든 요소를 처리하는 것입니다.
외부 루프 내부에 또 다른 루프가 있습니다. j=0에서 시작하여 8보다 작거나 같을 때까지 실행됩니다. 내부에는 array[j]가 array[j+1]보다 큰지 비교하고 확인하는 조건부 if 문이 있습니다. 조건이 만족되면 array[j]와 array[j+1]의 값이 서로 바뀝니다.
이를 위해 num이라는 이름의 변수가 사용됩니다. 첫 번째 array[j]는 num에 할당되고 array[j+1]은 array[j]에 할당되고 마지막으로 num은 array[j+1]에 할당됩니다. 이 프로세스는 배열의 모든 요소가 오름차순으로 정렬될 때까지 계속됩니다. 그런 다음 정렬된 배열이 인쇄됩니다.
버블 정렬의 최적화된 구현
결과를 개선하기 위해 버블 정렬에 최적화된 알고리즘이 있습니다. 플래그 변수를 사용하면 최적화가 수행됩니다. 플래그 변수는 스와핑이 있으면 1을 유지하고 그렇지 않으면 루프에서 벗어날 것입니다. 다음은 C에서 최적화된 버블 정렬 프로그램입니다.
#include<stdio.h>
보이드 메인
{
정수 배열 [10], i, j, num, 플래그=0;
(i=0, i<=9, i++)
{
scanf("%d", &배열[i])
}
for(i=0;i<=9;i++)
{
for(j=0;j<=9-i;j++)
{
if(배열[j]>배열[j+1])
{
숫자 = 배열[j];
배열[j]=배열[j+1];
배열[j+1]=숫자;
플래그=1;
}
if(! 플래그)
{
부서지다;
}
}
}
printf("정렬된 배열은 /n입니다.");
for(i=0;i<=9;i++)
{
printf("%d",&배열[i])
}
}
주어진 프로그램은 일반적인 버블 정렬 프로그램과 유사한 방식으로 실행됩니다. 유일한 변경 사항은 플래그 변수를 사용하는 것입니다. 초기에 플래그는 0으로 설정됩니다. 그러나 스와핑이 발생하면 플래그는 1이 됩니다. 이는 어레이가 여전히 한 번 더 확인해야 함을 의미합니다. 반면에 플래그가 1이 아닌 경우 스와핑이 발생하지 않았음을 의미하며 배열이 이미 정렬되어 있다고 가정하고 내부 루프를 종료합니다. 실행되면 일반 버블 정렬과 동일한 결과를 얻을 수 있습니다.
시간 복잡도
버블 정렬의 최상의 시간 복잡도는 O(n)입니다. 배열이 이미 정렬되어 있을 때 발생합니다. 최악의 경우는 배열이 정렬되지 않은 경우 O(n*n)입니다.
읽기: 지금 체크아웃해야 하는 Java의 상위 12개 패턴 프로그램
다음은?
Java, 전체 스택 소프트웨어 개발에 대해 자세히 알아보려면 작업 전문가를 위해 설계되었으며 500시간 이상의 엄격한 교육, 9개 이상의 프로젝트를 제공하는 upGrad & IIIT-B의 전체 스택 소프트웨어 개발 PG 디플로마를 확인하십시오. , 과제, IIIT-B 동문 상태, 실질적인 실습 캡스톤 프로젝트 및 최고의 기업과의 취업 지원.