삽입 정렬과 선택 정렬

삽입 정렬과 선택 정렬

---

삽입 정렬과 선택 정렬의 차이점을 이해하려고합니다.

둘 다 두 가지 구성 요소 인 정렬되지 않은 목록과 정렬 된 목록이있는 것 같습니다. 둘 다 정렬되지 않은 목록에서 하나의 요소를 가져와 적절한 위치에 정렬 된 목록에 넣는 것 같습니다. 삽입 정렬은 단순히 올바른 지점을 찾아서 삽입하는 동안 선택 정렬이 한 번에 하나씩 교체하여이 작업을 수행한다고 말하는 사이트 / 책을 보았습니다. 그러나 다른 기사에서 삽입 정렬도 바뀐다 고 말하는 것을 보았습니다. 결과적으로 나는 혼란 스럽습니다. 표준 소스가 있습니까?

---

선택 정렬 :

목록이 주어지면 현재 요소를 가져 와서 현재 요소의 오른쪽에있는 가장 작은 요소로 교환합니다.

삽입 정렬 :

목록이 주어지면 현재 요소를 목록의 적절한 위치에 삽입하고 삽입 할 때마다 목록을 조정합니다. 카드 게임에서 카드를 배열하는 것과 비슷합니다.

선택 정렬의 시간 복잡도는 항상있는 n(n - 1)/2반면 삽입 정렬은 최악의 경우 복잡도이므로 시간 복잡도가 더 좋습니다 n(n - 1)/2. 일반적으로 그보다 적거나 같은 비교가 필요 n(n - 1)/2합니다.

출처 : http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

---

삽입 정렬과 선택 정렬에는 모두 외부 루프 (모든 인덱스에 대해)와 내부 루프 (인덱스 하위 집합에 대해)가 있습니다. 내부 루프의 각 패스는 정렬되지 않은 요소가 부족해질 때까지 정렬되지 않은 영역을 희생하여 정렬 된 영역을 하나의 요소로 확장합니다.

차이점은 내부 루프가 수행하는 작업입니다.

• 선택 정렬에서 내부 루프는 정렬되지 않은 요소 위에 있습니다. 각 패스는 하나의 요소를 선택하고 최종 위치 (정렬 된 영역의 현재 끝)로 이동합니다.

• 삽입 정렬에서 내부 루프의 각 패스는 정렬 된 요소를 반복 합니다. 정렬 된 요소는 루프가 다음 정렬되지 않은 요소를 삽입 할 올바른 위치를 찾을 때까지 대체됩니다.

따라서 선택 정렬에서 정렬 된 요소는 출력 순서로 발견되고 발견되면 그대로 유지됩니다. 반대로, 삽입 정렬에서 정렬되지 않은 요소는 입력 순서대로 소비 될 때까지 그대로 유지되고 정렬 된 영역의 요소는 계속 이동합니다.

스와핑에 관한 한 : 선택 정렬은 내부 루프의 패스 당 하나의 스왑을 수행합니다. 삽입 정렬은 일반적으로 내부 루프 temp 이전 과 같이 삽입 할 요소를 저장하여 내부 루프가 정렬 된 요소를 하나씩 위로 이동 한 다음 temp나중에 삽입 지점으로 복사 할 공간을 남겨 둡니다 .

---

연결 목록 정렬에 대한 설명을 배열 정렬에 대한 설명과 비교하기 때문에 혼란이있을 수 있습니다 . 그러나 나는 당신이 당신의 출처를 인용하지 않았기 때문에 확신 할 수 없습니다.

정렬 알고리즘을 이해하는 가장 쉬운 방법은 종종 알고리즘에 대한 자세한 설명을 얻는 것입니다 ( "이 종류는 스왑을 사용합니다. 어딘가에 있습니다. 나는 어디를 말하는 것이 아닙니다"와 같은 모호하지 않음). 간단한 정렬 알고리즘의 경우), 알고리즘을 직접 실행하십시오.

선택 정렬 : 정렬되지 않은 데이터를 검색하여 남은 가장 작은 요소를 찾은 다음 정렬 된 데이터 바로 다음 위치로 교체합니다. 끝날 때까지 반복하십시오. 목록을 정렬하는 경우 가장 작은 요소를 위치로 바꿀 필요가 없습니다. 대신 목록 노드를 이전 위치에서 제거하고 새 위치에 삽입 할 수 있습니다.

삽입 정렬 : 정렬 된 데이터 바로 뒤에있는 요소를 가져와 정렬 된 데이터를 스캔하여 배치 할 위치를 찾아 거기에 배치합니다. 끝날 때까지 반복하십시오.

