C에서 선택 정렬을 구현하는 방법?

선택 정렬은 배열의 가장 낮은 정수를 찾아 최상위 위치에 할당하는 방식으로 작동하는 또 다른 알고리즘입니다. 가장 작은 정수 위치 옆의 인덱스는 스캔해야 하는 다음 배열을 시작하는 데 사용됩니다.

C에서 선택 정렬의 예

가장 작은 숫자가 2인 숫자 [10,2,8,4,6]이 있는 배열을 가져오면 가장 작은 숫자인 2를 첫 번째 위치에 배치하고 그 다음에 배열을 찾습니다. [2,10,8,4,6]과 같이. 다음으로 2가 이미 올바른 위치에 있기 때문에 다음으로 가장 작은 숫자를 사용합니다. 다음으로 작은 숫자는 4로, 두 번째 위치에 배치되며, 그 후 배열이 최종적으로 정렬될 때까지 유사하게 검색됩니다.

C의 선택 정렬은 숫자를 오름차순으로 정렬합니다. 알고리즘을 수정하면 숫자를 내림차순으로 정렬할 수 있습니다. 선택 정렬 C++ 또는 선택 정렬 Python 과 같은 C 이외의 다른 언어에서도 수행할 수 있습니다 .

세계 최고의 대학에서 소프트웨어 개발 과정을 온라인으로 배우십시오. PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 취득하여 경력을 빠르게 쌓으십시오.

선택 정렬 알고리즘

• 먼저 선택 정렬 알고리즘 의 올바른 절차를 위해 선택 정렬의 초기 요소를 최소값으로 설정하고 배열에서 가장 작은 요소를 검색합니다 .
• 이제 최소 요소가 두 번째 구성 요소와 비교됩니다. 두 번째 요소가 최소값 아래로 떨어지면 이를 교체한 다음 세 번째 요소에 최소값을 할당합니다.
• 그렇지 않으면 세 번째 요소로 계속 진행하여 최소값과 비교합니다. 두 번째 요소가 첫 번째 요소를 초과하면 교체합니다. 마지막 구성 요소까지 이 과정을 반복합니다.
• 반복할 때마다 최소값이 정렬되지 않은 목록의 시작 부분에 도달한 것을 볼 수 있습니다.
• 각 반복에 대해 정렬되지 않은 목록의 첫 번째 항목부터 인덱싱을 시작합니다. 목록이 정렬되거나 모든 구성 요소가 적절하게 배치될 때까지 1~4단계를 여러 번 반복합니다.

소프트웨어 엔지니어링에 대한 인기 코스 및 기사

각 반복에 대한 다음 예제는 C 에서 선택 정렬 프로세스를 자세히 이해하는 데 도움이 됩니다.

반복 #1

나는 [ ] = 8,5,2,6,4

최소 설정 - 8

i 0 과 i 1 비교

i 0 > i 1 이므로 최소값 = 5로 설정합니다.

• i1 과 i2 비교

i 1 > i 2 이므로 최소값 = 2로 설정합니다.

• i 2 와 i 3 비교

i 2 < i 3 이므로 최소값= 2로 설정합니다.

• i 2 와 i 4 비교

i 2 < i 4 이므로 최소값을 2로 설정합니다.

2는 모든 요소 중 가장 작은 수이므로 i 0 과 i 2 를 바꿔야 합니다.

­ 반복 #2

I [ ]= 2,5,8,6,4

최소 5개 설정

• i1 과 i2 비교

i 1 < i 2 이므로 최소값 = 5로 설정합니다.

• i 1 과 i 3 비교

i 1 < i 3이므로 최소값 = 5로 설정

• i 1 과 i 4 비교

다시, i 1 < i 4 , 최소값 = 4로 설정합니다.

4는 배열에서 가장 작은 요소이므로 i 1 과 i 4 를 바꿔야 합니다 .

반복 #3

나 [ ]= 2,4,8,6,5

최소 8개 설정

• i 2 와 i 3 비교

i 2 > i 3 이므로 최소값 = 6으로 설정합니다.

• i 3 과 i 4 비교

i 3 > i 4 이므로 최소값 = 5로 설정합니다.

5는 배열에서 가장 작은 요소이므로 i 2 와 i 4 를 바꿔야 합니다 .

반복 #4

나는 [ ] = 2,4,5,6,8

최소 6개 설정

• i 3 과 i 4 비교

