선택 정렬 selectionsort with swift

선택 정렬은 가장 작은 값을 찾아서 앞으로 보내주는 정렬입니다.

 

첫 번째 원소를 두 번째 원소부터 마지막 원소까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고,

두 번째 원소를 세 번째 원소부터 마지막 원소와 차례대로 비교하여 그중 가장 작은 값을 찾아 두번째 위치에 놓는 과정을 반복합니다.

+ 선택정렬을 코드로 작성할 때는 가장 작은 값을 찾기 위한 min값이 있어야합니다.

 

코드를 살펴봅시다.

 

selectionsort with swift

arr는 우리가 정렬해야 할 배열이며, 1부터 7까지 정렬되지 않은 상태로 존재합니다.

arr의 크기는 7이고 인덱스는 0부터 6까지 입니다.

(external for loop) 외부에 있는 for 루프는 최솟값이 놓일 인덱스를 위해 사용합니다.

(internal for loop) 내부에 있는 for 루프는 최솟값이 놓일 인덱스를 제외한 범위에서 최솟값을 찾기 위해 사용합니다.

min은 최솟값의 인덱스를 나타내는 변수로 사용됩니다.

 

그럼 어떻게 실행되는지 차근차근 살펴봅시다.

 

external for loop로 x는 0으로 고정되어 있으며 internal for loop를 돌면서 a[y] a[min]을 비교해줍니다.

여기서 internal for loop의 범위는 1부터 6까지 입니다. (초록색 박스 친 범위라고 생각하시면 됩니다.)

 

internal for loop에서 y가 1일 때 a[1]는 1이고, a[0]은 4이니 min값이 1로 변경됩니다.

그 이후로는 인덱스 1보다 작은 값을 찾지 못하고 internal for loop를 다 실행하면 x = 0, min = 1 입니다.

 

x와 min이 다를 경우 swap을 해줍니다. 

여기까지 첫 번째 external for loop를 돈 모습입니다.

 

이제 두 번째 external for loop를 돌려봅시다.

 

external for loop로 x는 1로 고정되어 있으며 internal for loop를 돌면서 a[y] a[min]을 비교해줍니다.

여기서 internal for loop의 범위는 2부터 6까지 입니다. (초록색 박스 친 범위라고 생각하시면 됩니다.)

 

쭉 돌면서 y가 3일 때 a[3]는 3이고, a[1]은 4이니 min값이 3으로 변경됩니다.

또 돌면서 y가 5일 때 a[5]는 2고, a[3]은 3이니 min값이 5로 변경됩니다.

그 이후로는 인덱스 5보다 작은 값을 찾지 못하고 internal for loop를 다 실행하면 x = 1, min = 5 입니다.

 

x와 min이 다를 경우 swap을 해줍니다. 

여기까지 두 번째 external for loop를 돈 모습입니다.

 

이제 두 번째 external for loop를 돌려봅시다.

external for loop로 x는 2로 고정되어 있으며 internal for loop를 돌면서 a[y] a[min]을 비교해줍니다.

여기서 internal for loop의 범위는 3부터 6까지 입니다. (초록색 박스 친 범위라고 생각하시면 됩니다.)

 

쭉 돌면서 y가 3일 때 a[3]는 3이고, a[2]은 5이니 min값이 3으로 변경됩니다.

그 이후로는 인덱스 3보다 작은 값을 찾지 못하고 internal for loop를 다 실행하면 x = 2, min = 3 입니다.

 

x와 min이 다를 경우 swap을 해줍니다. 

여기까지 세 번째 external for loop를 돈 모습입니다.

 

이제 네 번째 external for loop를 돌려봅시다.

위와 동일한 작업을 해줍니다.

internal for loop를 다 실행하면 x = 3, min = 5 입니다.

x와 min이 다르니 swap을 시켜줍니다.

위와 동일한 작업을 해줍니다.

internal for loop를 다 실행하면 x = 5, min = 5 입니다.

x와 min이 변경되지 않았으니, swap을 시켜줄 필요가 없습니다.

 

즉 한 번의 external for loop를 실행하면 최솟값을 찾아서 앞으로 보내줍니다.

위 이미지는 external for loop돌 때 array의 변화를 나타낸 것입니다.

external for loop를 한 번 돌 때마다 최솟값이 밑에서부터 변경되는 게 보이시나요.

 

'가장 작은 값을 찾아서 앞으로 보내준다' 이것이 selectionsort의 핵심입니다. 

 

간단한 정렬 알고리즘이지만, 시간 복잡도는 O(n^2)입니다.