삽입 정렬 은 "스캔"단계에서 스왑 을 사용할 수 있지만 반드시 그럴 필요는 없으며 다음과 같은 데이터 유형의 배열을 정렬하지 않는 한 가장 효율적인 방법이 아닙니다. (a) 이동할 수없고 복사 또는 스왑 만 가능합니다. (b) 스왑보다 복사하는 데 더 비쌉니다. 삽입 정렬을 사용 스왑을 수행하는 경우가 작동하는 방식은 동시에 장소를 검색한다는 것입니다 및 긴 요소로는보다 큰 전과를 들어, 반복적으로 직전 요소와 새로운 요소를 교환하여, 거기에 새로운 요소를 넣어 그것. 더 크지 않은 요소에 도달하면 올바른 위치를 찾은 다음 다음 새 요소로 이동합니다.

---

SELECTION SORT
특정 / 무작위 방식으로 쓰여진 숫자 배열이 있다고 가정하고 오름차순으로 배열한다고 가정합시다. 따라서 한 번에 하나의 숫자를 가져 와서 가장 작은 숫자로 대체하십시오. 목록에서 사용할 수 있습니다. 이 단계를 수행하면 궁극적으로 원하는 결과를 얻을 수 있습니다.

INSERTION SORT
비슷한 가정을 염두에두고 있지만 유일한 차이점은 이번에는 한 번에 하나의 숫자를 선택하고 미리 정렬 된 부분에 삽입하므로 비교가 줄어들어 더 효율적이라는 것입니다.

---

두 알고리즘의 논리는 매우 유사합니다. 둘 다 배열의 시작 부분에 부분적으로 정렬 된 하위 배열이 있습니다. 유일한 차이점은 정렬 된 배열에 넣을 다음 요소를 검색하는 방법입니다.

• Insertion sort: inserts the next element at the correct position;

• Selection sort: selects the smallest element and exchange it with the current item;

Also, Insertion Sort is stable, as opposed to Selection Sort.

I implemented both in python, and it's worth noting how similar they are:

def insertion(data):
    data_size = len(data)
    current = 1
    while current < data_size:
        for i in range(current):
            if data[current] < data[i]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

With a small change it is possible to make the Selection Sort algorithm.

def selection(data):
    data_size = len(data)
    current = 0
    while current < data_size:
        for i in range(current, data_size):
            if data[i] < data[current]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

---

In a nutshell, I think that the selection sort searches for the smallest value in the array first, and then does the swap whereas the insertion sort takes a value and compares it to each value left to it (behind it). If the value is smaller, it swaps. Then, the same value is compared again and if it is smaller to the one behind it, it swaps again. I hope that makes sense!

---

In short,

Selection sort : Select the first element from unsorted array and compare it with remaining unsorted elements. It is similar to Bubble sort, but instead of swapping each smaller elements, keeps the smallest element index updated and swap it at the end of each loop.

Insertion sort : It is opposite to Selection sort where it picks first element from unsorted sub-array and compare it with sorted sub-array and insert the smallest element where found and shift all the sorted elements from its right to the first unsorted element.

---

I'll give it yet another try: consider what happens in the lucky case of almost sorted array.

While sorting, the array can be thought of as having two parts: left hand side - sorted, right hand side - unsorted.

Insertion sort - pick first unsorted element and try to find a place for it among the already sorted part. Since you search from right to left it might very well happen that the first sorted element you are comparing to (the largest one, most right in the left part) is smaller than the picked element so you can immediately continue with the next unsorted element.

Selection sort - pick the first unsorted element and try to find the smallest element of the whole unsorted part, and exchange those two if desirable. The problem is, since the right part is unsorted, you have to go thought every element every time, since you cannot possibly be sure whether there is or is not even smaller element than the picked one.

Btw., this is exactly what heapsort improves upon selection sort - it is able to find the smallest element much more quickly because of the heap.

---

Selection Sort: As you start building the sorted sublist, the algorithm ensures that the sorted sublist is always completely sorted, not only in terms of it's own elements but also in terms of the complete array i.e. both sorted and unsorted sublist. Thus the new smallest element once found from the unsorted sublist would just be appended at the end of the sorted sublist.

Insertion Sort: The algorithm again divide the array into two part, but here the element is picked from second part and inserted at correct position to the first part. This never guarantees that the first part is sorted in terms of the complete array, though ofcourse in the final pass every element is at its correct sorted position.

---

Both algorithms generally works like this

Step 1: take the next unsorted element from the unsorted list then

Step 2: put it in the right place in the sorted list.

One of the steps is easier for one algorithm and vice versa.

Insertion sort: We take the first element of the unsorted list, put it in the sorted list, somewhere. We know where to take the next element (the first position in the unsorted list), but it requires some work to find where to put it (somewhere). Step 1 is easy.