i 3 < i 4 이므로 최소값 = 6으로 설정합니다.

최소값은 올바른 위치에 배치됩니다. 따라서 스와핑이 발생하지 않습니다.

C의 선택 정렬 예

// C에서 선택 정렬

#include <stdio.h>

// 두 요소의 위치를 ​​바꾸는 함수

무효 스왑(int *a, int *b) {

정수 온도 = *a;

*a = *b;

*b = 온도;

}

void selectionSort(int 배열[], int 크기) {

for (int 단계 = 0; 단계 < 크기 – 1; 단계++) {

int min_idx = 단계;

for (int i = 단계 + 1; i < 크기; i++) {

// 내림차순으로 정렬하려면 이 줄에서 >를 <로 변경합니다.

// 각 루프에서 최소 요소를 선택합니다.

if (배열[i] < 배열[min_idx])

min_idx = i;

}

// min을 올바른 위치에 배치

swap(&array[min_idx], &array[단계]);

}

}

// 배열을 출력하는 함수

void printArray(int 배열[], int 크기) {

for (int i = 0; i < 크기; ++i) {

printf("%d ", 배열[i]);

}

printf("\n");

}

// 드라이버 코드

정수 메인() {

정수 데이터[] = {20, 12, 10, 15, 2};

정수 크기 = 크기(데이터) / 크기(데이터[0]);

selectionSort(데이터, 크기);

printf("오름차순으로 정렬된 배열:\n");

printArray(데이터, 크기);

}

선택 정렬의 복잡도 분석

입력 – n개의 입력 항목이 주어집니다.

출력 – 목록을 정렬하는 데 필요한 단계 수입니다.

논리 – n개의 항목이 주어지면 첫 번째 패스에서 n-1 비교, 두 번째 패스에서 n-2 비교, 세 번째 패스에서 n-3 비교 등을 수행합니다. 결과적으로 총 비교 수는 다음을 사용하여 계산할 수 있습니다.

출력 –

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

합계 = n(n-1)/2 즉, O(n²)

선택 정렬 방식은 스와핑을 위한 임시 변수를 위한 추가 메모리 공간이 필요하기 때문에 시간 복잡도는 O(n2)이고 공간 복잡도는 O(1)입니다.

선택 정렬 시간 복잡도 분석

최상의 경우: 이전에 정렬된 배열의 경우 선택 정렬 방법의 최상의 경우 시간 복잡도는 O(n²)입니다.

평균 경우: 선택 정렬 알고리즘은 항목이 뒤죽박죽 배열될 때, 즉 오름차순도 내림차순도 아닌 경우 평균 사례 시간 복잡도가 O(n²)입니다.

최악의 경우: 배열의 내림차순을 오름차순으로 바꿀 때 최악의 시간 복잡도는 O(n²)입니다.

선택 정렬 방법의 시간 복잡도는 세 가지 시나리오 각각에서 O(n²)입니다. 각 단계의 최소한의 항목을 파악해야 제대로 배치할 수 있기 때문입니다. 전체 배열을 추적한 후 최소 요소를 찾았습니다.

결론

이것으로 "Selection Sort In C"에 대한 블로그 게시물을 마칩니다. 선택 정렬 C++ 및 선택 정렬 Python과 같은 다른 언어에서도 수행될 수 있음을 이해해야 합니다 . 이 기사가 C에서 요소를 정렬하는 방법을 이해하는 데 도움이 되기를 바랍니다.

선택 정렬은 프로그래머가 되는 여정의 유일한 부분이 아닙니다. 전문 학위로 소프트웨어 개발 경력을 크게 향상시키고 싶다면 upGrad가 여기 있습니다! upGrad의 프런트엔드 개발(JavaScript, HTML, CSS), 백엔드(NoSQL-MongoDB) 및 마이크로서비스를 개발했다면 UpGrad의 컴퓨터 과학 석사 과정을 이수할 수 있습니다. IIIT Bangalore & LJMU Alumni Status에서 제공하는 이 과정은 전 세계 기술 대기업에서 소프트웨어 엔지니어/풀스택 개발자로 경력을 쌓는 데 도움이 됩니다.

이 과정은 Java, Spring 및 Hibernate와 같은 도구에 대한 기본 지식을 다루며 풀 스택 개발 기술을 강화하여 놀라운 기회가 있는 취업 시장을 탐색합니다.

자세히 알아보려면 가입 하세요!