Chiarimento del "sort"

[frankus89]

salve, volevo sapere quale fosse la differenza tra il selection sort e il bubble sort.
grazie

[Luc@s]

prestazioni, implementazioni e idee di fondo in realtà...

[frankus89]

in soldoni scusa??

[Luc@s]

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

Class: Sorting algorithm
Data Structure: Array
Time Complexity: О(n²)
Space Complexity: О(n) total, O(1) auxiliary
Optimal: No

--

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.

Class: Sorting algorithm
Data Structure: Array
Time Complexity: О(n²)
Space Complexity: О(n) total, O(1) auxiliary
Optimal: Not usually

[Luc@s]

procedure bubbleSort( A : list of sortable items ) defined as:
  for each i in 1 to length(A) do:
     for each j in length(A) downto i + 1 do:
       if A[ j - 1 ] > A[ j ] then
         swap( A[ j - 1],  A[ j ] )
       end if
     end for
  end for
end procedure

for i ← 0 to n-2 do
    min ← i
    for j ← (i + 1) to n-1 do
        if A[j] < A[min]
            min ← j
    swap A[i] and A[min]

[Umby2]

Su wikipedia Italia, sono presenti entrambe voci:

Per il Bubble: http://it.wikipedia.org/wiki/Bubble_sort

Per il Selection: http://it.wikipedia.org/wiki/Selection_sort