(Python) 2차 정렬

2차 정렬

버블 방식(버블 정렬) 또는 단순 교환으로 정렬).

장르의 불멸의 고전. 동작 원리는 간단합니다. 배열을 처음부터 끝까지 이동하면서 정렬되지 않은 인접 요소를 동시에 교환합니다. 꼴찌까지 첫 패스 결과 "팝업" 최대 요소. 이제 배열의 정렬되지 않은 부분(첫 번째 요소에서 두 번째 요소까지)을 다시 우회하고 그 과정에서 정렬되지 않은 이웃을 변경합니다. 두 번째로 큰 요소는 끝에서 두 번째 위치에 있습니다. 같은 정신으로 계속해서 배열의 계속 감소하는 정렬되지 않은 부분을 우회하여 발견된 최대값을 끝까지 밀어냅니다.
 

정렬 삽입

정렬 삽입 – 이것은 매우 간단하지만 비효율적인 알고리즘이지만 일반적으로 더 효율적인 다른 많은 알고리즘이 개발된 후에도 관련성이 있는 몇 가지 특정 이점이 있습니다.

삽입 정렬을 사용하면 정렬하기 전에 전체 배열을 앞에 둘 필요가 없습니다. 알고리즘은 정렬하는 동안 한 번에 하나의 요소를 받을 수 있습니다. 이것은 정렬 중에 더 많은 요소를 추가해야 하는 경우 매우 편리합니다. 알고리즘은 "재실행" 없이 올바른 위치에 새 요소를 삽입합니다. 전체 배열 정렬.

삽입 정렬은 작은(~10개 요소) 데이터세트에 대한 효율성으로 인해 실제로 사용할 수 있습니다.

문제는 다음과 같습니다. 이미 정렬된 배열의 일부가 있고 순서를 유지하면서 배열의 나머지 요소를 정렬된 부분에 삽입하려고 합니다. 이를 위해 알고리즘의 각 단계에서 입력 데이터 요소 중 하나를 선택하고 전체 입력 데이터 세트가 정렬될 때까지 이미 정렬된 배열 부분의 원하는 위치에 삽입합니다. 입력 배열에서 다음 요소를 선택하는 방법은 임의적이지만 일반적으로(그리고 안정적인 정렬 알고리즘을 얻기 위해) 요소는 입력 배열에 나타나는 순서대로 삽입됩니다.

이 알고리즘의 알고리즘 구현

<예비> // null 요소는 이미 정렬된 시퀀스로 간주됩니다. // 따라서 루프는 1부터 시작합니다. I=1에서 N-1까지의 루프 1단계 X=A[I] 지=나 WHEN J>0 AND A[J-1]>X //삽입할 곳을 찾는 중 교환 A[J],A[J-1] J=J-1 END BYE A[J]=엑스 다음 나 계산 복잡성: \(\displaystyle O(n^{2})\).