정렬은 요소를 오름차순(또는 내림차순)으로 정렬하는 과정입니다.
정렬 유형
C 언어는 다음과 같은 5가지 정렬 기술을 제공합니다. -
- 버블 정렬(또는) 교환 정렬
- 선택 정렬
- 삽입 정렬(또는) 선형 정렬
- 빠른 정렬(또는) 파티션 교환 정렬
- 병합 정렬(또는) 외부 정렬
빠른 정렬
분할 정복 알고리즘입니다.
- 1단계 - 배열에서 요소를 선택하고 그것을 피벗 요소라고 합니다.
- 2단계 - 정렬되지 않은 배열 요소를 두 개의 배열로 나눕니다.
- 3단계 - 피벗 요소보다 작은 값이 첫 번째 하위 배열 아래에 오면 피벗보다 큰 값을 가진 나머지 요소가 두 번째 하위 배열에 옵니다.
아래 주어진 예를 고려하십시오. 여기서
- P는 피벗 요소입니다.
- L은 왼쪽 포인터입니다.
- R은 오른쪽 포인터입니다.
요소는 6, 3, 7, 2, 4, 5입니다.
지금,
- 피벗이 고정된 위치에 있습니다.
- 왼쪽 요소가 모두 적습니다.
- 오른쪽 요소가 피벗보다 큽니다.
- 이제 배열을 왼쪽 부분과 오른쪽 부분 2개의 하위 배열로 나눕니다.
- 왼쪽 파티션을 사용하여 빠른 정렬을 적용합니다.
지금,
- 피벗이 고정된 위치에 있습니다.
- 모든 왼쪽 요소가 더 적고 정렬됨
- 오른쪽 요소가 더 크고 정렬된 순서로 표시됩니다.
- 최종 정렬된 목록은 2, 3, 4, 5, 6, 7의 두 하위 배열을 결합하는 것입니다.
예시
다음은 빠른 정렬 기술을 사용하여 요소를 정렬하는 C 프로그램입니다 -
#include<stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i<count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i<count;i++)
printf(" %d",number[i]);
return 0;
} 출력
위의 프로그램이 실행되면 다음과 같은 출력을 생성합니다 -
How many elements are u going to enter?: 10 Enter 10 elements: 2 3 5 7 1 9 3 8 0 4 Order of Sorted elements: 0 1 2 3 3 4 5 7 8 9