선택 정렬 – 데이터 구조 및 알고리즘 자습서 - TECHCODEVIEW.COM

선택 정렬 목록의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 반복적으로 선택하고 이를 목록의 정렬된 부분으로 이동하여 작동하는 간단하고 효율적인 정렬 알고리즘입니다.

알고리즘은 목록의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 반복적으로 선택하고 이를 정렬되지 않은 부분의 첫 번째 요소와 교체합니다. 전체 목록이 정렬될 때까지 정렬되지 않은 나머지 부분에 대해 이 프로세스가 반복됩니다.

선택 정렬 알고리즘은 어떻게 작동하나요?

다음 배열을 예로 들어 보겠습니다. 도착[] = {64, 25, 12, 22, 11}

첫 번째 패스:

정렬된 배열의 첫 번째 위치의 경우 전체 배열이 인덱스 0부터 4까지 순차적으로 이동됩니다. 첫 번째 위치는 64 현재 저장되어 있으며 전체 배열을 순회한 후에는 다음이 분명합니다. 열하나 가장 낮은 값입니다.
따라서 64를 11로 바꿉니다. 한 번 반복한 후 열하나 배열에서 가장 작은 값인 는 정렬된 목록의 첫 번째 위치에 나타나는 경향이 있습니다.

선택 정렬 알고리즘 | 첫 번째 요소를 배열의 최소값으로 교체

두 번째 패스:

25가 존재하는 두 번째 위치의 경우 다시 배열의 나머지 부분을 순차적으로 탐색합니다.
탐색한 후에 우리는 그것을 발견했습니다. 12 는 배열에서 두 번째로 낮은 값이고 배열의 두 번째 위치에 나타나야 하므로 이 값을 바꿉니다.

선택 정렬 알고리즘 | i=1을 다음 최소 요소로 교체

세 번째 패스:

이제 3위는 어디일까요? 25 다시 배열의 나머지 부분을 탐색하여 배열에 있는 세 번째로 작은 값을 찾습니다.
횡단하는 동안, 22 세 번째로 작은 값이 나왔고 배열의 세 번째 위치에 나타나야 하므로 교체됩니다. 22 세 번째 위치에 요소가 있습니다.

선택 정렬 알고리즘 | i=2를 다음 최소 요소로 교체

네 번째 패스:

마찬가지로 네 번째 위치의 경우 배열의 나머지 부분을 순회하여 배열에서 네 번째로 작은 요소를 찾습니다.
처럼 25 는 네 번째로 낮은 값이므로 네 번째 위치에 배치됩니다.

선택 정렬 알고리즘 | i=3을 다음 최소 요소로 교체

다섯 번째 패스:

마침내 배열에 존재하는 가장 큰 값이 자동으로 배열의 마지막 위치에 배치됩니다.
결과 배열은 정렬된 배열입니다.

선택 정렬 알고리즘 | 필수 정렬 배열

추천 연습 선택 정렬 시도해 보세요!

다음은 위의 접근 방식을 구현한 것입니다.

C++

 // C++ program for implementation of // selection sort #include  using namespace std; // Function for Selection sort void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of  // unsorted subarray  for (i = 0; i < n - 1; i++) {  // Find the minimum element in  // unsorted array  min_idx = i;  for (j = i + 1; j < n; j++) {  if (arr[j] < arr[min_idx])  min_idx = j;  }  // Swap the found minimum element  // with the first element  if (min_idx != i)  swap(arr[min_idx], arr[i]);  } } // Function to print an array void printArray(int arr[], int size) {  int i;  for (i = 0; i < size; i++) {  cout << arr[i] << ' ';  cout << endl;  } } // Driver program int main() {  int arr[] = { 64, 25, 12, 22, 11 };  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call  selectionSort(arr, n);  cout << 'Sorted array: 
';  printArray(arr, n);  return 0; } // This is code is contributed by rathbhupendra>

씨

 // C program for implementation of selection sort #include  void swap(int *xp, int *yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } void selectionSort(int arr[], int n) {  int i, j, min_idx;  // One by one move boundary of unsorted subarray  for (i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  min_idx = i;  for (j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first element  if(min_idx != i)  swap(&arr[min_idx], &arr[i]);  } } /* Function to print an array */ void printArray(int arr[], int size) {  int i;  for (i=0; i < size; i++)  printf('%d ', arr[i]);  printf('
