모든 것에 대한인지 적 사실 / 컴퓨터 / 프로그래밍의 정렬 방법 : 버블 정렬

프로그래밍에서 정렬 방법 : 버블 정렬

버블 정렬은 가장 많이 고려되지 않습니다.빠른 방법, 또한 가장 느린 순서 방법 목록을 닫습니다. 그러나 장점도 있습니다. 따라서 특정 순서로 요소를 정렬해야하는 경우 버블 방법으로 정렬하는 것이 문제에 대한 가장 논리적이고 자연스러운 해결책입니다. 예를 들어 평범한 사람은 직관에 따라 수동으로 사용할 것입니다.

이 특이한 이름은 어디에서 왔습니까?

방법의 이름은 다음과 같은 비유를 사용하여 발명되었습니다.물 속에서 기포. 이것은 은유입니다. 작은 기포가 위로 올라가는 것처럼-결국 그 밀도는 어떤 액체 (이 경우 물)보다 크므로 배열의 각 요소 값이 작을수록 점차 시작으로 향합니다. 숫자 목록의.

알고리즘 설명

버블 정렬은 다음과 같이 수행됩니다.

첫 번째 패스 : 숫자 배열의 요소를 2로 가져와 쌍으로 비교합니다. 일부 두 요소에서 첫 번째 값이 두 번째 값보다 큰 것으로 판명되면 프로그램은 해당 위치를 교환합니다.
따라서 가장 큰 수는 배열의 끝에 끝납니다. 다른 모든 요소는 그대로 혼란스러운 순서로 남아 있으며 정렬이 필요합니다.
따라서 두 번째 패스가 필요합니다. 이전 패스 (이미 설명)와 유추하여 이루어지며 비교 횟수-1을 뺀 것입니다.
통과 번호 3은 두 번째보다 비교 횟수가 하나 적고 첫 번째 것보다 두 번 적습니다. 기타;
요약하면 각 패스에는 (배열의 총 값, 특정 숫자) 마이너스 (통과 숫자) 비교가 있습니다.

더 짧게, 미래 프로그램의 알고리즘은 다음과 같이 작성할 수 있습니다.

숫자 배열은 두 개의 숫자가 발견 될 때까지 검사되며 두 번째 숫자는 첫 번째 숫자보다 커야합니다.
프로그램은 서로에 대해 잘못 배치 된 배열의 요소를 교환합니다.

설명 된 알고리즘을 기반으로하는 의사 코드

가장 간단한 구현은 다음과 같습니다.

절차 Sortirovka_Puzirkom;

처음에는

사이클 제이 ...에서 nachalnii_index 전에 konechii_index;

사이클 나는 ...에서 nachalnii_index 전에 konechii_index-1;

만약 massiv [i]> massiv [i + 1] (첫 번째 요소가 두 번째 요소보다 큼) 그러면 :

(장소에서 값을 변경하십시오);

끝

물론 여기서 단순함은상황 : 알고리즘이 단순할수록 모든 단점이 더 많이 나타납니다. 작은 배열의 경우에도 시간 비용이 너무 높습니다 (여기서 상대성이 작용합니다. 평신도에게는 시간이 작게 보일 수 있지만 프로그래머의 비즈니스에서는 매초 또는 밀리 초가 중요합니다).

더 나은 구현이 필요했습니다. 예를 들어, 배열의 값을 장소별로 교환하는 것을 고려하십시오.

절차 Sortirovka_Puzirkom;

처음에는

Sortirovka = 참;

싸이클 바이 Sortirovka = 참;

Sortirovka = 거짓;

사이클 나는 ...에서 nachalnii_index 전에 konechii_index-1;

만약 massiv [i]> massiv [i + 1] (첫 번째 요소가 두 번째 요소보다 큼) 그러면 :

(우리는 장소에서 요소를 바꿉니다).

Sortirovka = 참; (교환이 이루어 졌다는 것을 나타냄).

끝.

방법의 단점

가장 큰 단점은 프로세스 기간입니다. 버블 정렬 알고리즘은 얼마나 걸립니까?

실행 시간은 배열에있는 숫자 수의 제곱으로 계산되며 최종 결과는 이에 비례합니다.

최악의 경우 배열이 순회됩니다.하나의 값을 뺀 요소 수만큼 결국 비교할 것이없는 요소가 하나만 남아 있고 배열을 통한 마지막 패스는 쓸모없는 작업이되기 때문입니다.

게다가, 간단한 분류 방법교환은 작은 배열에만 해당됩니다. 그것의 도움으로 많은 양의 데이터를 처리하는 것은 불가능합니다. 결과는 오류 또는 프로그램의 실패입니다.

장점

버블 정렬은 이해하기 매우 쉽습니다.기술 대학의 커리큘럼에서 배열 요소의 순서를 공부할 때 먼저 통과합니다. 이 방법은 Delphi 프로그래밍 언어 (D (Delphi))와 C / C ++ (C / C plus plus), 정확한 순서로 값을 배열하는 믿을 수 없을 정도로 간단한 알고리즘과 Pascal 모두에서 쉽게 구현됩니다. 정렬은 초보자에게 이상적입니다.

단점으로 인해 알고리즘은 과외 목적으로 사용되지 않습니다.