[Sorting] Selection Sort 선택정렬

The basic idea is as follows:

1. Select successive elements in ascending order and place them into their proper position.
2. Find the smallest element from the array, and exchange it with the first element.
   Find the second smallest element, and exchange it with the second element;
   and so on.
3. Repeat these procedures until the data is sorted in the proper order.

 

# Example

array = { 170, 45, 75, 90, 802, 24, 2, 66 };

1. Smallest value 2:
   170 ↔ 2 { 2, 45, 75, 90, 802, 24, 170, 66 }
2. Smallest value 24:
   45 ↔ 24 { 2, 24, 75, 90, 802, 45, 170, 66 }
3. Smallest value 45:
   75 ↔ 45 { 2, 24, 45, 90, 802, 75, 170, 66 }
4. Smallest value 66:
   90 ↔ 66 { 2, 24, 45, 66, 802, 75, 170, 90 }
5. Smallest value 75:
   802 ↔ 75 { 2, 24, 45, 66, 75, 802, 170, 90 }
6. Smallest value 90:
   802 ↔ 90 { 2, 24, 45, 66, 75, 90, 170, 802 }
7. Smallest value 170:
   170 ↔ 170 { 2, 24, 45, 66, 75, 90, 170, 802 }
8. Smallest value 802:
   802 ↔ 802 { 2, 24, 45, 66, 75, 90, 170, 802 }

result = { 2, 24, 45, 66, 75, 90, 170, 802 };

 

 

# Pseudocode

arr: array
min: index of minimum value (target)
tmp: temp value

test()
	for i is 0 to arr.size() - 1 do:
    	min := i        
        for j is i + 1 to arr.size() - 1 do:
        	if arr[j] is less than arr[min]
            	min := j
         end for
         
         tmp := arr[min]
         arr[min] := arr[i]
         arr[i] := tmp
         
    end for    
end

 

# Computation in C

 

 

# Time Complexity

• Worst complexity: O(n²)
• Average complexity: O(n²)
• Best complexity: O(n²)

# Space complexity

• O(1)