'); } // Driver program to test above functions int main() {  int arr[] = {64, 25, 12, 22, 11};  int n = sizeof(arr)/sizeof(arr[0]);  selectionSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>

자바

 // Java program for implementation of Selection Sort import java.io.*; public class SelectionSort {  void sort(int arr[])  {  int n = arr.length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n-1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i+1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  void printArray(int arr[])  {  int n = arr.length;  for (int i=0; i

파이썬3

 # Python program for implementation of Selection # Sort A = [64, 25, 12, 22, 11] # Traverse through all array elements for i in range(len(A)-1): # Find the minimum element in remaining  # unsorted array min_idx = i for j in range(i+1, len(A)): if A[min_idx]>A[j]: min_idx = j # 발견된 최소 요소를 # 첫 번째 요소와 교체 A[i], A[min_idx] = A[min_idx], A[i] # 위 테스트를 위한 드라이버 코드 print ('Sorted array ') for i in range(len(A)): print(A[i],end=' ')>

씨#

 // C# program for implementation  // of Selection Sort using System; class GFG {   static void sort(int []arr)  {  int n = arr.Length;  // One by one move boundary of unsorted subarray  for (int i = 0; i < n - 1; i++)  {  // Find the minimum element in unsorted array  int min_idx = i;  for (int j = i + 1; j < n; j++)  if (arr[j] < arr[min_idx])  min_idx = j;  // Swap the found minimum element with the first  // element  int temp = arr[min_idx];  arr[min_idx] = arr[i];  arr[i] = temp;  }  }  // Prints the array  static void printArray(int []arr)  {  int n = arr.Length;  for (int i=0; i

자바스크립트

PHP

  // PHP program for implementation  // of selection sort  function selection_sort(&$arr, $n) { for($i = 0; $i < $n ; $i++) { $low = $i; for($j = $i + 1; $j < $n ; $j++) { if ($arr[$j] < $arr[$low]) { $low = $j; } } // swap the minimum value to $ith node if ($arr[$i]>$arr[$low]) { $tmp = $arr[$i]; $arr[$i] = $arr[$low]; $arr[$low] = $tmp; } } } // 드라이버 코드 $arr = array(64, 25, 12, 22, 11); $len = 개수($arr); Selection_sort($arr, $len); echo '정렬된 배열: 
'; ($i = 0; $i< $len; $i++) echo $arr[$i] . ' '; // This code is contributed  // by Deepika Gupta.  ?>>

산출

Sorted array: 11 12 22 25 64>

선택 정렬의 복잡성 분석

시간 복잡도: 선택 정렬의 시간 복잡도는 다음과 같습니다. 에 ² ) 두 개의 중첩 루프가 있으므로:

배열의 요소를 하나씩 선택하는 하나의 루프 = O(N)
해당 요소를 다른 모든 배열 요소와 비교하는 또 다른 루프 = O(N)
따라서 전체 복잡도 = O(N) * O(N) = O(N*N) = O(N²)

보조 공간: O(1)은 배열에서 두 값을 교환하는 동안 임시 변수에 사용되는 유일한 추가 메모리입니다. 선택 정렬은 O(N)개 이상의 스왑을 수행하지 않으며 메모리 쓰기 비용이 많이 드는 경우 유용할 수 있습니다.

자바에서 문자열의 동등성

선택 정렬 알고리즘의 장점

간단하고 이해하기 쉽습니다.
작은 데이터세트에 잘 작동합니다.

선택 정렬 알고리즘의 단점

선택 정렬은 최악의 경우와 평균적인 경우 O(n^2)의 시간 복잡도를 갖습니다.
대규모 데이터 세트에서는 제대로 작동하지 않습니다.
동일한 키를 가진 항목의 상대적 순서를 유지하지 않으므로 안정적이지 않습니다.

선택 정렬에 대해 자주 묻는 질문

Q1. 선택 정렬 알고리즘은 안정적입니까?

선택 정렬 알고리즘의 기본 구현은 다음과 같습니다. 안정적이지 않다 . 그러나 안정적으로 만들 수 있습니다. 다음을 참조하세요. 안정적인 선택 정렬 자세한 내용은.

Q2. 선택 정렬 알고리즘이 적절합니까?

예, 선택 정렬 알고리즘은 추가 공간이 필요하지 않기 때문에 내부 알고리즘입니다.

TechCodeview

선택 정렬 - 데이터 구조 및 알고리즘 자습서