introduction sorting techniques c
C ++의 다양한 정렬 기법 목록.
정렬은 특정 순서로 데이터를 정렬하기 위해 구현되는 기술입니다. 데이터 더미에서 필요한 정보를 쉽게 검색 할 수 있도록 사용하는 데이터가 특정 순서로되어 있는지 확인하려면 정렬이 필요합니다.
데이터가 정리되지 않고 정렬되지 않은 경우 특정 정보를 원할 때 데이터를 검색하기 위해 매번 하나씩 검색해야합니다.
따라서 정보 검색과 데이터에 대해 수행되는 다른 작업이 쉽고 효율적으로 수행 될 수 있도록 데이터를 특정 순서로 정렬하는 것이 항상 권장됩니다.
우리는 기록 형태로 데이터를 저장합니다. 각 레코드는 하나 이상의 필드로 구성됩니다. 각 레코드에 특정 필드의 고유 한 값이있는 경우이를 키 필드라고합니다. 예를 들어, 클래스에서 Roll No는 고유 또는 키 필드가 될 수 있습니다.
특정 키 필드에서 데이터를 정렬 한 다음 오름차순 / 내림차순 또는 내림차순 / 내림차순으로 정렬 할 수 있습니다.
마찬가지로 전화 사전에서 모든 레코드는 사람의 이름, 주소 및 전화 번호로 구성됩니다. 여기에서 전화 번호는 고유하거나 키 필드입니다. 이 전화 필드에서 사전의 데이터를 정렬 할 수 있습니다. 또는 숫자 또는 영숫자로 데이터를 정렬 할 수도 있습니다.
다른 보조 메모리없이 주 메모리 자체에서 정렬 할 데이터를 조정할 수있는 경우이를 다음과 같이 호출합니다. 내부 정렬 .
반면에 정렬 중에 중간 데이터를 저장하기위한 보조 메모리가 필요한 경우이 기술을 다음과 같이 호출합니다. 외부 정렬 .
이 튜토리얼에서는 C ++의 다양한 정렬 기술을 자세히 배웁니다.
학습 내용 :
C ++의 정렬 기법
C ++는 아래와 같이 다양한 정렬 기술을 지원합니다.
버블 정렬
버블 정렬은 모든 요소를 인접한 요소와 비교하고 순서가 맞지 않으면 요소를 교체하는 가장 간단한 기술입니다. 이렇게하면 모든 반복이 끝날 때 (패스라고 함) 가장 무거운 요소가 목록 끝에 버블 링됩니다.
다음은 버블 정렬의 예입니다.
정렬 할 배열 :
위에서 볼 수 있듯이 작은 배열이고 거의 정렬 되었기 때문에 몇 번의 패스만으로 완전히 정렬 된 배열을 얻을 수있었습니다.
C ++에서 Bubble Sort 기법을 구현해 보겠습니다.
#include using namespace std; int main () { int i, j,temp; int a(5) = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < 산출:
입력 목록…
10 2 0 43 12
정렬 된 요소 목록…
0 2 10 12 43
출력에서 볼 수 있듯이 버블 정렬 기법에서는 모든 패스에서 가장 무거운 요소가 배열 끝까지 버블 링되어 배열이 완전히 정렬됩니다.
트리 데이터 구조 C ++
선택 정렬
목록에서 가장 작은 요소를 찾아 적절한 위치에 배치하는 방법은 간단하지만 구현하기 쉽습니다. 각 패스에서 다음으로 가장 작은 요소가 선택되고 적절한 위치에 배치됩니다.
이전 예제에서와 동일한 배열을 선택하고이 배열을 정렬하기 위해 선택 정렬을 수행해 보겠습니다.
위의 그림에서 볼 수 있듯이 N 개의 요소에 대해 N-1 패스를 사용하여 배열을 완전히 정렬합니다. 모든 패스가 끝날 때 배열에서 가장 작은 요소가 정렬 된 배열의 적절한 위치에 배치됩니다.
다음으로 C ++를 사용하여 선택 정렬을 구현해 보겠습니다.
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(5) = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< 산출:
정렬 할 요소 목록 입력
12 45 8 15 33
정렬 된 요소 목록은
8 12 15 33 45
선택 정렬에서는 모든 패스에서 배열의 가장 작은 요소가 적절한 위치에 배치됩니다. 따라서 정렬 프로세스가 끝나면 완전히 정렬 된 배열을 얻습니다.
삽입 정렬
삽입 정렬은 목록의 두 번째 요소에서 시작하는 기술입니다. 두 번째 요소를 이전 요소 (1성) 요소를 제거하고 적절한 위치에 배치합니다. 다음 단계에서는 각 요소에 대해 이전 요소와 비교하고 해당 요소를 적절한 위치에 삽입합니다.
위의 세 가지 정렬 기술은 간단하고 구현하기 쉽습니다. 이러한 기술은 목록 크기가 더 작을 때 잘 수행됩니다. 목록의 크기가 커짐에 따라 이러한 기술은 효율적으로 수행되지 않습니다.
다음 그림을 이해하면 기술이 명확 해집니다.
정렬 할 배열은 다음과 같습니다.
이제 각 패스에 대해 현재 요소를 모든 이전 요소와 비교합니다. 따라서 첫 번째 단계에서는 두 번째 요소부터 시작합니다.
따라서 N 개의 요소를 포함하는 배열을 완전히 정렬하려면 N 개의 패스가 필요합니다.
C ++를 사용하여 삽입 정렬 기술을 구현해 보겠습니다.
#include using namespace std; int main () { int myarray(5) = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < 산출:
입력 목록은
12 4 3 1 15
정렬 된 목록은
1 34 12 15
위의 출력은 삽입 정렬을 사용하여 정렬 된 전체 배열을 보여줍니다.
빠른 정렬
Quicksort는 데이터를 정렬하는 데 사용할 수있는 가장 효율적인 알고리즘입니다. 이 기술은 문제를 여러 하위 문제로 나누고 이러한 하위 문제를 해결 한 후 개별적으로 병합하여 완전한 정렬 목록을 만드는 '분할 및 정복'전략을 사용합니다.
퀵 정렬에서는 먼저 피벗 요소를 중심으로 목록을 나눈 다음 피벗 요소에 따라 적절한 위치에 다른 요소를 배치합니다.
위의 그림에서 볼 수 있듯이 Quicksort 기법에서는 피벗보다 작은 모든 요소가 왼쪽에 있고 피벗보다 큰 요소가 오른쪽에 있도록 배열을 피벗 요소 주위로 나눕니다. 그런 다음이 두 배열을 독립적으로 가져와 정렬 한 다음 결합하거나 정복하여 결과 정렬 된 배열을 얻습니다.
Quicksort의 핵심은 피벗 요소를 선택하는 것입니다. 배열의 첫 번째, 마지막 또는 중간 요소 일 수 있습니다. 피벗 요소를 선택한 후 첫 번째 단계는 배열을 적절하게 분할 할 수 있도록 피벗을 올바른 위치에 배치하는 것입니다.
C ++를 사용하여 빠른 정렬 기술을 구현해 보겠습니다.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< 산출:
입력 배열
12 23 3 43 51
Quicksort로 정렬 된 배열
3 12 23 43 51
위의 퀵 정렬 구현에서는 배열의 마지막 요소 인 피벗 요소 주위에 입력 배열을 분할하는 데 사용되는 분할 루틴이 있습니다. 그런 다음 Quicksort 루틴을 재귀 적으로 호출하여 그림과 같이 하위 배열을 개별적으로 정렬합니다.
병합 정렬
이것은 '분할 및 정복'전략을 사용하는 또 다른 기술입니다. 이 기술에서는 먼저 목록을 동일한 절반으로 나눕니다. 그런 다음 두 목록이 모두 정렬되도록 이러한 목록에 대해 병합 정렬 기술을 독립적으로 수행합니다. 마지막으로 두 목록을 병합하여 완전한 정렬 목록을 얻습니다.
병합 정렬 및 빠른 정렬은 대부분의 다른 정렬 기술보다 빠릅니다. 목록 크기가 커져도 성능은 그대로 유지됩니다.
병합 정렬 기법의 예를 살펴 보겠습니다.
위의 그림에서 병합 정렬 기술은 각 하위 배열에 요소가 하나만있을 때까지 원래 배열을 하위 배열로 반복적으로 분할합니다. 이 작업이 완료되면 하위 배열이 독립적으로 정렬되고 함께 병합되어 완전한 정렬 된 배열을 형성합니다.
다음으로 C ++ 언어를 사용하여 Merge Sort를 구현해 보겠습니다.
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< 산출:
정렬 할 요소 수 입력 : 5
정렬 할 5 개 요소 입력 : 10 21 47 3 59
정렬 된 배열
3 10 21 47 59
쉘 정렬
쉘 정렬은 삽입 정렬 기술의 확장입니다. 삽입 정렬에서는 다음 요소 만 처리하는 반면, 쉘 정렬에서는 상위 목록에서 더 작은 목록을 만드는 데 사용하는 증분 또는 간격을 제공합니다. 하위 목록의 요소는 연속적 일 필요가 없으며 일반적으로 'gap_value'떨어져 있습니다.
셸 정렬은 삽입 정렬보다 빠르게 수행되며 삽입 정렬보다 이동이 적습니다.
숙련 된 개발자를위한 세일즈 포스 인터뷰 질문 및 답변
간격을 제공하면 3 개의 요소가 떨어져있는 각 요소가있는 다음 하위 목록이 있습니다.
그런 다음이 세 가지 하위 목록을 정렬합니다.
정렬 된 하위 배열을 병합 한 후 얻은 위의 배열은 거의 정렬되어 있습니다. 이제이 배열에서 삽입 정렬을 수행하여 전체 배열을 정렬 할 수 있습니다.
따라서 적절한 증분을 사용하여 배열을 하위 목록으로 나누고 함께 병합하면 거의 정렬 된 목록을 얻을 수 있습니다. 이 목록에서 삽입 정렬 기술을 수행 할 수 있으며 배열은 원래 삽입 정렬보다 적은 이동으로 정렬됩니다.
아래는 C ++에서 쉘 정렬의 구현입니다.
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18}; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i 산출:
정렬 할 배열 :
45 23 53 43 18
쉘 정렬 후 배열 :
18 23 43 45 53
따라서 셸 정렬은 삽입 정렬보다 크게 개선 된 역할을하며 배열을 정렬하는 데 절반의 단계도 필요하지 않습니다.
힙 정렬
힙 정렬은 힙 데이터 구조 (최소 힙 또는 최대 힙)를 사용하여 목록을 정렬하는 기술입니다. 먼저 정렬되지 않은 목록에서 힙을 생성하고 힙을 사용하여 배열을 정렬합니다.
힙 정렬은 효율적이지만 빠르거나 병합 정렬은 아닙니다.
위의 그림에 표시된 것처럼 먼저 정렬 할 배열 요소에서 최대 힙을 구성합니다. 그런 다음 힙을 탐색하고 마지막 요소와 첫 번째 요소를 바꿉니다. 현재 마지막 요소는 이미 정렬되어 있습니다. 그런 다음 나머지 요소에서 최대 힙을 다시 구성합니다.
다시 힙을 탐색하고 첫 번째와 마지막 요소를 교체하고 마지막 요소를 정렬 된 목록에 추가합니다. 이 프로세스는 정렬 된 목록의 첫 번째 요소가되는 힙에 하나의 요소 만 남을 때까지 계속됩니다.
이제 C ++를 사용하여 힙 정렬을 구현해 보겠습니다.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i 산출:
입력 배열
4 17 3 12 9
정렬 된 배열
34 9 12 17
지금까지 모든 주요 정렬 기술을 그림과 함께 간략하게 설명했습니다. 각 기술을 이해하기 위해 다양한 예제와 함께 후속 자습서에서 이러한 각 기술을 자세히 배웁니다.
결론
데이터를 올바른 순서로 정렬하려면 정렬이 필요합니다. 정렬되지 않고 정리되지 않으면 액세스하는 데 더 오랜 시간이 걸리므로 전체 프로그램의 성능에 영향을 미칠 수 있습니다. 따라서 액세스, 검색, 조작 등과 같은 데이터와 관련된 모든 작업에 대해 정렬 할 데이터가 필요합니다.
프로그래밍에 사용되는 많은 정렬 기술이 있습니다. 각 기술은 우리가 사용하는 데이터 구조 또는 알고리즘이 데이터를 정렬하는 데 걸리는 시간 또는 알고리즘이 데이터를 정렬하는 데 사용하는 메모리 공간에 따라 사용할 수 있습니다. 우리가 사용하는 기술은 정렬하는 데이터 구조에 따라 다릅니다.
정렬 기술을 사용하면 데이터 구조를 특정 순서로 정렬하고 요소를 오름차순 또는 내림차순으로 정렬 할 수 있습니다. 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 쉘 정렬, 병합 정렬 및 힙 정렬과 같은 정렬 기술을 보았습니다. 버블 정렬 및 선택 정렬이 더 간단하고 구현하기 쉽습니다.
후속 자습서에서는 위에서 언급 한 각 정렬 기술을 자세히 살펴 보겠습니다.
=> 무료 C ++ 과정을 보려면 여기를 클릭하십시오.
추천 도서
