정렬 알고리즘 효율/성능

Question

저는 프로그래밍 초보자이며 정렬 작업 만하고이 알고리즘을 만들었습니다. 그것은 버블과 비슷하지만 인접한 쌍이 아니라 쌍을 비교합니다 : 첫 번째와 두 번째, 첫 번째와 세 번째 ... 두 번째와 세 번째, 두 번째와 네 번째 등등. 알고리즘의 성능/효율성이 무엇인지 나 거품과 비교해 보시겠습니까? 또는 적어도 문제를 직접 해결하는 방법에 대한 조언. 나는이 거품보다 얼마나 거품이 더 좋은지에 관심이 있습니다. 고맙습니다. 그 첫 번째 N 개 요소들이 올바른 위치에 외부 루프의 n 번째 반복에 말할 때

void sortArray(int a[]) { 

int q, x, temp; 

for (q = 0; q < SIZE - 1; q++) { 
    for (x = q + 1; x < SIZE; x++) { 
     if (a[q] < a[x]) { 
      temp = a[q]; 
      a[q] = a[x]; 
      a[x] = temp; 
     } 
    } 
} 

}

Answer 1

귀하의 정렬 방식은 기존 버블 정렬과 유사하며 기본적으로 동일한 성능을 가져야합니다.

정렬 및 거품 정렬 모두 선택 정렬의 비효율적 인 버전으로 볼 수 있습니다. 세 알고리즘 모두에 대해 내부 루프의 각 패스는 배열의 정렬되지 않은 영역을 반복하고, 가장 작은/가장 큰 요소를 찾아 최종 위치에 남겨 둡니다. 알고리즘은 정렬되지 않은 영역에서 다른 순열을 수행하기 때문에 동일하지 않지만이 차이는 알고리즘의 작동에 기능적으로 기여하지 않습니다.

일단 이것을 인식하면 왜 선택 정렬이 다른 두 가지보다 일정한 이점을 갖는 경향이 있는지 쉽게 알 수 있습니다. 내부 루프의 각 패스는 필요한 최소 스왑 횟수를 수행합니다 (예 : 종료). 반대로 거품 정렬과 정렬은 반복 당 반복 당 하나의 스왑을 수행 할 수 있습니다 ...

점근 적으로 그래도 세 가지 유형 모두 O (N^2) 시간이 걸릴 것입니다. 구체적으로 말하자면, 내부 루프의 반복이 N*(N-1)/2입니다.

Answer 2

@Kevin 맞다. 기존 버블 정렬 (인접 요소를 비교하고 바꾼다)도이 작업을 수행하지만 목록에있는 다른 항목도 부분적으로 정렬하므로 모든 반복 작업이 완료되기 전에 목록이 정렬 될 가능성이 높아집니다. 정렬이 완료 될 수있는 외부 루프 반복 중에 스왑이 감지되지 않습니다).

Answer 3

간단한 답변 - 버블 정렬과 마찬가지로 알고리즘의 복잡도는 O (n)입니다. 즉 두 알고리즘의 복잡성은 본질적으로 같습니다.