선택 정렬 - DS 튜토리얼

이번 포스팅에서는 선택정렬 알고리즘에 대해 알아보겠습니다. 선택 정렬 작업 절차도 간단합니다. 이 기사는 학생들이 시험에서 선택 문제로 직면할 수 있기 때문에 학생들에게 매우 도움이 되고 흥미로울 것입니다. 따라서 주제에 대해 토론하는 것이 중요합니다.

선택 정렬에서는 배열의 정렬되지 않은 요소 중에서 가장 작은 값이 모든 패스에서 선택되어 배열의 적절한 위치에 삽입됩니다. 가장 간단한 알고리즘이기도 합니다. 내부 비교 정렬 알고리즘입니다. 이 알고리즘에서 배열은 두 부분으로 나누어집니다. 첫 번째는 정렬된 부분이고 다른 하나는 정렬되지 않은 부분입니다. 처음에는 배열의 정렬된 부분은 비어 있고, 정렬되지 않은 부분은 주어진 배열입니다. 정렬된 부분은 왼쪽에 배치되고, 정렬되지 않은 부분은 오른쪽에 배치됩니다.

선택 정렬에서는 정렬되지 않은 배열에서 첫 번째로 작은 요소가 선택되어 첫 번째 위치에 배치됩니다. 그 후 두 번째로 작은 요소가 선택되어 두 번째 위치에 배치됩니다. 배열이 완전히 정렬될 때까지 프로세스가 계속됩니다.

선택 정렬의 평균 및 최악의 복잡성은 다음과 같습니다. 에²) , 어디 N 항목의 개수입니다. 이로 인해 대규모 데이터 세트에는 적합하지 않습니다.

선택 정렬은 일반적으로 다음과 같은 경우에 사용됩니다.

작은 배열을 정렬해야 합니다.
교환비용은 상관없어요
모든 요소를 필수로 확인해야 합니다.

이제 선택 정렬 알고리즘을 살펴보겠습니다.

연산

 SELECTION SORT(arr, n) Step 1: Repeat Steps 2 and 3 for i = 0 to n-1 Step 2: CALL SMALLEST(arr, i, n, pos) Step 3: SWAP arr[i] with arr[pos] [END OF LOOP] Step 4: EXIT SMALLEST (arr, i, n, pos) Step 1: [INITIALIZE] SET SMALL = arr[i] Step 2: [INITIALIZE] SET pos = i Step 3: Repeat for j = i+1 to n if (SMALL &gt; arr[j]) SET SMALL = arr[j] SET pos = j [END OF if] [END OF LOOP] Step 4: RETURN pos

선택정렬 알고리즘의 작동

이제 선택 정렬 알고리즘의 작동을 살펴보겠습니다.

선택 정렬 알고리즘의 작동을 이해하기 위해 정렬되지 않은 배열을 살펴보겠습니다. 예제를 통해 선택 정렬을 이해하는 것이 더 쉬울 것입니다.

배열의 요소는 다음과 같습니다.

이제 정렬된 배열의 첫 번째 위치에 대해 전체 배열이 순차적으로 스캔됩니다.

현재, 12 첫 번째 위치에 저장되어 있으며, 전체 배열을 검색한 결과 8 가장 작은 값입니다.

자바 부울

따라서 12를 8로 바꾸십시오. 첫 번째 반복 후에는 정렬된 배열의 첫 번째 위치에 8이 나타납니다.

현재 29가 저장되어 있는 두 번째 위치의 경우 정렬되지 않은 배열의 나머지 항목을 순차적으로 다시 스캔합니다. 스캔한 후에는 12가 배열에서 두 번째 위치에 나타나야 하는 두 번째로 낮은 요소라는 것을 알게 되었습니다.

이제 29를 12로 바꿉니다. 두 번째 반복 후에는 정렬된 배열의 두 번째 위치에 12가 나타납니다. 따라서 두 번의 반복 후에 가장 작은 두 값이 정렬된 방식으로 처음에 배치됩니다.

나머지 배열 요소에도 동일한 프로세스가 적용됩니다. 이제 전체 정렬 과정을 그림으로 표현해 보겠습니다.

이제 배열이 완전히 정렬되었습니다.

선택 정렬의 복잡성

이제 최상의 경우, 평균적인 경우, 최악의 경우 선택 정렬의 시간 복잡도를 살펴보겠습니다. 또한 선택 정렬의 공간 복잡도도 살펴보겠습니다.

1. 시간 복잡도

사례	시간 복잡도
최선의 경우	에²)
평균 사례	에²)
최악의 경우	에²)

