이 튜토리얼에서는 Python에서 선택 정렬 알고리즘을 구현합니다. 적은 스와핑을 사용하는 매우 간단한 알고리즘입니다.
이 알고리즘에서는 각 패스의 정렬되지 않은 배열에서 가장 작은 요소를 선택하고 정렬되지 않은 배열의 시작 부분과 바꿉니다. 이 과정은 모든 요소가 올바른 위치에 배치될 때까지 계속됩니다. 이는 간단하고 내부 비교 정렬 알고리즘입니다.
선택 정렬 작업
다음은 Python의 선택 정렬 작업을 설명하는 단계입니다.
선택 정렬 알고리즘을 적용하기 위해 정렬되지 않은 배열을 사용하겠습니다.
[30, 10, 12, 8, 15, 1]
1 단계: 배열의 길이를 가져옵니다.
길이 = len(배열) → 6
2 단계: 먼저 첫 번째 요소를 최소 요소로 설정합니다.
단계 - 3: 이제 최소값을 두 번째 요소와 비교하십시오. 두 번째 요소가 첫 번째 요소보다 작으면 이를 최소값으로 지정합니다.
다시 두 번째 요소를 세 번째 요소와 비교하고 세 번째 요소가 두 번째 요소보다 작으면 이를 최소값으로 지정합니다. 이 프로세스는 마지막 요소를 찾을 때까지 계속됩니다.
단계 - 4: 각 반복 후에 정렬되지 않은 배열 앞에서 최소 요소가 교체됩니다.
단계 - 5: 두 번째부터 세 번째 단계는 정렬된 배열을 얻을 때까지 반복됩니다.
선택 정렬 알고리즘
선택 정렬 알고리즘은 다음과 같습니다.
연산
selection_sort(array) repeat (0, length - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element <currentminimum set element as new minimum swap with first unsorted position end selection_sort < pre> <h2>Selection Sort Program using Python</h2> <p>The following code snippet shows the selection sort algorithm implementation using Python.</p> <p> <strong>Code -</strong> </p> <pre> def selection_sort(array): length = len(array) for i in range(length-1): minIndex = i for j in range(i+1, length): if array[j] <array[minindex]: minindex="j" array[i], array[minindex]="array[minIndex]," array[i] return array print('the sorted is: ', selection_sort(array)) < pre> <p> <strong>Output:</strong> </p> <pre> The sorted array is: [3, 6, 9, 21, 33] </pre> <p> <strong>Explanation -</strong> </p> <p>Let's understand the above code -</p> <ul> <li>First, we define the <strong>selection_sort()</strong> function that takes array as an argument.</li> <li>In the function, we get the length of the array which used to determine the number of passes to be made comparing values.</li> <li>As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable</li> <li>The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.</li> <li>Find the minimum element in the unsorted list and update the minIndex position.</li> <li>Place the value at the beginning of the array.</li> <li>Once the iteration is completed, the sorted array is returned.</li> <li>At last we create an unsorted array and pass to the <strong>selection_sort()</strong> It prints the sorted array.</li> </ul> <h2>Time Complexity of Selection Sort</h2> <p>Time complexity is an essential in term of how much time an algorithm take to sort it. In the selection sort, there are two loops. The outer loop runs for the n times (n is a total number of element).</p> <p>The inner loop is also executed for n times. It compares the rest of the value to outer loop value. So, there is n*n times of execution. Hence the time complexity of merge sort algorithm is O(n<sup>2</sup>).</p> <p>The time complexity can be categorized into three categories.</p> <hr></array[minindex]:></pre></currentminimum> 설명 -
위의 코드를 이해해 봅시다 -
- 먼저, 우리는 선택_정렬() 배열을 인자로 받는 함수.
- 함수에서 값을 비교하는 패스 수를 결정하는 데 사용된 배열의 길이를 얻습니다.
- 보시다시피 외부 루프와 내부 루프라는 두 개의 루프를 사용합니다. 외부 루프는 목록의 값을 반복하는 데 사용됩니다. 이 루프는 0부터 (길이-1)까지 반복됩니다. 따라서 첫 번째 반복은 (5-1) 또는 4번 수행됩니다. 각 반복에서 변수 i의 값이 변수에 할당됩니다.
- 내부 루프는 오른쪽 요소의 각 값을 가장 왼쪽 요소의 다른 값과 비교하는 데 사용됩니다. 따라서 두 번째 루프는 i+1부터 반복을 시작합니다. 정렬되지 않은 값만 선택됩니다.
- 정렬되지 않은 목록에서 최소 요소를 찾고 minIndex 위치를 업데이트합니다.
- 배열의 시작 부분에 값을 배치합니다.
- 반복이 완료되면 정렬된 배열이 반환됩니다.
- 마지막으로 정렬되지 않은 배열을 생성하고 선택_정렬() 정렬된 배열을 인쇄합니다.
선택 정렬의 시간 복잡도
시간 복잡도는 알고리즘이 정렬하는 데 걸리는 시간과 관련하여 필수적입니다. 선택 정렬에는 두 개의 루프가 있습니다. 외부 루프는 n번 동안 실행됩니다(n은 전체 요소 수).
자바에서 문자열을 정수로
내부 루프도 n번 실행됩니다. 나머지 값을 외부 루프 값과 비교합니다. 따라서 n*n번의 실행이 있습니다. 따라서 병합 정렬 알고리즘의 시간 복잡도는 O(n2).
시간 복잡도는 세 가지로 분류할 수 있습니다.