Selection sort: We take the element somewhere from the unsorted list, then put it in the last position of the sorted list. We need to find the next element (it most likely is not in the first position of the unsorted list, but rather, somewhere) then put it right at the end of the sorted list. Step 2 is easy

---

The inner loop of the insertion sort goes through already sorted elements (contrary to the selection sort). This allows it to abort the inner loop when the right position is found. Which means, that:

1. The inner loop will go through only half of its elements in an average case.
2. The inner loop will be aborted even sooner if the array is almost sorted.
3. The inner loop will abort immediately if the array is already sorted, making the complexity of the insertion sort linear in this case.

The selection sort will have to always go through all inner loop elements. That’s why the insertion sort is mostly preferred to the selection sort. But, on the other hand, the selection sort does much less element swaps, which might be more important in some cases.

---

Basically insertion sort works by comparing two elements at a time and selection sort selects the minimum element from the whole array and sorts it.

Conceptually insertion sort keeps on sorting the sub list by comparing two elements till the whole array is sorted while the selection sort selects the minimum element and swaps it to the first position second minimum element to the second position and so on.

Insertion sort can be shown as :

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

Selection sort can be shown as :

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;

---

A simple explanation could be as below:

Given: An unsorted array or list of numbers.

Problem Statement: To sort the list/array of numbers in ascending order to understand the difference between Selection Sort and Insertion Sort.

Insertion Sort: You see the list from top to bottom for easier understanding. We consider the first element as our initial minimum value. Now, the idea is that we traverse across each index of that list/array linearly to find out if there is any other element at any index that is having a lesser value than the initial minimum value. If we find such a value, we just swap the values at their indexes, i.e. lets say 15 was the minimum initial value at index 1 and during linear traversal of the indexes, we come across a number with lesser value, say 7 at index 9. Now, this value 7 at index 9 is swapped with the index 1 having 15 as its value. This traversal will continue to do comparison with the value of the current index with the remaining indexes to swap for the smaller value. This continues till the second last index of the list/array, as the last index is already sorted and doesn't have a value to check with outside the array/list.

Selection Sort: Let's assume that the first index element of the list/array is sorted. Now from the element at second index, we compare it with its previous index to see if the value is smaller. The traversal could be visualized into two parts, sorted and unsorted. One would be visualizing a comparison check from the unsorted towards the sorted for a given index in the list/array. Let's say you have value 19 at index 1 and value 10 at index 3. We consider traversal from the unsorted to the sorted, i.e. right to left. So, lets say we have to sort at index 3. We see that it has a lesser value than index 1 when we compared from right to left. Once identified, we just place this number 10 of index 3 in the place of index 1 having value 19. The original value 19 at index 1 gets shifted by one place to the right. This traversal keeps on continuing for every element in the list/array till the last element.

I haven't added any code as the question seems about understanding the concept of the method of traversal.

---

Insertion sort do not swap things. Even though it make use of a temp variable, The point of making use of temp var is when we found a value at an index to be less compared to the value to its previous index, we shift the greater value to the place of lesser value's index which would over write things. Then we use the temp var to be substituted at the previous index. Example: 10, 20, 30, 50, 40. iteration 1: 10, 20, 30, 50, 50. [temp = 40] iteration 2: 10,20, 30, 40(temp's value), 50. So, we just insert a value at the desired position from some variable.

But When we consider selection sort, We first find the index having lower value and swap that value with the value from first index and keep on repeatedly swapping till all the indices get sorted. This is exactly same as traditional swapping of two numbers. Example: 30, 20 ,10, 40, 50. Iteration 1: 10, 20, 30, 40, 50. Here temp var is used exclusively for swapping.

---

Insertion sort does a lot more swapping that selection. Here is an example:

---

In layman terms, (and probably the easiest way to attain a high level understanding of the problem)

Bubble sort is similar to standing in a line and trying to sort yourselves by height. You keep switching with the person next to you until you are at the right place. This takes place all the way from the left (or right depending on the implementation) and you keep switching until everybody is sorted.

그러나 선택 정렬에서 수행하는 작업은 카드 한 장을 정렬하는 것과 유사합니다. 카드를보고 가장 작은 카드를 가져 와서 왼쪽 끝까지 놓는 식으로 계속합니다.

---

선택-특정 항목 (가장 낮은 항목)을 선택하고 i (반복 없음) 번째 요소로 교체합니다. (즉, 첫 번째, 두 번째, 세 번째 .......) 따라서 정렬 된 목록을 한쪽에 만듭니다.

삽입-첫 번째와 두 번째 비교 세 번째와 두 번째 및 첫 번째 비교 네 번째와 세 번째, 두 번째 및 첫 번째 비교 ...

모든 정렬이 비교되는 링크

참고 URL : https://stackoverflow.com/questions/15799034/insertion-sort-vs-selection-sort