bubble sort c with examples
C ++의 버블 정렬 기법.
버블 정렬은 가장 간단한 정렬 기술입니다.
버블 정렬 기술에서 목록의 각 요소는 인접한 요소와 비교됩니다. 따라서 목록 A에 n 개의 요소가있는 경우 A (0)은 A (1)과 비교되고 A (1)은 A (2)와 비교됩니다.
첫 번째 요소가 두 번째 요소보다 큰지 비교 한 후 두 요소가 교체됩니다.
=> 전문가의 전체 C ++ 과정을 보려면 여기를 방문하십시오.
학습 내용 :
안드로이드를위한 최고의 무료 mp3 다운로더는 무엇입니까
버블 정렬 기법
버블 정렬 기술을 사용하여 정렬은 패스 또는 반복으로 수행됩니다. 따라서 각 반복이 끝날 때 가장 무거운 요소가 목록의 적절한 위치에 배치됩니다. 즉, 목록에서 가장 큰 요소가 버블 링됩니다.
우리는 아래에 버블 정렬 기술의 일반적인 알고리즘을 제공했습니다.
일반 알고리즘
1 단계 : i = 0 ~ N-1의 경우 2 단계 반복
2 단계 : J = i + 1 ~ N-반복
3 단계 : A (J)> A (i) 인 경우
A (J)와 A (i) 교체
(내부 for 루프의 끝)
(외부 for 루프 인 경우 종료)
4 단계 : 종료
다음은 두 개의 반복 루프를 사용하여 목록을 순회하는 버블 정렬 알고리즘의 의사 코드입니다.
첫 번째 루프에서는 0부터 시작합니다.일요소와 다음 루프에서 인접한 요소에서 시작합니다. 내부 루프 본문에서 인접한 각 요소를 비교하고 순서가 맞지 않으면 서로 바꿉니다. 외부 루프의 각 반복이 끝날 때 가장 무거운 요소가 끝에서 버블 링됩니다.
의사 코드
Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array(i-1) > array(i) then swap array(i-1) and array(i) swapped = true end if end for until not swapped end procedure위에 주어진 것은 버블 정렬 기술에 대한 의사 코드입니다. 이제 자세한 그림을 사용하여이 기술을 설명하겠습니다.
삽화
크기 5의 배열을 가져 와서 버블 정렬 알고리즘을 설명합니다.
배열이 완전히 정렬되었습니다.
위의 그림은 아래와 같이 표 형식으로 요약 할 수 있습니다.
| 통과하다 | 정렬되지 않은 목록 | 비교 | 정렬 된 목록 |
|---|---|---|---|
| {5,0,10,12,15} | {10.12} | {5,0,10,12,15} | |
| 1 | {10,5,15,0,12} | {10.5} | {5,10,15,0,12} |
| {5,10,15,0,12} | {10.15} | {5,10,15,0,12} | |
| {5,10,15,0,12} | {15.0} | {5,10,0,15,12} | |
| {5,10,0,15,12} | {15.12} | {5,10,0,12,15} | |
| 두 | {5,10,0,12,15} | {5,10} | {5,10,0,12,15} |
| {5,10,0,12,15} | {10.0} | {5,0,10,12,15} | |
| 삼 | {5,0,10,12,15} | {5,0} | {0,5,10,12,15} |
| {5,0,10,12,15} | {5,10} | {5,0,10,12,15} | |
| {5,0,10,12,15} | 분류 됨 |
그림과 같이 모든 패스에서 가장 큰 요소가 마지막까지 버블 링되어 모든 패스로 목록을 정렬합니다. 서론에서 언급했듯이 각 요소는 인접한 요소와 비교되고 순서가 맞지 않으면 서로 교체됩니다.
따라서 위의 그림과 같이 첫 번째 패스가 끝날 때 배열이 오름차순으로 정렬되면 가장 큰 요소가 목록의 끝에 배치됩니다. 두 번째 패스의 경우 두 번째로 큰 요소가 목록의 마지막 두 번째 위치에 배치됩니다.
N-1 (여기서 N은 목록의 총 요소 수)에 도달하면 전체 목록이 정렬됩니다.
C ++ 바이너리 트리 구현
버블 정렬 기술은 모든 프로그래밍 언어로 구현할 수 있습니다. 아래의 C ++ 및 Java 언어를 사용하여 버블 정렬 알고리즘을 구현했습니다.
C ++ 예제
버블 정렬을 보여주는 프로그래밍 예제를 보겠습니다.
#include using namespace std; int main () { int i, j,temp,pass=0; int a(10) = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ...
'; for(i = 0; i<10; i++) { cout < 산출:
입력 목록…
10 2 0 14 43 25 1815 45
정렬 된 요소 목록…
012 5 10 14 18 25 43 45
목록을 정렬하는 데 걸린 패스 수 : 10
자바 예
class Main { public static void main(String() args) { int pass = 0; int() a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a(i) 산출:
두 프로그램 모두 10 개 요소의 배열을 사용했으며 버블 정렬 기술을 사용하여 정렬했습니다. 두 프로그램 모두 배열의 인접한 요소를 반복하기 위해 두 개의 for 루프를 사용했습니다.
각 패스 (외부 루프)의 끝에서 배열의 가장 큰 요소가 배열의 끝까지 버블 링됩니다. 또한 전체 배열을 정렬하는 데 필요한 패스 수를 계산합니다.
Windows 10을위한 최고의 시스템 유지 관리 소프트웨어
버블 정렬 알고리즘의 복잡성 분석
위에서 본 의사 코드와 그림에서 버블 정렬로 첫 번째 패스에서 N-1 비교, 두 번째 패스에서 N-2 비교 등을 수행합니다.
따라서 버블 정렬의 총 비교 수는 다음과 같습니다.
나는 = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-1) / 2
= O (n두) => 버블 정렬 기법의 시간 복잡성
따라서 버블 정렬 기술의 다양한 복잡성은 다음과 같습니다.
최악의 시간 복잡성 O (n 2) 최상의 경우 시간 복잡성 의 위에) 평균 시간 복잡성 O (n 2) 공간 복잡성 O (1)
버블 정렬 기법은 스와핑을 용이하게하기 위해 temp 변수에 대한 추가 메모리 공간 하나만 필요합니다. 따라서 버블 정렬 알고리즘의 공간 복잡도는 O (1)입니다.
버블 정렬 기술의 가장 좋은 경우 시간 복잡도는 목록이 이미 정렬되어 O (n)가 될 때입니다.
결론
버블 정렬의 가장 큰 장점은 알고리즘의 단순성입니다. 버블 정렬에서 배열이 오름차순으로 정렬되면 모든 패스에서 가장 큰 요소가 목록의 끝까지 버블 링됩니다.
마찬가지로 목록을 내림차순으로 정렬하려면 가장 작은 요소가 모든 패스가 끝날 때 적절한 위치에 있습니다.
가장 간단하고 구현하기 쉬운 정렬 기술인 버블 정렬은 일반적으로 청중에게 정렬을 소개하기 위해 사용됩니다. 둘째, 버블 정렬은 컴퓨터 그래픽과 같은 응용 프로그램에서도 사용되며 다각형 가장자리를 채우려면 다각형을 정렬하는 정점을 정렬하기 위해 버블 정렬이 필요합니다.
다음 자습서에서는 선택 정렬에 대해 자세히 알아 봅니다.
=> 처음부터 C ++를 배우려면 여기를 방문하십시오.
추천 도서
