삽입 정렬과 버블 정렬 알고리즘

삽입 정렬과 버블 정렬 알고리즘

---

몇 가지 정렬 알고리즘을 이해하려고 노력하고 있지만 버블 정렬과 삽입 정렬 알고리즘의 차이점을 확인하는 데 어려움을 겪고 있습니다.

나는 둘 다 O (n ² ) 라는 것을 알고 있지만 버블 정렬은 각 패스에 대해 배열의 최대 값을 맨 위로 버블 링하는 반면 삽입 정렬은 각 패스에서 가장 낮은 값을 맨 아래로 싱크합니다. 그들은 똑같은 일을하고 있지만 다른 방향으로하고 있지 않습니까?

삽입 정렬의 경우 비교 / 잠재적 스왑 수는 0에서 시작하여 매번 증가하지만 (예 : 0, 1, 2, 3, 4, ..., n) 버블 정렬의 경우 이와 동일한 동작이 발생하지만 정렬 (즉, n, n-1, n-2, ... 0)은 버블 정렬이 정렬 될 때 마지막 요소와 더 이상 비교할 필요가 없기 때문입니다.

이 모든 것에 대해 일반적으로 삽입 정렬이 더 낫다는 것이 합의 된 것 같습니다. 아무도 이유를 말해 줄 수 있습니까?

편집 : 저는 주로 알고리즘의 효율성이나 점근 적 복잡성이 아니라 알고리즘 작동 방식의 차이점에 관심이 있습니다.

---

ith 반복의 거품 정렬에서는 ni-1 내부 반복 (n ^ 2) / 2 total이 있지만 삽입 정렬에서는 i 번째 단계에서 최대 i 반복이 있지만 내부 루프를 중지 할 수 있으므로 평균적으로 i / 2입니다. 이전에는 현재 요소의 올바른 위치를 찾은 후. 따라서 (0에서 n까지의 합계) / 2는 (n ^ 2) / 4 합계입니다.

이것이 삽입 정렬이 버블 정렬보다 빠른 이유입니다.

---

삽입 정렬

이후 난 첫번째 반복 I를 요소는 정렬된다.

각 반복에서 다음 요소는 올바른 지점에 도달 할 때까지 정렬 된 섹션을 통해 버블 링됩니다 .

sorted  | unsorted
1 3 5 8 | 4 6 7 9 2
1 3 4 5 8 | 6 7 9 2

4는 정렬 된 섹션에 버블 링됩니다.

의사 코드 :

for i in 1 to n
    for j in i downto 2
        if array[j - 1] > array[j]
            swap(array[j - 1], array[j])
        else
            break

버블 정렬

후에 내가 반복 마지막으로 내가 요소가 가장 큰를하고, 명령했다.

각 반복에서 정렬되지 않은 섹션을 선별 하여 최대 값을 찾습니다.

unsorted  | biggest
3 1 5 4 2 | 6 7 8 9
1 3 4 2 | 5 6 7 8 9

5는 정렬되지 않은 섹션에서 버블 링됩니다.

의사 코드 :

for i in 1 to n
    for j in 1 to n - i
         if array[j] > array[j + 1]
             swap(array[j], array[j + 1])

일반적인 구현은 외부 루프의 반복 중 하나 동안 스왑이 수행되지 않으면 조기에 종료됩니다 (배열이 정렬됨을 의미하기 때문).

차

삽입시 정렬 요소는 정렬 된 섹션으로 버블 링되는 반면 버블 정렬에서는 최대 값이 정렬되지 않은 섹션에서 버블 링됩니다.

---

또 다른 차이점은 여기에서 보지 못했습니다.

버블 정렬 에는 스왑 당 3 개의 값 할당 이 있습니다. 방금 값을 저장 한 지점에 다른 스왑 변수를 작성해야하는 것보다 먼저 푸시하고 싶은 값 (1 번)을 저장하기 위해 임시 변수를 만들어야합니다. of (no.2) 그런 다음 다른 자리 (no.3)에 임시 변수를 작성해야합니다. 변수를 올바른 지점으로 정렬하려면 각 지점에 대해이를 수행해야합니다.

