sorting => 선택

비고

컴퓨터 과학에서 선택 정렬은 정렬 알고리즘, 특히 내부 비교 정렬입니다. 그것은 O (n ² ) 시간의 복잡성을 가지고있어서 큰리스트에서는 비효율적이며, 일반적으로 유사한 삽입 정렬보다 나쁩니다. 선택 정렬은 단순성으로 유명하며 특정 상황에서 특히 보조 메모리가 제한적인 경우보다 복잡한 알고리즘보다 성능 이점이 있습니다.

아래 이미지는 선택 정렬이 어떻게 작동하는지 보여줍니다.

의사 코드 아래에서는 (모든 언어로) 프로그램을 만들거나 선택 정렬을 이해하는 데 도움이됩니다.

procedure selection sort 
list  : array of items
n     : size of list

for i = 1 to n - 1
/* set current element as minimum*/
  min = i    

  /* check the element to be minimum */

  for j = i+1 to n 
     if list[j] < list[min] then
        min = j;
     end if
  end for

  /* swap the minimum element with the current element*/
  if indexMin != i  then
     swap list[min] and list[i]
  end if

end for

end procedure

장점 :

이해 하기엔 너무 간단하다.
작은 목록에서 잘 수행됩니다.
원래 목록을 보유하는 데 필요한 것 이상의 추가 임시 저장 장치가 필요하지 않습니다.

심상 참고 : RMIT 대학

선택 정렬 (Python)

선택 정렬 작동 방식을 보여주는 애니메이션

아래 예제는 파이썬에서 선택 정렬을 보여줍니다.

def sort_selection(my_list):

for pos_upper in xrange( len(my_list)-1, 0, -1):
    max_pos = 0
    for i in xrange(1, pos_upper + 1):
        if(my_list[i] > my_list[max_pos]):
            max_pos = i
            print "resetting max_pos = " + str(max_pos)

    my_list[pos_upper], my_list[max_pos] = my_list[max_pos], my_list[pos_upper]
    print "pos_upper: " + str(pos_upper) + " max_pos: " + str(max_pos) + " my_list: " + str(my_list)

return my_list


if __name__ == "__main__":

    my_list = [54,26,93,17,77,31,44,55,20]
    print "my_list: " + str(my_list)
    print sort_selection(my_list)

프로그램 출력 :

my_list: [54, 26, 93, 17, 77, 31, 44, 55, 20]
resetting max_pos = 2
pos_upper: 8 max_pos: 2 my_list: [54, 26, 20, 17, 77, 31, 44, 55, 93]
resetting max_pos = 4
pos_upper: 7 max_pos: 4 my_list: [54, 26, 20, 17, 55, 31, 44, 77, 93]
resetting max_pos = 4
pos_upper: 6 max_pos: 4 my_list: [54, 26, 20, 17, 44, 31, 55, 77, 93]
pos_upper: 5 max_pos: 0 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
resetting max_pos = 4
pos_upper: 4 max_pos: 4 my_list: [31, 26, 20, 17, 44, 54, 55, 77, 93]
pos_upper: 3 max_pos: 0 my_list: [17, 26, 20, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 2 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
resetting max_pos = 1
pos_upper: 1 max_pos: 1 my_list: [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

이미지 참조 : 해적 학습자

선택 정렬 (Java)

선택 정렬 작동 방식을 보여주는 애니메이션

아래 예제에서는 선택 정렬을 오름차순으로 보여줍니다.

public class MySelectionSort {
 
    public static int[] doSelectionSort(int[] arr){
         
        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++)
                if (arr[j] < arr[index]) 
                    index = j;
      
            int smallerNumber = arr[index];  
            arr[index] = arr[i];
            arr[i] = smallerNumber;
        }
        return arr;
    }

선택 정렬 결과를 보여주기 위해 샘플 main() 메서드를 작성했습니다.

    public static void main(String a[]){
         
        int[] arr1 = {10,34,2,56,7,67,88,42};
        int[] arr2 = doSelectionSort(arr1);
        for(int i:arr2){
            System.out.print(i);
            System.out.print(", ");
        }
    }
}

프로그램 출력 :

2, 7, 10, 34, 42, 56, 67, 88

아래 예제에서는 내림차순으로 선택 정렬을 보여줍니다.

public static void doDescendingSelectionSort ( int [ ] num )
{
     int i, j, first, temp;  
     for ( i = num.length - 1; i > 0; i - - )  
     {
          first = 0;   //initialize to subscript of first element
          for(j = 1; j <= i; j ++)   //locate smallest element between positions 1 and i.
          {
               if( num[ j ] < num[ first ] )         
                 first = j;
          }
          temp = num[ first ];   //swap smallest found with element in position i.
          num[ first ] = num[ i ];
          num[ i ] = temp; 
      }           
}

이미지 참조 : Wikipedia

Modified text is an extract of the original Stack Overflow Documentation

아래 라이선스 CC BY-SA 3.0

와 제휴하지 않음 Stack Overflow

sorting
선택

수색…

비고

선택 정렬 (Python)

선택 정렬 (Java)