에²)

2. 공간 복잡성

공간 복잡도	오(1)
안정적인	예

선택 정렬의 공간 복잡도는 O(1)입니다. 선택정렬에서는 교체를 위해 별도의 변수가 필요하기 때문이다.

선택 정렬 구현

이제 다양한 프로그래밍 언어의 선택 정렬 프로그램을 살펴보겠습니다.

프로그램: C 언어로 선택 정렬을 구현하는 프로그램을 작성하세요.

 #include void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 17 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are - 
'); printarr(a, n); selection(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-7.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C++ language.</p> <pre> #include using namespace std; void selection(int arr[], int n) { int i, j, small; for (i = 0; i <n-1; 15 i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } void printarr(int a[], n) * function to print i; (i="0;" i cout<< a[i] <<' '; main() a[]="{" 80, 10, 29, 11, 8, 30, }; n="sizeof(a)" sizeof(a[0]); 'before sorting elements are - '<<endl; printarr(a, n); selection(a, '
after return 0; pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-8.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in C# language.</p> <pre> using System; class Selection { static void selection(int[] arr) { int i, j, small; int n = arr.Length; for (i = 0; i <n-1; i++) one by move boundary of unsorted subarray { small="i;" minimum element in array for (j="i+1;" j < n; j++) if (arr[j] arr[small]) swap the with first int temp="arr[small];" arr[small]="arr[i];" arr[i]="temp;" } static void printarr(int[] a) * function to print i; n="a.Length;" (i="0;" i console.write(a[i] + ' '); main() int[] a="{" 85, 50, 29, 18, 7, 30, 3}; console.write('before sorting elements are - printarr(a); selection(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-9.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in python.</p> <pre> def selection(a): # Function to implement selection sort for i in range(len(a)): # Traverse through all array elements small = i # minimum element in unsorted array for j in range(i+1, len(a)): if a[small] &gt; a[j]: small = j # Swap the found minimum element with # the first element a[i], a[small] = a[small], a[i] def printArr(a): # function to print the array for i in range(len(a)): print (a[i], end = &apos; &apos;) a = [69, 14, 1, 50, 59] print(&apos;Before sorting array elements are - &apos;) printArr(a) selection(a) print(&apos;
After sorting array elements are - &apos;) selection(a) printArr(a) </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-10.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in Java.</p> <pre> public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println('
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo 'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;></pre></n-1;></pre></n-1;></pre></n-1;>

산출:

프로그램: Java에서 선택 정렬을 구현하는 프로그램을 작성하세요.

 public class Selection { void selection(int a[]) /* function to sort an array with selection sort */ { int i, j, small; int n = a.length; for (i = 0; i <n-1; 21 i++) { small="i;" minimum element in unsorted array for (j="i+1;" j < n; j++) if (a[j] a[small]) swap the with first int temp="a[small];" a[small]="a[i];" a[i]="temp;" } void printarr(int a[]) * function to print i; n="a.length;" (i="0;" i system.out.print(a[i] + \' \'); public static main(string[] args) a[]="{" 91, 49, 4, 19, 10, }; selection i1="new" selection(); system.out.println(\'
before sorting elements are - i1.printarr(a); i1.selection(a); system.out.println(\'
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-11.webp" alt="selection Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement selection sort in PHP.</p> <pre> <?php function selection(&$a, $n) /* function to sort an array with selection sort */ { for ($i = 0; $i < $n; $i++) { $small = $i; //minimum element in unsorted array for ($j = $i+1; $j < $n; $j++) if ($a[$j] < $a[$small]) $small = $j; // Swap the minimum element with the first element $temp = $a[$small]; $a[$small] = $a[$i]; $a[$i] = $temp; } } function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo \' \'; } } $a = array( 90, 48, 3, 18, 9, 20 ); $n = count($a); echo \'Before sorting array elements are - <br>&apos;; printArray($a, $n); selection($a, $n); echo &apos; <br> After sorting array elements are - <br>&apos;; printArray($a, $n); ?&gt; </pre> <p> <strong>Output:</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/65/selection-sort-algorithm-12.webp" alt="selection Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Selection sort complexity, working, and implementation in different programming languages.</p> <hr></n-1;>

산출:

위 코드를 실행하면 출력은 다음과 같습니다.

이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.

이 글은 알고리즘에만 국한된 것이 아닙니다. 또한 다양한 프로그래밍 언어에서의 선택 정렬 복잡성, 작업 및 구현에 대해서도 논의했습니다.