[알고리즘] 선택 정렬

오늘은 선택 정렬에 대해 알아보려고 한다.
선택 정렬은 배열의 가장 작은 숫자를 선택하여, 정렬이 되지 않은 배열의 가장 왼쪽 원소와 교환하는 작업을 반복하여 정렬하는 방법이다.

1. 정렬이 되지 않은 배열에서 가장 작은 수를 선택한다.
   [70, 31, 3, 72, 20]

   index = 0
   for j in range(len(data)):
       if data[index] > data[j] :
           index = j

2. 가장 작은 수로 선택 된 원소와 정렬되지 않은 배열의 가장 왼쪽 원소를 교환한다.
   [70, 31, 3, 72, 20] --> [ 3, 31, 70, 72, 20]

   index = 0
   for j in range(len(data)):
       if data[index] > data[j] :
           index = j
   data[0], data[index] = data[index], data[0]

3. 위의 1번 2번 과정을 정렬이 될 때까지 반복한다.
   [70, 31, 3, 72, 20] --> [ 3, 31, 70, 72, 20]

   [ 3, 31, 70, 72, 20] --> [ 3, 20, 70, 72, 31]

   [ 3, 20, 70, 72, 31] --> [ 3, 20, 31, 72, 70]

   [ 3, 20, 31, 72, 70] --> [ 3, 20, 31, 70, 72]

   def select(data):
       for i in range(len(data)-1):
           index = i
           for j in range(i+1, len(data)):
               if data[index] > data[j]:
                   index = j
           if i != index:
               data[i], data[index] = data[index], data[i]
       return data