삽입 정렬 을 사용하면 변수를 임시 변수에 정렬 한 다음 변수의 올바른 지점에 도달하는 한 모든 변수를 해당 지점 앞에 1 지점 뒤로 놓습니다. 이는 스팟 당 1 개의 값을 할당 합니다. 결국 임시 변수를 그 자리에 씁니다.

이는 가치 할당도 훨씬 적습니다.

이것은 가장 강력한 속도 이점은 아니지만 언급 할 수 있다고 생각합니다.

나는 이해하기를 바란다. 그렇지 않다면 미안하다. 나는 영국 출신이 아니다.

---

버블 정렬은 정렬 된 요소의 전역 최대 값을 실제로 추적하지 않기 때문에 온라인이 아닙니다 (항목 수를 알지 못하면 입력 스트림을 정렬 할 수 없습니다). 항목이 삽입되면 처음부터 버블 링을 시작해야합니다.

---

삽입 정렬의 주요 장점은 온라인 알고리즘이라는 것입니다. 처음에 모든 값을 가질 필요는 없습니다. 이는 네트워크 또는 일부 센서에서 오는 데이터를 처리 할 때 유용 할 수 있습니다.

I have a feeling, that this would be faster than other conventional n log(n) algorithms. Because the complexity would be n*(n log(n)) e.g. reading/storing each value from stream (O(n)) and then sorting all the values (O(n log(n))) resulting in O(n^2 log(n))

On the contrary using Insert Sort needs O(n) for reading values from the stream and O(n) to put the value to the correct place, thus it's O(n^2) only. Other advantage is, that you don't need buffers for storing values, you sort them in the final destination.

---

well bubble sort is better than insertion sort only when someone is looking for top k elements from a large list of number i.e. in bubble sort after k iterations you'll get top k elements. However after k iterations in insertion sort, it only assures that those k elements are sorted.

---

Though both the sorts are O(N^2).The hidden constants are much smaller in Insertion sort.Hidden constants refer to the actual number of primitive operations carried out.

When insertion sort has better running time?

1. Array is nearly sorted-notice that insertion sort does fewer operations in this case, than bubble sort.
2. Array is of relatively small size: insertion sort you move elements around, to put the current element.This is only better than bubble sort if the number of elements is few.

Notice that insertion sort is not always better than bubble sort.To get the best of both worlds, you can use insertion sort if array is of small size, and probably merge sort(or quicksort) for larger arrays.

---

Bubble sort is almost useless under all circumstances. In use cases when insertion sort may have too many swaps, selection sort can be used because it guarantees less than N times of swap. Because selection sort is better than bubble sort, bubble sort has no use cases.

---

insertion sort:

1.In the insertion sort swapping is not required.

2.the time complexity of insertion sort is Ω(n)for best case and O(n^2) worst case.

3.less complex as compared to bubble sort.

4.example: insert books in library, arrange cards.

bubble sort: 1.Swapping required in bubble sort.

2.the time complexity of bubble sort is Ω(n)for best case and O(n^2) worst case.

3.more complex as compared to insertion sort.

---

Number of swap in each iteration

• Insertion-sort does at most 1 swap in each iteration.
• Bubble-sort does 0 to n swaps in each iteration.

Accessing and changing sorted part

• Insertion-sort accesses(and changes when needed) the sorted part to find the correct position of a number in consideration.
• When optimized, Bubble-sort does not access what is already sorted.

Online or not

• Insertion-sort is online. That means Insertion-sort takes one input at a time before it puts in appropriate position. It does not have to compare only adjacent-inputs.
• Bubble-sort is not-online. It does not operate one input at a time. It handles a group of inputs(if not all) in each iteration. Bubble-sort only compare and swap adjacent-inputs in each iteration.

---

Insertion sort can be resumed as "Look for the element which should be at first position(the minimum), make some space by shifting next elements, and put it at first position. Good. Now look at the element which should be at 2nd...." and so on...

Bubble sort operate differently which can be resumed as "As long as I find two adjacent elements which are in the wrong order, I swap them".

참고URL : https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms